|
|
Posted on 2011-06-23 23:11 Uriel 閱讀(408) 評論(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;
}
|