|
|
Posted on 2011-06-20 23:41 Uriel 閱讀(703) 評論(0) 編輯 收藏 引用 所屬分類: 考研&保研復試上機題
個人感覺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 == -1) return -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 == -1) return -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(0, 0, 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(1, 0, 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;
}
|