Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
    发指啊... 第一次快写完了结果傲游挂了... ...直接全部重来啊... ...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[] = {2357111317192329313741434753596167717379838997101103};
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, 
0sizeof(a));
        memset(b, 
0sizeof(b));
        memset(c, 
0sizeof(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 Uriel
@毛
因为最后只剩加减法,加减法是从左到右依次计算,而在进栈时是从左到右进栈的,出栈顺序与入栈相反,直接出栈一个计算一个的话就变成是从右到左计算了,所以倒置一下。。(不过这种做法很挫就是了。。= =)

# re: 浙大计算机研究生复试上机考试-2006年  回复  更多评论   

2012-03-02 14:26 by
哦,想通了。一下子脑子短路了,好笨啊!!!我也想的是这个方法,嘿嘿。可每次提交都是WA,看了帖子才知道错在这了,谢谢~~~

# re: 浙大计算机研究生复试上机考试-2006年  回复  更多评论   

2012-03-02 14:30 by Uriel
@毛
表示我当时debug了半天才发现。。= =
感觉做题之前还是该拿笔算算,想想清楚。。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理