|
Posted on 2011-06-25 23:34 Uriel 阅读(384) 评论(0) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
再做一套玩玩~~
1. 最小长方形 就是分别找到x, y的最小, 最大值, 水题, 不解释
//浙大计算机研究生复试上机考试-2007年 最小长方形 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std;
int mx, my, ax, ay, x, y;
int main() { bool flg = false; while(1) { mx = my = 300; ax = ay = -300; while(scanf("%d %d", &x, &y)) { if(!x && !y && flg) return 0; if(!x && !y) { flg = true; break; } mx = min(mx, x); my = min(my, y); ax = max(ax, x); ay = max(ay, y); flg = false; } printf("%d %d %d %d\n", mx, my, ax, ay); } return 0; }
2. 统计字符 大水, 不解释
//浙大计算机研究生复试上机考试-2007年 统计字符 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std;
int cnt[300]; char s[10], str[100];
int main() { int i; while(gets(s), strcmp(s, "#")) { gets(str); memset(cnt, 0, sizeof(cnt)); for(i = 0; str[i]; ++i) { cnt[str[i]]++; } for(i = 0; s[i]; ++i) { printf("%c %d\n", s[i], cnt[s[i]]); } } return 0; }
3. 游船出租 大水, 不解释
//浙大计算机研究生复试上机考试-2007年 游船出租 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 110
struct boat{ int id, st, tt, bg; }p[N];
int cnt; double ti;
int main() { int id, t, h, m; char op[3]; while(1) { while(scanf("%d", &id)) { if(id == -1) return 0; scanf("%s %d:%d", op, &h, &m); if(!id) break; t = h * 60 + m; if(op[0] == 'S') { if(p[id].st == 1) continue; else { p[id].st = 1; p[id].bg = t; } } else if(op[0] == 'E') { if(!p[id].st) continue; else { p[id].st = 0; ti += t - p[id].bg; cnt++; } } } if(cnt)printf("%d %.0lf\n", cnt, ti / cnt); else puts("0 0"); cnt = 0; ti = 0.0; } return 0; }
4. EXCEL排序 考sort的大水题
//浙大计算机研究生复试上机考试-2007年 EXCEL排序 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; #define N 100010
struct M { int sco; char id[10], name[10]; }p[N];
bool cmp1(M a, M b) { return strcmp(a.id, b.id) < 0; }
bool cmp2(M a, M b) { if(strcmp(a.name, b.name))return strcmp(a.name, b.name) < 0; else return strcmp(a.id, b.id) < 0; }
bool cmp3(M a, M b) { if(a.sco != b.sco)return a.sco < b.sco; else return strcmp(a.id, b.id) < 0; }
int c, n;
int main() { int i, g = 1; while(scanf("%d %d", &n, &c), n | c) { for(i = 0; i < n; ++i) { scanf("%s %s %d", p[i].id, p[i].name, &p[i].sco); } if(c == 1) sort(p, p + n, cmp1); else if(c == 2) sort(p, p + n, cmp2); else if(c == 3) sort(p, p + n, cmp3); printf("Case %d:\n", g++); for(i = 0; i < n; ++i) printf("%s %s %d\n", p[i].id, p[i].name, p[i].sco); } return 0; }
5. 畅通工程 注意重边, 一开始有个地方NC了, 一开始我最后判'?'是算出最小生成树的所有边权值和大于INF就输出'?', 这样有可能每条边其实都没超过INF, 但总和超过了, 被我判成'?', 实际上这种情况是符合要求的. 改为判断每条边都小于INF就过了
//浙大计算机研究生复试上机考试-2007年 畅通工程 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; #define N 110 #define INF 0x3f3f3f3f
int n, m, ans, 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 mi = INF, j = 1; for(int k = 2; k <= n; ++k) if(lowcost[k] < mi && !s[k]) { mi = 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 i, j, a, b, c; while(scanf("%d %d", &m, &n), m) { for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) { if(i == j) adj[i][j] = 0; else adj[i][j] = adj[j][i] = INF; } } for(i = 0; i < m; ++i) { scanf("%d %d %d", &a, &b, &c); adj[a][b] = min(c, adj[a][b]); adj[b][a] = adj[a][b]; } prim(adj); ans = 0; bool ok = true; for(i = 1; i <= n; ++i) { if(lowcost[i] >= INF) { ok = false; break; } ans += lowcost[i]; } if(!ok) puts("?"); else printf("%d\n", ans); } return 0; }
6. 最大报销额 0-1背包, 以物品项数作为dp数组的下标 这题很坑爹, 那个单张发票中A, B, C三种物品以外的物品都不考虑, 而且这三种物品在同一张发票中可能重复出现, 要把它们全加起来, 单张发票的A或者B或者C都不能超过600.0 ... ...因为这个WA到死啊... ...
//浙大计算机研究生复试上机考试-2007年 最大报销额 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 50
struct tic { int nt; double mon; }p[N];
int n, nn, aa, cnt[3]; double q, ans, dp[10100];
void DP() { for(int i = 0; i <= aa; ++i) dp[i] = 0; for(int i = 0; i < nn; ++i) { for(int j = aa; j >= p[i].nt; --j) { double tp = dp[j - p[i].nt] + p[i].mon; if(dp[j] < tp && dp[j - p[i].nt] + p[i].mon <= q) dp[j] = tp; } } }
int main() { int i, j, k; char c[10]; double x, tp, ttp; while(scanf("%lf %d", &q, &n), n) { nn = aa = 0; for(i = 0; i < n; ++i) p[i].mon = 0.0; for(i = 0; i < n; ++i) { scanf("%d", &p[nn].nt); aa += p[nn].nt; bool ok = true; cnt[0] = cnt[1] = cnt[2] = 0; for(j = 0; j < p[nn].nt; ++j) { scanf("%s", c); if(c[0] == 'A' || c[0] == 'B' || c[0] == 'C') { for(k = 0; c[k] != ':'; ++k); for(k++, tp = 0; c[k] != '.'; ++k) tp = tp * 10 + c[k] - '0'; for(ttp = 0, k = strlen(c) - 1; c[k] != '.'; --k) ttp = ttp / 10 + c[k] - '0'; tp += ttp / 10; p[nn].mon += tp; cnt[c[0] - 'A'] += tp; if(cnt[c[0] - 'A'] > 600.0) ok = false; } } if(ok && p[nn].mon <= 1000.0) nn++; } DP(); ans = 0; for(i = 0; i <= aa; ++i) if(ans < dp[i]) ans = dp[i]; printf("%.2lf\n", ans); } return 0; }
发现茫茫多想考研的同学都复习了好多了, 表示还木有开始复习的鸭梨很大... ... 不切水题玩了, 要开始好好复习了!!
|