Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
    最近各种悲剧, 5门专必木有哪门考得好的, 嵌入式估计年级垫底了要; 软工的大作业被老师批了, 60%的总评分数估计很难看了要; 系统结构的BT卷子就不多说了; OS成绩一般般; 网络还没出来, 不过填空选择各种概念混淆... ...估计保研是彻底没戏了....T_T 
    夏令营最后只投了SJTU一个, 不过我们这种非985的二流学校应该也没戏的吧... ...要不干脆暑假回家复习考研去算了.

    前段时间各种复习考试, 然后赶软工大作业, 然后临时抱佛脚下六级, 现在还拖着软件课程设计没做完...好久不切题, Baidu, TCO2011和GCJ什么的基本一两轮之后就都挂了... ...前几天听某同学在讨论复试上机神马的, 据鲸鱼队长说ACMers做那个没问题? 于是无聊去HDOJ切了套ZJU的复试题, 各种不给力啊, 代码能力下降得一塌糊涂...

随便贴下代码, 研友神马的欢迎一起交流啊~

1. xxx定律
    大水题
//浙大计算机研究生复试上机考试-2009年 xxx定律
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

int n, step;

int main() {
    
while (scanf("%d"&n), n) {
        step 
= 0;
        
while (n != 1{
            
if (n & 1{
                n 
= 3 * n + 1;
                n 
>>= 1;
            }
 else {
                n 
>>= 1;
            }

            step
++;
        }

        printf(
"%d\n", step);
    }

    
return 0;
}


2. ZOJ
    继续大水题
//浙大计算机研究生复试上机考试-2009年 ZOJ
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

int f[3];
char s[200];

int main() {
    
int i;
    
while (scanf("%s", s), s[0!= 'E'{
        f[
0= f[1= f[2= 0;
        
for (i = 0; s[i]; ++i) {
            
if (s[i] == 'Z')
                f[
0]++;
            
else if (s[i] == 'O')
                f[
1]++;
            
else
                f[
2]++;
        }

        
while (!(!f[0&& !f[1&& !f[2])) {
            
if (f[0]) {
                putchar(
'Z');
                f[
0]--;
            }

            
if (f[1]) {
                putchar(
'O');
                f[
1]--;
            }

            
if (f[2]) {
                putchar(
'J');
                f[
2]--;
            }

        }

        puts(
"");
    }

    
return 0;
}


3. 继续xxx定律
    水题, 直接判, 一开始没读懂题... 发现中文题没比英文题好读多少... 囧rz
//浙大计算机研究生复试上机考试-2009年 继续xxx定律
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;
#define N 5500

int n, a[N], ans[N], flg[100 * N];

int main() {
    
int i;
    
while (scanf("%d"&n), n) {
        memset(flg, 
-1sizeof(flg));
        
for (i = 0; i < n; ++i) {
            scanf(
"%d"&a[i]);
            
if (flg[a[i]] == -1)
                flg[a[i]] 
= 1;
            
int tp = a[i];
            
while (tp != 1{
                
if (tp & 1{
                    tp 
= 3 * tp + 1;
                    tp 
>>= 1;
                }
 else {
                    tp 
>>= 1;
                }

                flg[tp] 
= 0;
            }

        }

        
bool ft = false;
        
for (i = n - 1; i >= 0--i) {
            
if (flg[a[i]] == 1{
                
if (!ft)
                    printf(
"%d", a[i]);
                
else
                    printf(
" %d", a[i]);
                ft 
= true;
            }

        }

        puts(
"");
    }

    
return 0;
}


4. 寻找大富翁
    还是大水题, sort就行
//浙大计算机研究生复试上机考试-2009年 寻找大富翁
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;

int n, m, p[100010];

int main() {
    
int i;
    
while (scanf("%d %d"&n, &m), n | m) {
        
for (i = 0; i < n; ++i) {
            scanf(
"%d"&p[i]);
        }

        sort(p, p 
+ n);
        m 
= min(n, m);
        
for (i = n - 1; i > n - m; --i)
            printf(
"%d ", p[i]);
        printf(
"%d\n", p[n - m]);
    }

    
return 0;
}


5. 找出直系亲属
    写挫了, 写了好久啊, 先根据所给关系建树, 我这里建的跟一般想法的树不同, 我是从儿子指向父母结点的, 因为倒过来的话一个结点会有两个父亲结点, 感觉不太正常. 建完树, 根据每个询问, 分别以两个结点往下BFS, 若能搜到另一个结点, 则他们之间存在直系亲属关系, 否则就没有. 记录下一个结点多少步能搜到另一个结点, 处理下输出
     freopen之类的SB错误几次才过...= =
//浙大计算机研究生复试上机考试-2009年 找出直系亲属
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

struct node {
    
int id, ns;
    
int pt[30];
}
 p[30];

int n, m, np, id[30], flg[30], step, q[1000][2];
bool ok;

int BFS(int idx, int idy) {
    
int i, l = 0, r = 1;
    q[
0][0= idx;
    q[
0][1= 0;
    
while (l < r) {
        
for (i = 0; i < p[q[l][0]].ns; ++i) {
            
if (p[q[l][0]].pt[i] == idy) {
                step 
= q[l][1+ 1;
                
return step;
            }

            q[r][
0= p[q[l][0]].pt[i];
            q[r][
1= q[l][1+ 1;
            
++r;
        }

        
++l;
    }

    
return -1;
}


int main() {
    freopen(
"out.txt""w", stdout);
    
int i;
    
char s[10];
    
while (scanf("%d %d"&n, &m), n | m) {
        memset(p, 
0sizeof(p));
        memset(id, 
0sizeof(id));
        memset(flg, 
0sizeof(flg));
        np 
= 0;
        
for (i = 0; i < n; ++i) {
            scanf(
"%s", s);
            
if (!flg[s[0- 'A']) {
                id[s[
0- 'A'= np;
                p[np].id 
= s[0- 'A';
                flg[s[
0- 'A'= 1;
                np
++;
            }

            
int tpid = id[s[0- 'A'];
            
if (s[1!= '-'{
                
if (!flg[s[1- 'A']) {
                    p[np].ns 
= 0;
                    p[np].id 
= s[1- 'A';
                    id[s[
1- 'A'= np;
                    flg[s[
1- 'A'= 1;
                    np
++;
                }

                p[tpid].pt[p[tpid].ns] 
= id[s[1- 'A'];
                p[tpid].ns
++;
            }

            
if (s[2!= '-'{
                
if (!flg[s[2- 'A']) {
                    p[np].ns 
= 0;
                    p[np].id 
= s[2- 'A';
                    id[s[
2- 'A'= np;
                    flg[s[
2- 'A'= 1;
                    np
++;
                }

                p[tpid].pt[p[tpid].ns] 
= id[s[2- 'A'];
                p[tpid].ns
++;
            }

        }

        
while (m--{
            scanf(
"%s", s);
            ok 
= false;
            step 
= 0;
            
if (~BFS(id[s[0- 'A'], id[s[1- 'A'])) {
                
if (step == 1)
                    puts(
"child");
                
else {
                    
while (step > 2{
                        printf(
"great-");
                        step
--;
                    }

                    puts(
"grandchild");
                }

                
continue;
            }

            
if (BFS(id[s[1- 'A'], id[s[0- 'A']) == -1)
                puts(
"-");
            
else {
                
if (step == 1)
                    puts(
"parent");
                
else {
                    
while (step > 2{
                        printf(
"great-");
                        step
--;
                    }

                    puts(
"grandparent");
                }

            }

        }

    }

    
return 0;
}

2011.09.25 PS: 上面的代码太挫了。。处理结点编号根本不用转来转去。。今天又敲了一遍。。竟然直接过sample直接AC。。
//2009年浙江大学计算机及软件工程研究生机试题 找出直系亲属
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

struct node {
    
int ns, pt[30];
}
p[30];

int n, m, stp, q[1000][2];

int BFS(int x, int y) {
    
int l = 0, r = 1, i;
    q[l][
0= x;
    q[l][
1= 0;
    
while(l < r) {
        
int tp = q[l][0];
        
for(i = 0; i < p[tp].ns; ++i) {
            
if(p[tp].pt[i] == y) {
                stp 
= q[l][1+ 1;
                
return 1;
            }

            
else {
                q[r][
0= p[tp].pt[i];
                q[r][
1= q[l][1+ 1;
                
++r;
            }

        }

        
++l;
    }

    
return 0;
}


int main() {
    
int i, j, tp;
    
char s[5];
    
while(scanf("%d %d"&n, &m), n | m) {
        
for(i = 0; i < 26++i) {
            p[i].ns 
= 0;
            
for(j = 0; j < 30++j) p[i].pt[j] = -1;
        }

        
for(i = 0; i < n; ++i) {
            scanf(
"%s", s);
            
if(s[1!= '-'{
                tp 
= s[1- 'A';
                p[tp].pt[p[tp].ns
++= s[0- 'A';
            }

            
if(s[2!= '-'{
                tp 
= s[2- 'A';
                p[tp].pt[p[tp].ns
++= s[0- 'A';
            }

        }

        
while(m--{
            scanf(
"%s", s);
            stp 
= 0;
            
if(BFS(s[0- 'A', s[1- 'A')) {
                
if(stp == 1) puts("parent");
                
else {
                    
for(i = 0; i < stp - 2++i) {
                        printf(
"great-");
                    }

                    puts(
"grandparent");
                }

            }

            
else if(BFS(s[1- 'A', s[0- 'A')) {
                
if(stp == 1) puts("child");
                
else {
                    
for(i = 0; i < stp - 2++i) {
                        printf(
"great-");
                    }

                    puts(
"grandchild");
                }

            }

            
else
                puts(
"-");
        }

    }

    
return 0;
}
 

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