|
Posted on 2011-06-20 23:41 Uriel 阅读(690) 评论(0) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
个人感觉2010年的题目比2009年的稍难... ... 都说ACMer做这种复试题应该秒杀... 结果我还是悲剧地各种WA... 代码能力和细心程度都严重不足啊... ... 貌似网上解题报告很多的样子... 还是再贴下自己的吧, 供大家一起学习讨论 1. A+B 一开始是三位三位一读, 一个数读完处理符号, WA三次 后来改成直接两个字符串全读进去再一位位处理就A了... 还是有点莫名
//浙大计算机研究生复试上机考试-2010年 A+B #include<ctype.h> #include<stdio.h> #include<stdlib.h> #include<string.h> #define I __int64
int main() { int i, a, b; char s1[20], s2[20]; while (~scanf("%s %s", s1, s2)) { a = b = 0; for (i = 0; s1[i]; ++i) { if (!isdigit(s1[i])) continue; a = a * 10 + s1[i] - '0'; } if (s1[0] == '-') a *= -1; for (i = 0; s2[i]; ++i) { if (!isdigit(s2[i])) continue; b = b * 10 + s2[i] - '0'; } if (s2[0] == '-') b *= -1; printf("%d\n", a + b); } return 0; } 2. ZOJ问题 水题, 一开始最后的地方没有判'&& n2 > 0', WA一次 题目就是要求满足(n1 * n2 == n3 && n2 > 0) 再加上一个z一个j, z在j前面
//浙大计算机研究生复试上机考试-2010年 ZOJ问题 #include<stdio.h> #include<stdlib.h> #include<string.h>
char s[1010];
int main() { int i, j; int nj, nz, n1, n2, n3; //句中j的个数; z的个数; z左边o的个数; zj之间o的个数; j右边o的个数 bool ok, f; while (~scanf("%s", s)) { if (!strcmp(s, "zoj")) { puts("Accepted"); continue; } f = false; ok = true; nj = nz = 0; for (i = 0; s[i]; ++i) { if (s[i] == 'j') { nj++; f = true; } else if (s[i] == 'z') { nz++; if (f) { ok = false; break; } } } if (nj != 1 || nz != 1) ok = false; if (ok) { n1 = n2 = n3 = 0; for (i = 0; s[i] != 'z'; ++i) n1++; ++i; for (; s[i] != 'j'; ++i) n2++; ++i; for (; s[i]; ++i) n3++; if (n1 * n2 == n3 && n2 > 0) ; else ok = false; } if (ok) puts("Accepted"); else puts("Wrong Answer"); } return 0; } 3. 奥运排序问题 水题, 直接sort就行, 一开始理解错题意了, WA得半死, 网上搜了解题报告才发现最后只有那m个国家参与排序... = = 代码改得又长又挫... ...
//浙大计算机研究生复试上机考试-2010年 奥运排序问题 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std;
struct M { int ng, nm, id, rk, ans; double np, pp; }p[100100], q[100100];
int n, m, id[100100], a[100100];
bool cmp1(M a, M b) { return a.ng > b.ng; }
bool cmp2(M a, M b) { return a.nm > b.nm; }
bool cmp3(M a, M b) { return a.np > b.np; }
bool cmp4(M a, M b) { return a.pp > b.pp; }
int main() { int i, s, x; while(~scanf("%d %d", &n, &m)) { for(i = 0; i < n; ++i) { scanf("%d %d %d", &p[i].ng, &p[i].nm, &s); p[i].np = 1.0 * p[i].ng/(1.0 * s); p[i].pp = 1.0 * p[i].nm/(1.0 * s); p[i].rk = n + 1; p[i].id = i; } for(i = 0; i < m; ++i) { scanf("%d", &a[i]); q[i] = p[a[i]]; } for(i = 0; i < m; ++i) p[i] = q[i]; sort(p, p + m, cmp1); int rank = 1, pos = 0; for(i = 0; i < m; ++i) { if(p[i].ng == p[pos].ng) { if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 1; } } else{ pos = i; rank = pos + 1; if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 1; } } } sort(p, p + m, cmp2); rank = 1, pos = 0; for(i = 0; i < m; ++i) { if(p[i].nm == p[pos].nm) { if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 2; } } else{ pos = i; rank = pos + 1; if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 2; } } } sort(p, p + m, cmp3); rank = 1, pos = 0; for(i = 0; i < m; ++i) { if(p[i].np == p[pos].np) { if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 3; } } else{ pos = i; rank = pos + 1; if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 3; } } } sort(p, p + m, cmp4); rank = 1, pos = 0; for(i = 0; i < m; ++i) { if(p[i].pp == p[pos].pp) { if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 4; } } else{ pos = i; rank = pos + 1; if(p[i].rk > rank) { p[i].rk = rank; p[i].ans = 4; } } } for(i = 0; i < m; ++i){ id[p[i].id] = i; } for(i = 0; i < m; ++i) { printf("%d:%d\n", p[id[a[i]]].rk, p[id[a[i]]].ans); } puts(""); } return 0; } 4. 最短路径问题 无向图最短路问题, 每条路同时还有个费用值, 当有相同长度的最短路时选择总费用最小的 Dijkstra算法稍加改动就行, 这题的trick是有重边, WA了两次搜了解题报告才反应过来, 这种trick在ACM题里应该都不算是什么trick了, 就算没有也应该考虑到... 实在是不应该... ...
//浙大计算机研究生复试上机考试-2010年 最短路径问题 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1010 #define INF 0x3f3f3f3f
int dis[N], cost[N], n, m, len[N][N], val[N][N];
void dij(int v, int a[][N], int b[][N]) { int i, j; bool s[N]; for(i = 1; i <= n; ++i) { dis[i] = a[v][i]; cost[i] = b[v][i]; s[i] = false; } dis[v] = 0; cost[v] = 0; s[v] = true; for(i = 1; i < n; ++i) { int tp = INF, u = v, cst = INF; for(j = 1; j <= n; ++j) { if(!s[j] && (dis[j] < tp || (dis[j] == tp && cost[j] < cst))) { u = j; tp = dis[j]; cst = cost[j]; } } s[u] = true; for(j = 1; j <= n ;++j) { if(!s[j] && (a[u][j] < INF)) { int newdis = dis[u] + a[u][j]; cst = cost[u] + b[u][j]; if(newdis < dis[j] || (newdis == dis[j] && cst < cost[j])) { dis[j] = newdis; cost[j] = cst; } } } } return; }
int main() { int i, j, a, b, d, p, s, t; while(scanf("%d %d", &n, &m), n | m) { for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) { val[i][j] = val[j][i] = INF; len[i][j] = len[j][i] = INF; } val[i][i] = len[i][i] = 0; } for(i = 0; i < m; ++i) { scanf("%d %d %d %d", &a, &b, &d, &p); if(len[a][b] > d) { len[a][b] = len[b][a] = d; val[a][b] = val[b][a] = p; } } scanf("%d %d", &s, &t); dij(s, len, val); printf("%d %d\n", dis[t], cost[t]); } return 0; } 2011.09.10 PS: 九度上上述代码WA... 判重边那里要改一下...
int main() { int i, j, a, b, d, p, s, t; while(scanf("%d %d", &n, &m), n | m) { for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) { val[i][j] = val[j][i] = INF; len[i][j] = len[j][i] = INF; } val[i][i] = len[i][i] = 0; } for(i = 0; i < m; ++i) { scanf("%d %d %d %d", &a, &b, &d, &p); if(len[a][b] >= d) { len[a][b] = len[b][a] = d; if(val[a][b] > p)val[a][b] = val[b][a] = p; } } scanf("%d %d", &s, &t); dij(s, len, val); printf("%d %d\n", dis[t], cost[t]); } return 0; } 5. 二叉搜索树 唉... 复旦省赛就挂在BST上, 做这题大水BST还WA两次... ...最后比较每个结点的时候忘记比较根结点了...@_@ 我的方法是先建树, 然后模板树和待匹配树同时BFS, 遇到不同的结点马上返回-1, 表示生成的两棵BST不同, 数组下标弄得很恶心, 自己查了半天... 后来看了下, 网上很多大牛都是建树之后做先序遍历和后序遍历, 因为这样两次遍历之后就能唯一确定一棵树, 代码比我的方法的好看 2011.09.01 PS: 先序遍历和后序遍历不是不能唯一确定一棵二叉树的么。。 看到一位大牛的方法不错 http://www.pyoung.net/?p=954, 照这个方法又做了一遍, 直接用数组存最后strcmp就行, 很方便~ 见第二份代码 方法一: 我的挫方法
//浙大计算机研究生复试上机考试-2010年 二叉搜索树 #include<stdio.h> #include<stdlib.h> #include<string.h>
struct node{ int id, l, r; }p[2][30];
int n, np[2], que[2][1000]; char s[15];
void init(int tr) { int i; for(i = 0; i < 30; ++i) { p[tr][i].l = p[tr][i].r = -1; } }
void insert(int tr, int t, int x, int id) { if(x > p[tr][t].id) { if(p[tr][t].r == -1) { p[tr][t].r = id; p[tr][id].id = x; p[tr][id].l = p[tr][id].r = -1; } else insert(tr, p[tr][t].r, x, id); } else { if(p[tr][t].l == -1) { p[tr][t].l = id; p[tr][id].id = x; p[tr][id].l = p[tr][id].r = -1; } else insert(tr, p[tr][t].l, x, id); } }
int BFS() { int l = 0, r = 1; que[0][0] = que[1][0] = 0; while(l < r) { if(~p[0][que[0][l]].l && p[1][que[1][l]].l == -1) return -1; if(p[0][que[0][l]].l == -1 && ~p[1][que[1][l]].l) return -1; if(~p[0][que[0][l]].r && p[1][que[1][l]].r == -1) return -1; if(p[0][que[0][l]].r == -1 && ~p[1][que[1][l]].r) return -1; if(~p[0][que[0][l]].l) { if(p[1][p[1][que[1][l]].l].id != p[0][p[0][que[0][l]].l].id) return -1; que[1][r] = p[1][que[1][l]].l; que[0][r] = p[0][que[0][l]].l; ++r; } if(~p[0][que[0][l]].r) { if(p[1][p[1][que[1][l]].r].id != p[0][p[0][que[0][l]].r].id) return -1; que[1][r] = p[1][que[1][l]].r; que[0][r] = p[0][que[0][l]].r; ++r; } ++l; } return 0; }
int main() { int i; while(scanf("%d", &n), n) { scanf("%s", s); init(0); np[0] = np[1] = strlen(s); p[0][0].id = s[0] - '0'; p[0][0].l =p[0][0].r = -1; for(i = 1; s[i]; ++i) { insert(0, 0, s[i] - '0', i); } while(n--) { scanf("%s", s); init(1); p[1][0].id = s[0] - '0'; p[1][0].l =p[1][0].r = -1; for(i = 1; s[i]; ++i) { insert(1, 0, s[i] - '0', i); } if(~BFS()) puts("YES"); else puts("NO"); } } return 0; } 方法二:
//2010年浙江大学计算机及软件工程研究生机试题 二叉搜索树
#include<stdio.h> #include<stdlib.h> #include<string.h> #define N 2050
int n; char s1[N], s2[N];
void insert(char *s, char c, int t) { if(s[t] == ' ') s[t] = c; else { if(s[t] > c) insert(s, c, 2 * t); else insert(s, c, 2 * t + 1); } }
int main() { int i; char s[30]; while(scanf("%d", &n), n) { memset(s1, ' ', sizeof(s1)); scanf("%s", s); for(i = 0; s[i]; ++i) { insert(s1, s[i], 1); } while(n--) { memset(s2, ' ', sizeof(s2)); scanf("%s", s); for(i = 0; s[i]; ++i) { insert(s2, s[i], 1); } if(strcmp(s1, s2)) puts("NO"); else puts("YES"); } } return 0; }
|