http://cs.scu.edu.cn/soj/contest/contest.action?cid=262
A题，给你一个无向图，求没有连接到1的点的个数。可以用并查集或者从1出发DFS也行，10分钟1A，嘻嘻。
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 260 using namespace std; int pre[MAX]; int find(int x) { while( x != pre[x] ) x = pre[x]; return x; } void Union(int x,int y) { int a = find(x); int b = find(y); if( a == b ) return ; int c = min(a,b); pre[a] = pre[b] = pre[x] = pre[y] = c; } int main() { int n,m,i,from,to; while( ~scanf("%d%d",&n,&m) ) { for(int i=1; i<=n; i++) pre[i] = i; while( m-- ) { scanf("%d%d",&from,&to); Union(from,to); } int flag = 0; for(i=1; i<=n; i++) if( find(i) != 1 ) { flag = 1; printf("%d/n",i); } if( !flag ) printf("0/n"); } return 0; }
B题，给你小时，分钟，秒，三级排序，用sort或者qsort均可。
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 5010 using namespace std; typedef struct MAP{ int h,m,s; }MAP; MAP t[MAX]; bool cmp(MAP a, MAP b) { if( a.h == b.h ) { if( a.m == b.m ) return a.s < b.s; else return a.m < b.m; } else return a.h < b.h; } int main() { int n,i; while( ~scanf("%d",&n) ) { for(i=0; i<n; i++) scanf("%d%d%d",&t[i].h,&t[i].m,&t[i].s); sort(t,t+n,cmp); for(i=0; i<n; i++) { printf("%d %d %d/n",t[i].h,t[i].m,t[i].s); } } return 0; }
C题，给你A，B，求大于A而且不大于62的E，使得2^E的最高位等于B，求出最小的E。
WA了一次，好不容易查出错误 long long sum = (1 << 45)，这个是不对的，因为1默认的是int，所以可以用循环 sum *= 2.真悲剧，不过这个错记住了。
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> using namespace std; int main() { char str[100]; int a,b,e; int i; while( ~scanf("%d %d",&a,&b) ) { long long sum = 1; for(i=1; i<=a; i++) sum *= 2; //printf("%lld/n",sum); int flag =0; for(i=a+1; i<=62; i++) { sum *= 2; sprintf(str,"%lld",sum); if( str[0]-'0' == b ) { printf("%d/n",i); flag = 1; break; } } if( !flag ) printf("0/n"); } return 0; }
D题，数学题，给你矩阵大小以及l1，l2，求得距离在l1和l2之间的点的对数。后来和lzs同学讨论，我的想法差不多是对的 = =。。就是觉得细节太繁没有实现成功，悲剧。。。
E，没看。
F，我想法是用最大流，可是木有找到EK的邻接表的模板，也没心思做了，太累了。。这题求能从任意源点达到而且能到达任意一个汇点的点。。lzs说他的想法是正反进行两次拓扑排序。。。= =。。。这个想法好啊。。。
G、应该是DP，没仔细想，估计也不会 = =。。。
H、没看
I、求访问最多节点个数而且和它相连的节点不被访问。开始建图好纠结啊，用最大二分匹配，WA掉了。后来想起来了，直接建图，然后求最小顶点覆盖，即n-最大匹配数/2即可。A掉了。LZS说他用树形DP了，表示不懂。。
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 50010 using namespace std; typedef struct NODE{ int to; NODE *next; }NODE; NODE node[MAX*3],*head[MAX]; int used[MAX],mat[MAX]; int cou; void init() { cou = 0; memset(node,'/0',sizeof(node)); memset(head,'/0',sizeof(head)); } int Augment(int x) { int i,k; NODE *p = head[x]; while( p != NULL ) { k = p->to; if( !used[k] ) { used[k] = 1; if( mat[k] == -1 || Augment(mat[k]) ) { mat[k] = x; return 1; } } p = p->next; } return 0; } int Hungary(int s,int n) { memset(mat,-1,sizeof(mat)); int i,sum = 0; for(i=s; i<=n; i++) { memset(used,0,sizeof(used)); if( Augment(i) && head[i] != NULL ) sum++; } return sum; } void Add(int x,int y) { node[cou].to = y; node[cou].next = head[x]; head[x] = &node[cou++]; } int main() { int n,i,from,to; while( ~scanf("%d",&n) ) { init(); for(i=1; i<n; i++) { scanf("%d%d",&from,&to); Add(from,to); Add(to,from); } int ans = Hungary(1,n); printf("%d/n",n-ans/2); } return 0; }
共计A掉4题，rank 18 = =。。被虐了。。哎。。。
