|
Posted on 2011-06-24 23:47 Uriel 阅读(563) 评论(4) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
发指啊... 第一次快写完了结果傲游挂了... ...直接全部重来啊... ...OMG 这套比2005年的稍难, 不过基本都是小模拟啦, 对ACM菜鸟来说都是大水题~~ 1. 还是A+B 注意题目第三个case, 8的前面全当成0, 所以108和8的前两位看作相同的 我的方法很WS, 因为题目说不超过8位, 就先把不足8位的数字串补足8位, 高位全填0, 然后从后面开始比较k位就ok了~
//浙大计算机研究生复试上机考试-2006年 还是A+B #include<stdio.h> #include<stdlib.h> #include<string.h>
int k, s1, s2, l1, l2; char a[10], b[10];
int cal(char *s) { int i, t = 0; for(i = 0; s[i]; ++i) t = t * 10 + s[i] - '0'; return t; }
int main() { int i; while(1) { scanf("%s %s %d", a, b, &k); if(!strcmp(a, "0") && !strcmp(b, "0")) break; l1 = strlen(a); l2 = strlen(b); for(i = 7; i > 7 - l1; --i) a[i] = a[l1 + i - 8]; for(i = 0; i <= 7 - l1; ++i) a[i] = '0'; for(i = 7; i > 7 - l2; --i) b[i] = b[l2 + i - 8]; for(i = 0; i <= 7 - l2; ++i) b[i] = '0'; if(!strncmp(a + 8 - k,b + 8 - k, k)) { puts("-1"); continue; } s1 = cal(a); s2 = cal(b); printf("%d\n", s1 + s2); } return 0; } 2. 火星A+B 一开始理解错题意了, 不过应该不会有人跟我有一样NC的理解吧... = = ...就不说了 有点像高精度加法, 一位位加就好了, 注意进制, 先打出100以内的质数表(保险起见多打了两个) 开始一处初始化忘了, WA三次才发现... ... PS: Discuss惊现ECUST-SJTU---ssjia大牛, 各种Orz 2011.09.17 PS: 这题九度上死活过不了啊... 求交流
//浙大计算机研究生复试上机考试-2006年 火星A+B #include<ctype.h> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std;
int bas[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}; int a[30], b[30], c[30], l1, l2; char s1[300], s2[300];
int main() { int i, tn1, tn2, tp; while(1) { scanf("%s %s", s1, s2); if(!strcmp(s1, "0") && !strcmp(s2, "0")) break; l1 = strlen(s1); l2 = strlen(s2); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); tn1 = tn2 = 0; tp = 1; for(i = l1 - 1; i >= 0; --i) { if(s1[i] == ',') { tn1++; tp = 1; } else if(isdigit(s1[i])) { a[tn1] = a[tn1] + tp * (s1[i] - '0'); tp *= 10; } } tp = 1; for(i = l2 - 1; i >= 0; --i) { if(s2[i] == ',') { tn2++; tp = 1; } else if(isdigit(s2[i])) { b[tn2] = b[tn2] + tp * (s2[i] - '0'); tp *= 10; } } int cf = 0; for(i = 0; i <= min(tn1, tn2); ++i) { c[i] = cf + a[i] + b[i]; if(c[i] >= bas[i]) { cf = c[i] / bas[i]; c[i] %= bas[i]; } else cf = 0; } for(;i <= max(tn1, tn2); ++i) { if(i <= tn1) { c[i] = cf + a[i]; if(c[i] >= bas[i]) { cf = c[i] / bas[i]; c[i] %= bas[i]; } else cf = 0; } else if(i <= tn2) { c[i] = cf + b[i]; if(c[i] >= bas[i]) { cf = c[i] / bas[i]; c[i] %= bas[i]; } else cf = 0; } } c[i] += cf; if(c[i] >= bas[i]) { cf = c[i] / bas[i]; c[i] %= bas[i]; } else cf = 0; if(cf) c[++i] = cf; while(c[i] == 0 && i > 0) --i; for(; i > 0; --i) printf("%d,", c[i]); printf("%d\n", c[0]); } return 0; }
3. 还是畅通工程 模板题, 不解释
//浙大计算机研究生复试上机考试-2006年 还是畅通工程 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 110 #define INF 0x3f3f3f3f
int n, 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, 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 i, j, ans, a, b, c; while(scanf("%d", &n), n) { for(i = 1; i <= n * (n - 1) / 2; ++i) { scanf("%d %d %d", &a, &b, &c); adj[a][b] = adj[b][a] = c; } prim(adj); ans = 0; for(i = 1; i <= n; ++i) ans += lowcost[i]; printf("%d\n", ans); } return 0; }
4. 统计同成绩学生人数 大水题, 不解释
//浙大计算机研究生复试上机考试-2006年 统计同成绩学生人数 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1010
int a[N], n, ans;
int main() { int x, i; while(scanf("%d", &n), n) { for(i = 0; i < n; ++i) scanf("%d", &a[i]); scanf("%d", &x); ans = 0; for(i = 0; i < n; ++i) if(a[i] == x) ans++; printf("%d\n", ans); } return 0; }
5. 简单计算器 我的方法比较麻烦... ...设置两个栈(偷懒用了STL, 慢就慢吧...||), 一个符号栈, 一个操作数栈 当读进操作数时, 若符号栈栈顶为*或/, 就马上计算掉, 弹出操作数栈栈顶连续两个元素和符号栈栈顶, 算好之后结果压进操作数栈, 这里注意下运算顺序, '-','/'都是有计算顺序要求的 当读到运算符时, 什么都不管, 直接压进符号栈 最后把操作数栈和符号栈元素全部倒置(稍微想想就知道为什么了, 一开始这里没想清楚, 单步了好一会儿才发现... ...), 然后不断弹出符号栈栈顶符号和操作数栈顶连续两个操作数, 计算完后结果压入操作数栈, 直至符号栈为空.
//浙大计算机研究生复试上机考试-2006年 简单计算器 #include<stack> #include<ctype.h> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std;
double cal(double a, double b, char c) { if(c == '+') return a + b; if(c == '-') return a - b; if(c == '*') return a * b; if(c == '/') return a / b; }
int main() { int i; char op[210]; while(gets(op), strcmp(op, "0") != 0) { i = 0; stack<double> opa; stack<char> opr; while(op[i]) { if(isdigit(op[i])) { double tp = 0.0; while(isdigit(op[i])) { tp = tp * 10 + op[i] - '0'; ++i; } opa.push(tp); if(!opr.empty() && opr.top() == '*') { opr.pop(); double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '*')); } else if(!opr.empty() && opr.top() == '/') { opr.pop(); double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '/')); } } else if(op[i] == '+') { opr.push('+'); ++i; } else if(op[i] == '-') { opr.push('-'); ++i; } else if(op[i] == '*') { opr.push('*'); ++i; } else if(op[i] == '/') { opr.push('/'); ++i; } else ++i; } stack<char>opr1; stack<double>opa1; while(!opr.empty()) { opr1.push(opr.top()); opr.pop(); } while(!opa.empty()) { opa1.push(opa.top()); opa.pop(); } while(!opr1.empty()) { double t1 = opa1.top(); opa1.pop(); double t2 = opa1.top(); opa1.pop(); opa1.push(cal(t1, t2, opr1.top())); opr1.pop(); } printf("%.2lf\n", opa1.top()); } return 0; }
2011.09.10 PS: 这题又用了另一种方法做 遇到数字的时候不处理, 直接压入操作数栈, 遇到'*'或'/'时, 操作符栈顶连续的'*'或'/'都计算掉, 再将自己压入操作符栈, 遇到'+'或'-'时, 操作符栈里的都能计算掉, 计算完后再将自己压入操作符栈, 最后将操作符栈从栈顶依次处理即可, 因为此时不会出现多个'+''-', '*''/'相连导致运算顺序错误的情况 本来以为这样很方便, 结果代码比原来长了快一倍... (因为写得挫... ) 其实像书上那样加入结束字符再处理的话代码应该会短一些... 有空再敲一次
//2006年浙江大学计算机及软件工程研究生机试题 简单计算器 #include<ctype.h> #include<stack> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std;
double cal(double a, double b, char c) { if(c == '+') return a + b; if(c == '-') return a - b; if(c == '*') return a * b; if(c == '/') return a / b; }
int main() { int i; char op[220]; while(gets(op), strcmp(op, "0")) { i = 0; stack<double> opa; stack<char> opr; while(op[i]) { if(isdigit(op[i])) { double tp = 0.0; while(isdigit(op[i])) { tp = tp * 10 + op[i] - '0'; ++i; } opa.push(tp); } else if(op[i] == '+') { if(opr.empty()) opr.push('+'); else { while(!opr.empty()) { if(opr.top() == '+') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opr.pop(); opa.push(cal(t2, t1, '+')); } else if(opr.top() == '-') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '-')); opr.pop(); } else if(opr.top() == '*') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '*')); opr.pop(); } else if(opr.top() == '/') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '/')); opr.pop(); } } opr.push('+'); } ++i; } else if(op[i] == '-') { if(opr.empty()) opr.push('-'); else { while(!opr.empty()) { if(opr.top() == '-') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '-')); opr.pop(); } else if(opr.top() == '+') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '+')); opr.pop(); } else if(opr.top() == '*') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '*')); opr.pop(); } else if(opr.top() == '/') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '/')); opr.pop(); } } opr.push('-'); } ++i; } else if(op[i] == '*') { if(opr.empty()) opr.push('*'); else { while(!opr.empty()) { if(opr.top() == '*') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '*')); opr.pop(); } else if(opr.top() == '/') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '/')); opr.pop(); } else break; } opr.push('*'); } ++i; } else if(op[i] == '/') { if(opr.empty()) opr.push('/'); else { while(!opr.empty()) { if(opr.top() == '/') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '/')); opr.pop(); } else if(opr.top() == '*') { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, '*')); opr.pop(); } else break; } opr.push('/'); } ++i; } else ++i; } while(!opr.empty()) { double t1 = opa.top(); opa.pop(); double t2 = opa.top(); opa.pop(); opa.push(cal(t2, t1, opr.top())); opr.pop(); } printf("%.2lf\n", opa.top()); } return 0; }
Feedback
# re: 浙大计算机研究生复试上机考试-2006年 回复 更多评论
2012-03-02 10:49 by
最后把操作数栈和符号栈元素全部倒置(稍微想想就知道为什么了, 一开始这里没想清楚, 单步了好一会儿才发现... ...), 为什么啊?还是没想明白,盼能解答
# re: 浙大计算机研究生复试上机考试-2006年 回复 更多评论
2012-03-02 14:16 by
@毛 因为最后只剩加减法,加减法是从左到右依次计算,而在进栈时是从左到右进栈的,出栈顺序与入栈相反,直接出栈一个计算一个的话就变成是从右到左计算了,所以倒置一下。。(不过这种做法很挫就是了。。= =)
# re: 浙大计算机研究生复试上机考试-2006年 回复 更多评论
2012-03-02 14:26 by
哦,想通了。一下子脑子短路了,好笨啊!!!我也想的是这个方法,嘿嘿。可每次提交都是WA,看了帖子才知道错在这了,谢谢~~~
# re: 浙大计算机研究生复试上机考试-2006年 回复 更多评论
2012-03-02 14:30 by
@毛 表示我当时debug了半天才发现。。= = 感觉做题之前还是该拿笔算算,想想清楚。。
|