比赛地址：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=26100#rank
都是些陈题，好多以前做过了都。
A：问第一个字符串是不是第二个的子串（非连续也可以）
直接遍历一边就行了。
#define maxn 100005 char s[maxn],t[maxn]; int l1,l2; int main() { while(scanf("%s%s",&s,&t)!=EOF) { l1 = strlen(s); l2 = strlen(t); int i = 0 ; int j = 0; while(j < l1 && i < l2) { if(s[j] == t[i] ) { i ++ ; j ++ ; } else i ++ ; } if(j != l1 ) { printf("No "); } else printf("Yes "); } return 0; }
B：以前做的，就是括号的两种表示法的转化，p法表示是每一个右括号前面的左括号的个数组成的序列，w法是每个右括号的与之对应的左括号中间的左右括号个数+1 组成的序列。
算是栈的应用吧 http://www.cppblog.com/jh818012/articles/164779.html 以前的做的地址
#define maxn 100 int a[maxn]; int b[maxn]; int c[maxn]; int n ; int num; int main() { int t; scanf("%d",&t); while(t -- ) { scanf("%d",&n); for(int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]); num = 0 ; int i , j ; i = 1; j = 0 ; while(i <= n ) { while(num < a[i]) { num ++ ; c[++j] = -1 ; } c[++j] = 1; i ++ ; } int tt = j ; int x,x1 ; num = 0 ; for(i = 1 ; i <= tt; i ++ ) if(c[i] == 1) { j = i - 1; x = 1 ; x1 = 0 ; while(j > 0 ) { if(c[j] < 0 ) x1 ++ ; x += c[j]; if(x == 0 ) break; j -- ; } b[++num ] = x1; // printf("%d ",x1); } for(i = 1 ; i <= n ; i++ ) { printf("%d",b[i]); if(i != n ) printf(" "); } printf(" "); } return 0; }
C：树的前序遍历和中序遍历求后续遍历
递归求解
char str1[100],str2[100]; void dfs(int s1,int t1,int s2,int t2 ) { if(s1 < 0 || t1 < 0 || s2 < 0 || t2 < 0 ) return ; if(s1 > t1 || s2 > t1 ) return ; if(t1 == s1) { printf("%c",str1[s1]); return ; } int m1,m2; m2 = s2; while(str2[m2] != str1[s1]) m2 ++ ; m1 = s1 + (m2 - s2); dfs(s1 + 1 , m1 , s2 , m2 - 1 ); dfs(m1 + 1 , t1 , m2 + 1 , t2 ); printf("%c",str1[s1]); return ; } int main() { int len ; while(scanf("%s%s",&str1,&str2)!=EOF) { len = strlen(str1); dfs(0,len - 1 ,0,len - 1 ); printf(" "); } return 0; }
D:水bfs，想让大家练一下队列。注意边界，vis的初始化和n，k为0的情况（这里贡献wa两次）
#define maxn 400005 struct node { int x,step; }; queue<node> q ; int n,k; bool vis[maxn]; int bfs() { while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); node tmp, u ; tmp.x = n ; tmp.step = 0; vis[n] = 1 ; q.push(tmp); while(!q.empty()) { u = q.front(); q.pop(); if(u.x == k ) return u.step; // tmp.x = u.x - 1 ; tmp.step = u.step + 1 ; if(tmp.x >= 0 && !vis[tmp.x]) { q.push(tmp); vis[tmp.x] = 1; } // tmp.x = u.x + 1 ; //tmp.step = u.step + 1 ; if(tmp.x >= 0 && tmp.x < 200000 && !vis[tmp.x]) { q.push(tmp); vis[tmp.x] = 1; } // tmp.x = u.x * 2; //tmp.step = u.step + 1 ; if(tmp.x >= 0 && tmp.x < 200000 && !vis[tmp.x]) { q.push(tmp); vis[tmp.x] = 1; } } } int main() { while(scanf("%d%d",&n,&k)!=EOF) { int ans = bfs(); printf("%d ",ans); } return 0; }
E：并查集吧。题意是说n个人，m个团队，每个人可能参加多个团队（也有人不参加团队），已知0号是suspects 。如果队伍中某个人是suspects，那么这整个队伍都是suspects 。求总的suspects 的个数。
直接用并查集表示关系集合。把数据中的每组的第一个人作为代表元，其他人与他合并关系。最后统计与0相同父亲的人有多少个就行了。
#define maxn 30005 int father[maxn]; int n,m; int find(int x ) { if(x == father[x] ) return x; father[x] = find(father[x]) ; return father[x]; } void unit(int u,int v) { father[find(v)] = find(u); } void init() { for(int i = 0 ; i < maxn ; i ++ ) father[i] = i ; } int main() { int tn,db; int x ; while(scanf("%d%d",&n,&m)!=EOF && !(m == 0 && n == 0)) { init(); for(int i = 0 ; i < m ; i ++ ) { scanf("%d",&tn); if(tn == 0 ) continue ; tn -- ; scanf("%d",&db); for(int j = 0 ; j < tn ; j ++ ) { scanf("%d",&x); unit(db,x); } } int tt; tt = find(0); int ans ; ans = 1 ; for(int i = 1; i < n ;i ++ ) { if(find(i) == tt) { ans ++ ; } } printf("%d ",ans); } return 0; }