hihoCoder太阁最新面经算法竞赛15
Link: http://hihocoder.com/contest/hihointerview24
题目1 : Boarding Passes
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Long long ago you took a crazy trip around the world. You can not remember which cities did you start and finish the trip. Luckily you have all the boarding passes. Can you find out the starting city and ending city?
输入
The first line contains a number N denoting the number of boarding passes. (1 <= N <= 100)
The following N lines each contain a pair of cities (the city name consists of no more than 10 capital letters)
It is guaranteed that there is always a valid solution.
输出
The starting and ending cities separated by a space.
样例输入
4
SFO HKG
PVG BOS
HKG ABC
ABC PVG
样例输出
SFO BOS
简单的题目， 根据一组车票的起终点，来判断整个行程的起始点。
“类似哈密顿图”， 不过一个点可以通过多次。
#include <iostream>
#include <cstdio>
#include <map>
using namespace std; int main(){
freopen("in.txt", "r", stdin); int n; string st1, st2;
map<string, int> startmp, endmp;
cin>>n;
for(int i=0; i<n; ++i){
cin >> st1 >> st2;
if(startmp.find(st1) == startmp.end() ){
startmp[st1] = 1;
}else{
++startmp[st1];
}
if( endmp.find(st2) == endmp.end() ){
endmp[st2] = 1;
}else{
++endmp[st2];
}
}
for(auto i= startmp.begin(); i != startmp.end(); ++i){
if( endmp.find(i->first) == endmp.end() || endmp[i->first] +1 == startmp[i->first] ){
cout << i->first << " ";
break;
}
}
for(auto i= endmp.begin(); i != endmp.end(); ++i){
if(startmp.find(i->first) == startmp.end() || startmp[i->first] + 1 == endmp[i->first] ){
cout << i->first << " ";
}
}
cout << endl;
return 0;
}
题目2 : Sorting Photo Files
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
You have a lot of photos whose file names are like:
beijing1
beijing10
beijing8
shanghai233
As you can see, all names have exactly two parts: the string part and the number part. If you sort the files in lexicographical order "beijing10" will go before "beijing8". You do not like that. You want to sort the files first in lexicographical order of the string part then in ascending order of the number part. Can you write a program to work it out?
输入
The first line contains an integer N denoting the number of files. (1 <= N <= 100)
The following N lines each contain a file name as described above.
It is guaranteed that the number part has no leading zeroes and is no more than 1000000.
输出
The sorted files one per line.
样例输入
4
beijing1
beijing10
beijing8
b233
样例输出
b233
beijing1
beijing8
beijing10
简单的题目， 划分string和num， 对其条件sort。
#include <iostream>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 100+5; struct Node{
string st;
int num;
}nd[maxn]; bool MyCmp(Node a, Node b){
if(a.st == b.st){
return a.num < b.num;
}
return a.st < b.st;
} int main(){
int n, tmp, j;
string s, s2;
cin >> n;
for(int i=0; i<n; ++i){
cin >> s;
for(j=0; j<s.length(); ++j){
if(s[j]>='0' && s[j]<='9'){
break;
}
}
nd[i].st = s.substr(0, j);
s2 = s.substr(j); tmp = 0;
for(int k=0; k<s2.length(); ++k){
tmp = 10*tmp + s2[k]-'0';
}
nd[i].num = tmp;
}
sort(nd, nd+n, MyCmp);
for(int i=0; i<n; ++i){
cout << nd[i].st << nd[i].num << endl;
}
return 0;
}
第三题：
题目3 : Circle Detect
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
You are given a directed graph G which has N nodes and M directed edges. Your task is to detect whether it contains any circle.
输入
The first line contains an integer T denoting the number of test cases. (1 <= T <= 5)
For each test case the first line contains two integers N and M. (1 <= N, M <= 100000)
Then follows M lines. Each contains two integers u and v denoting there is an edge from u to v. (1 <= u, v <= N)
输出
For each test case output "YES" or "NO" denoting whether there is a circle in the graph.
样例输入
2
5 5
1 2
2 3
4 5
5 4
4 2
3 2
1 2
2 3
样例输出
YES
NO
简单的题目， 重点在于如何使用dfs检测环。
使用dfsCheck 来检测是否有环！！！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 100000 + 5;
int n, m, flag, vis[maxn];
vector<int> mp[maxn]; bool dfsCheck(int cur){
if(vis[cur]){
return true;
}
vis[cur] = 1;
for(int i=0; i<mp[cur].size(); ++i){
if(dfsCheck(mp[cur][i])){
return true;
}
}
vis[cur] = 0;
return false;
}
int main(){
freopen("in.txt", "r", stdin); int test, x, y;
scanf("%d", &test);
while(test--){
scanf("%d %d", &n, &m);
for(int i=1; i<=n; ++i){
mp[i].clear();
vis[i] = 0;
}
for(int i=0; i<m; ++i){
scanf("%d %d", &x, &y);
mp[x].push_back(y);
}
flag = 0;
for(int i=1; i<=n; ++i){
if(dfsCheck(i)){
flag = 1;
break;
}
}
if(flag){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}