|
|
Posted on 2011-07-01 20:04 Uriel 阅读(396) 评论(0) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
各种悲剧, 深刻感觉到... ... 成绩是王道, 比赛什么的都是浮云... ... 暑假好好啃DS和高数吧... ... 再切套水题放松一下... ... 不过这套比起前面三年的还真不算很水的... ... 貌似现在HDU上的ZJU 2005-2011都切了... ... 1. 又一版 A+B 这个A+B很水啦, 递归输出实现进制转换就行
 //浙大计算机研究生复试上机考试-2008年 又一版 A+B
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define I __int64
int m;
I a, b;
  void print(I x)  {
 if(!x) return;
print(x / m);
printf("%d", x % m);
 }
int main() {
  while(scanf("%d", &m), m) {
scanf("%I64d %I64d", &a, &b);
a += b;
if(!a) printf("0");
else
print(a);
puts("");
 }
return 0;
}2. 欧拉回路 这题只是判欧拉回路是否存在, 不用输出欧拉回路的话就不用那个神奇的套圈法了 根据欧拉回路条件, 首先图要连通(一开始WA了一次忘记这个条件了), 这个嘛, BFS一下就好了, 再判下是否每个结点度数都是偶数
//浙大计算机研究生复试上机考试-2008年 欧拉回路
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1010
int n, m, deg[N], f[N][N], vis[N], q[N * 2];
void BFS() {
int l, r, i;
memset(vis, 0, sizeof(vis));
q[0] = 1; vis[1] = 1;
l = 0, r = 1;
while(l < r) {
for(i = 1; i <= n; ++i) {
if(i != q[l] && !vis[i] && f[i][q[l]]) {
vis[i] = 1;
q[r++] = i;
}
}
++l;
}
}
int main() {
int x, y, i;
while(scanf("%d", &n), n) {
scanf("%d", &m);
memset(deg, 0, sizeof(deg));
memset(f, 0, sizeof(f));
for(i = 0; i < m; ++i) {
scanf("%d %d", &x, &y);
if(!f[x][y]) {
deg[x]++;
deg[y]++;
f[x][y] = f[y][x] = 1;
}
}
BFS();
for(i = 1; i <= n; ++i) {
if(!vis[i] || deg[i] % 2) break;
}
if(i <= n) puts("0");
else
puts("1");
}
return 0;
} 3. 继续畅通工程 继续prim模板题, 不解释
//浙大计算机研究生复试上机考试-2008年 继续畅通工程
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 110
#define INF 0x3f3f3f3f
#define min(x, y) (x < y ? x : y)
int n, ans, 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 mi = INF, j = 1;
for(int k = 2; k <= n; ++k)
if(lowcost[k] < mi && !s[k]) {
mi = 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 i, j, x, y, c, st;
while(scanf("%d", &n), n) {
for(i = 1; i <= n; ++i) {
for(j = 1; j <= n; ++j) {
if(i == j) continue;
else
adj[i][j] = adj[j][i] = INF;
}
}
for(i = 0; i < n * (n - 1) / 2; ++i) {
scanf("%d %d %d %d", &x, &y, &c, &st);
if(!st) {
adj[x][y] = adj[y][x] = min(adj[y][x], c);
}
else
adj[x][y] = adj[y][x] = 0;
}
prim(adj);
ans = 0;
for(i = 1; i <= n; ++i) {
ans += lowcost[i];
}
printf("%d\n", ans);
}
return 0;
} 4. 魔咒词典 5000Ms的时限, 果断水过去了... ... 2011.09.17 PS: 坑爹啊... 九度怎么都AC不能...
//浙大计算机研究生复试上机考试-2008年 魔咒词典
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100010
#define Q 1010
struct M {
int mk, id, ans;
char name[25], s[100];
}p[N], q[N];
bool cmp1(M a, M b) {
return strcmp(a.name, b.name) < 0;
}
bool cmp2(M a, M b) {
return strcmp(a.s, b.s) < 0;
}
int nq, id[Q];
int main() {
int i, j, n = 0, pos1, pos2;
char s[110];
while(gets(s), strcmp(s, "@END@")) {
for(i = 0; s[i] != '['; ++i);
for(j = ++i; s[j] != ']'; ++j);
strncpy(p[n].name, &s[i], j - i);
strncpy(q[n].name, &s[i], j - i);
strcpy(p[n].s, &s[j + 2]);
strcpy(q[n].s, &s[j + 2]);
++n;
}
sort(p, p + n, cmp1);
sort(q, q + n, cmp2);
scanf("%d", &nq);
getchar();
for(i = 0; i < nq; ++i) {
gets(s);
if(s[0] == '[') {
s[strlen(s) - 1] = '\0';
for(j = 0; j < n; ++j) {
if(!strcmp(p[j].name, &s[1])) {
puts(p[j].s);
break;
}
}
if(j == n) puts("what?");
}
else {
for(j = 0; j < n; ++j) {
if(!strcmp(q[j].s, s)) {
puts(q[j].name);
break;
}
}
if(j == n) puts("what?");
}
}
return 0;
} 5. 毕业bg 简单DP, 好久不写DP, 一点感觉都没有了... ... 还看了一下解题报告才搞出sample, dp数组NC开小了还WA了一次... ...
//浙大计算机研究生复试上机考试-2008年 毕业bg
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 35
struct M {
int h, l, t;
}p[N];
bool cmp(M a, M b) {
if(a.t != b.t) return a.t < b.t;
return a.h < b.h;
}
int n, mxt, dp[1010];
int main() {
int i, j;
while(scanf("%d", &n), n > 0) {
mxt = 0;
memset(dp, 0, sizeof(dp));
for(i = 1; i <= n; ++i) {
scanf("%d %d %d", &p[i].h, &p[i].l, &p[i].t);
mxt = max(p[i].t, mxt);
}
sort(p + 1, p + n + 1, cmp);
for(i = 1; i <= n; ++i) {
for(j = p[i].t; j >= p[i].l; --j)
dp[j] = max(dp[j - p[i].l] + p[i].h, dp[j]);
for(j = p[i].t + 1; j <= mxt; ++j)
dp[j] = max(dp[j], dp[j - 1]);
}
printf("%d\n", dp[mxt]);
}
return 0;
}
|