|
|
Posted on 2011-06-20 23:41 Uriel 阅读(713) 评论(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;
}
|