|
|
Posted on 2011-06-24 23:47 Uriel 阅读(592) 评论(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了半天才发现。。= =
感觉做题之前还是该拿笔算算，想想清楚。。
|