Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
    大概是时间比较久远的缘故吧, 这套题目很水

1. A + B
    拿到题目直接看了下sample, 小惊吓了一下, 仔细一看发现原来只是吓吓人的玩意, 一位一位的判断是哪个数字就行
//浙大计算机研究生复试上机考试-2005年  A + B
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

char s[20];
 
int cal(char *s) {
    
if(!strcmp(s, "zero")) return 0;
    
if(!strcmp(s, "one")) return 1;
    
if(!strcmp(s, "two")) return 2;
    
if(!strcmp(s, "three")) return 3;
    
if(!strcmp(s, "four")) return 4;
    
if(!strcmp(s, "five")) return 5;
    
if(!strcmp(s, "six")) return 6;
    
if(!strcmp(s, "seven")) return 7;
    
if(!strcmp(s, "eight")) return 8;
    
if(!strcmp(s, "nine")) return 9;
}


int main() {
    
int a, b;
    
while(1{
        a 
= b = 0;
        
while(~scanf("%s", s), s[0!= '+'{
            a 
= a * 10 + cal(s);
        }

        
while(scanf("%s", s), s[0!= '='{
            b 
= b * 10 + cal(s);
        }

        
if(!&& !b) break;
        printf(
"%d\n", a + b);
    }

    
return 0;
}


2. 最大连续子序列
    最大子段和问题, 纪录最大子段的开始和结束位置
//浙大计算机研究生复试上机考试-2005年  最大连续子序列 
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define N 10010
#define INF 0x3f3f3f3f

int n, a[N];

int main() {
    
int i, mx, s, bg, ed, curb, cure, cnt;
    
while(scanf("%d"&n), n) {
        mx 
= -INF; s = bg = ed = curb = cure = cnt = 0;
        
for(i = 0; i < n; ++i) {
            scanf(
"%d"&a[i]);
            
if(a[i] < 0) cnt++;
            
if(s + a[i] < 0{
                s 
= 0;
                curb 
= cure = i + 1;
            }

            
else if(s + a[i] > mx) {
                cure 
= i;
                bg 
= curb;
                ed 
= cure;
                s 
+= a[i];
                mx 
= s;
            }

            
else {
                s 
+= a[i];
                cure 
= i;
            }

        }

        
if(s > mx) {
            bg 
= curb;
            mx 
= s;
            ed 
= cure;
        }

        
if(cnt == n) printf("0 %d %d\n", a[0], a[n - 1]);
        
else
            printf(
"%d %d %d\n", mx, a[bg], a[ed]); 
    }

    
return 0;
}


3. 畅通工程
    建邻接矩阵, 已经相连的结点间路径权值为0, 其他所有路径权值为1, 做一遍prim就能得到需要添加的最小边数
//浙大计算机研究生复试上机考试-2005年  畅通工程
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#define N 1010
#define INF 0x3f3f3f3f

int n, m, 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;
        
int 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 a, b, i, j, ans;
    
while(scanf("%d"&n), n) {
        scanf(
"%d"&m);
        
for(i = 1; i <= n; ++i) {
            
for(j = 1; j <= n; ++j) {
                
if(i == j) adj[i][j] = 0;
                
else
                    adj[i][j] 
= 1;
            }

        }

        
while(m--{
            scanf(
"%d %d"&a, &b);
            adj[a][b] 
= adj[b][a] = 0;
        }

        prim(adj);
        ans 
= 0;
        
for(i = 1; i <= n; ++i) ans += lowcost[i];
        printf(
"%d\n", ans);
    }

    
return 0;
}


4. 开门人和关门人
    将时间换算成以秒为单位的, 直接纪录到的最早的和离开的最晚的就行
    一开始NC了, 一个变量初始化写错地方了, 还以为是有BT输入, WA了三次... ...- -
//浙大计算机研究生复试上机考试-2005年  开门人和关门人 
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

char s[1001000][30];

int main() {
    
int n, m, i, t1, t2, h1, m1, s1, h2, m2, s2, mi, ma, f1, f2;
    scanf(
"%d"&n);
    
while(n--{
        scanf(
"%d"&m);
        f1 
= f2 = 0; mi = 86400; ma = 0;
        
for(i = 0; i < m; ++i) {
            scanf(
"%s %d:%d:%d %d:%d:%d", s[i], &h1, &m1, &s1, &h2, &m2, &s2);
            t1 
= h1 * 3600 + m1 * 60 + s1;
            t2 
= h2 * 3600 + m2 * 60 + s2;
            
if(t1 <= mi) {
                f1 
= i;
                mi 
= t1;
            }

            
if(t2 >= ma) {
                f2 
= i;
                ma 
= t2;
            }

        }

        printf(
"%s %s\n", s[f1], s[f2]);
    }

    
return 0;
}


5. 排名
   sort就行
//浙大计算机研究生复试上机考试-2005年  排名
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;
#define N 1010

struct M {
    
int nn, sco;
    
char id[30];
}
p[N];

bool cmp(M a, M b) {
    
if(a.sco != b.sco) return a.sco > b.sco;
    
else
        
return strcmp(a.id, b.id) < 0;
}


int n, m, g, q[N];

int main() {
    
int i, j, x;
    
while(scanf("%d"&n), n) {
        scanf(
"%d %d"&m, &g);
        
for(i = 0; i < m; ++i) scanf("%d"&q[i]);
        
for(i = 0; i < n; ++i) {
            scanf(
"%s %d", p[i].id, &p[i].nn);
            p[i].sco 
= 0;
            
for(j = 0; j < p[i].nn; ++j) {
                scanf(
"%d"&x);
                p[i].sco 
+= q[x - 1];
            }

        }

        sort(p, p 
+ n, cmp);
        
for(i = 0; i < n; ++i) {
            
if(p[i].sco < g) break;
        }

        printf(
"%d\n", i);
        
for(j = 0; j < i; ++j) {
            printf(
"%s %d\n", p[j].id, p[j].sco);
        }

    }

    
return 0;
}

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