|
|
Posted on 2011-06-23 23:11 Uriel 阅读(378) 评论(0) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
大概是时间比较久远的缘故吧, 这套题目很水 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(!a && !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;
}
|