|
Posted on 2011-06-23 23:11 Uriel 阅读(383) 评论(0) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
大概是时间比较久远的缘故吧, 这套题目很水 1. A + B 拿到题目直接看了下sample, 小惊吓了一下, 仔细一看发现原来只是吓吓人的玩意, 一位一位的判断是哪个数字就行
//浙大计算机研究生复试上机考试-2005年 A + B #include<stdio.h> #include<stdlib.h> #include<string.h>
char s[20]; int cal(char *s) { if(!strcmp(s, "zero")) return 0; if(!strcmp(s, "one")) return 1; if(!strcmp(s, "two")) return 2; if(!strcmp(s, "three")) return 3; if(!strcmp(s, "four")) return 4; if(!strcmp(s, "five")) return 5; if(!strcmp(s, "six")) return 6; if(!strcmp(s, "seven")) return 7; if(!strcmp(s, "eight")) return 8; if(!strcmp(s, "nine")) return 9; }
int main() { int a, b; while(1) { a = b = 0; while(~scanf("%s", s), s[0] != '+') { a = a * 10 + cal(s); } while(scanf("%s", s), s[0] != '=') { b = b * 10 + cal(s); } if(!a && !b) break; printf("%d\n", a + b); } return 0; } 2. 最大连续子序列 最大子段和问题, 纪录最大子段的开始和结束位置
//浙大计算机研究生复试上机考试-2005年 最大连续子序列 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 10010 #define INF 0x3f3f3f3f
int n, a[N];
int main() { int i, mx, s, bg, ed, curb, cure, cnt; while(scanf("%d", &n), n) { mx = -INF; s = bg = ed = curb = cure = cnt = 0; for(i = 0; i < n; ++i) { scanf("%d", &a[i]); if(a[i] < 0) cnt++; if(s + a[i] < 0) { s = 0; curb = cure = i + 1; } else if(s + a[i] > mx) { cure = i; bg = curb; ed = cure; s += a[i]; mx = s; } else { s += a[i]; cure = i; } } if(s > mx) { bg = curb; mx = s; ed = cure; } if(cnt == n) printf("0 %d %d\n", a[0], a[n - 1]); else printf("%d %d %d\n", mx, a[bg], a[ed]); } return 0; } 3. 畅通工程 建邻接矩阵, 已经相连的结点间路径权值为0, 其他所有路径权值为1, 做一遍prim就能得到需要添加的最小边数
//浙大计算机研究生复试上机考试-2005年 畅通工程 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1010 #define INF 0x3f3f3f3f
int n, m, adj[N][N], lowcost[N], closest[N];
void prim(int c[][N]) { bool s[N]; s[1] = true; for(int i = 2; i <= n; ++i) { lowcost[i] = c[1][i]; closest[i] = 1; s[i] = false; } for(int i = 1; i < n; ++i) { int mix = INF; int j = 1; for(int k = 2; k <= n; ++k) if(lowcost[k] < mix && !s[k]) { mix = lowcost[k]; j = k; } s[j] = true; for(int k = 2; k <= n; ++k) if(c[j][k] < lowcost[k] && !s[k]) { lowcost[k] = c[j][k]; closest[k] = j; } } }
int main() { int a, b, i, j, ans; while(scanf("%d", &n), n) { scanf("%d", &m); for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) { if(i == j) adj[i][j] = 0; else adj[i][j] = 1; } } while(m--) { scanf("%d %d", &a, &b); adj[a][b] = adj[b][a] = 0; } prim(adj); ans = 0; for(i = 1; i <= n; ++i) ans += lowcost[i]; printf("%d\n", ans); } return 0; } 4. 开门人和关门人 将时间换算成以秒为单位的, 直接纪录到的最早的和离开的最晚的就行 一开始NC了, 一个变量初始化写错地方了, 还以为是有BT输入, WA了三次... ...- -
//浙大计算机研究生复试上机考试-2005年 开门人和关门人 #include<stdio.h> #include<stdlib.h> #include<string.h>
char s[1001000][30];
int main() { int n, m, i, t1, t2, h1, m1, s1, h2, m2, s2, mi, ma, f1, f2; scanf("%d", &n); while(n--) { scanf("%d", &m); f1 = f2 = 0; mi = 86400; ma = 0; for(i = 0; i < m; ++i) { scanf("%s %d:%d:%d %d:%d:%d", s[i], &h1, &m1, &s1, &h2, &m2, &s2); t1 = h1 * 3600 + m1 * 60 + s1; t2 = h2 * 3600 + m2 * 60 + s2; if(t1 <= mi) { f1 = i; mi = t1; } if(t2 >= ma) { f2 = i; ma = t2; } } printf("%s %s\n", s[f1], s[f2]); } return 0; } 5. 排名 sort就行
//浙大计算机研究生复试上机考试-2005年 排名 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; #define N 1010
struct M { int nn, sco; char id[30]; }p[N];
bool cmp(M a, M b) { if(a.sco != b.sco) return a.sco > b.sco; else return strcmp(a.id, b.id) < 0; }
int n, m, g, q[N];
int main() { int i, j, x; while(scanf("%d", &n), n) { scanf("%d %d", &m, &g); for(i = 0; i < m; ++i) scanf("%d", &q[i]); for(i = 0; i < n; ++i) { scanf("%s %d", p[i].id, &p[i].nn); p[i].sco = 0; for(j = 0; j < p[i].nn; ++j) { scanf("%d", &x); p[i].sco += q[x - 1]; } } sort(p, p + n, cmp); for(i = 0; i < n; ++i) { if(p[i].sco < g) break; } printf("%d\n", i); for(j = 0; j < i; ++j) { printf("%s %d\n", p[j].id, p[j].sco); } } return 0; }
|