Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
    个人感觉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 == -1return -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 == -1return -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(
00, 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(
10, 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;
}

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