|
|
Posted on 2011-06-19 23:26 Uriel 阅读(572) 评论(0) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
最近各种悲剧, 5门专必木有哪门考得好的, 嵌入式估计年级垫底了要; 软工的大作业被老师批了, 60%的总评分数估计很难看了要; 系统结构的BT卷子就不多说了; OS成绩一般般; 网络还没出来, 不过填空选择各种概念混淆... ...估计保研是彻底没戏了....T_T 夏令营最后只投了SJTU一个, 不过我们这种非985的二流学校应该也没戏的吧... ...要不干脆暑假回家复习考研去算了. 前段时间各种复习考试, 然后赶软工大作业, 然后临时抱佛脚下六级, 现在还拖着软件课程设计没做完...好久不切题, Baidu, TCO2011和GCJ什么的基本一两轮之后就都挂了... ...前几天听某同学在讨论复试上机神马的, 据鲸鱼队长说ACMers做那个没问题? 于是无聊去HDOJ切了套ZJU的复试题, 各种不给力啊, 代码能力下降得一塌糊涂... 随便贴下代码, 研友神马的欢迎一起交流啊~ 1. xxx定律 大水题
 //浙大计算机研究生复试上机考试-2009年 xxx定律
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n, step;
  int main()  {
  while (scanf("%d", &n), n) {
 step = 0;
while (n != 1) {
if (n & 1) {
n = 3 * n + 1;
n >>= 1;
} else {
n >>= 1;
 }
step++;
}
printf("%d\n", step);
}
return 0;
 }2. ZOJ 继续大水题
//浙大计算机研究生复试上机考试-2009年 ZOJ
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int f[3];
char s[200];
int main() {
int i;
while (scanf("%s", s), s[0] != 'E') {
f[0] = f[1] = f[2] = 0;
for (i = 0; s[i]; ++i) {
if (s[i] == 'Z')
f[0]++;
else if (s[i] == 'O')
f[1]++;
else
f[2]++;
}
while (!(!f[0] && !f[1] && !f[2])) {
if (f[0]) {
putchar('Z');
f[0]--;
}
if (f[1]) {
putchar('O');
f[1]--;
}
if (f[2]) {
putchar('J');
f[2]--;
}
}
puts("");
}
return 0;
} 3. 继续xxx定律 水题, 直接判, 一开始没读懂题... 发现中文题没比英文题好读多少... 囧rz
//浙大计算机研究生复试上机考试-2009年 继续xxx定律
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 5500
int n, a[N], ans[N], flg[100 * N];
int main() {
int i;
while (scanf("%d", &n), n) {
memset(flg, -1, sizeof(flg));
for (i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if (flg[a[i]] == -1)
flg[a[i]] = 1;
int tp = a[i];
while (tp != 1) {
if (tp & 1) {
tp = 3 * tp + 1;
tp >>= 1;
} else {
tp >>= 1;
}
flg[tp] = 0;
}
}
bool ft = false;
for (i = n - 1; i >= 0; --i) {
if (flg[a[i]] == 1) {
if (!ft)
printf("%d", a[i]);
else
printf(" %d", a[i]);
ft = true;
}
}
puts("");
}
return 0;
} 4. 寻找大富翁 还是大水题, sort就行
//浙大计算机研究生复试上机考试-2009年 寻找大富翁
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n, m, p[100010];
int main() {
int i;
while (scanf("%d %d", &n, &m), n | m) {
for (i = 0; i < n; ++i) {
scanf("%d", &p[i]);
}
sort(p, p + n);
m = min(n, m);
for (i = n - 1; i > n - m; --i)
printf("%d ", p[i]);
printf("%d\n", p[n - m]);
}
return 0;
} 5. 找出直系亲属 写挫了, 写了好久啊, 先根据所给关系建树, 我这里建的跟一般想法的树不同, 我是从儿子指向父母结点的, 因为倒过来的话一个结点会有两个父亲结点, 感觉不太正常. 建完树, 根据每个询问, 分别以两个结点往下BFS, 若能搜到另一个结点, 则他们之间存在直系亲属关系, 否则就没有. 记录下一个结点多少步能搜到另一个结点, 处理下输出 freopen之类的SB错误几次才过...= =
//浙大计算机研究生复试上机考试-2009年 找出直系亲属
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node {
int id, ns;
int pt[30];
} p[30];
int n, m, np, id[30], flg[30], step, q[1000][2];
bool ok;
int BFS(int idx, int idy) {
int i, l = 0, r = 1;
q[0][0] = idx;
q[0][1] = 0;
while (l < r) {
for (i = 0; i < p[q[l][0]].ns; ++i) {
if (p[q[l][0]].pt[i] == idy) {
step = q[l][1] + 1;
return step;
}
q[r][0] = p[q[l][0]].pt[i];
q[r][1] = q[l][1] + 1;
++r;
}
++l;
}
return -1;
}
int main() {
freopen("out.txt", "w", stdout);
int i;
char s[10];
while (scanf("%d %d", &n, &m), n | m) {
memset(p, 0, sizeof(p));
memset(id, 0, sizeof(id));
memset(flg, 0, sizeof(flg));
np = 0;
for (i = 0; i < n; ++i) {
scanf("%s", s);
if (!flg[s[0] - 'A']) {
id[s[0] - 'A'] = np;
p[np].id = s[0] - 'A';
flg[s[0] - 'A'] = 1;
np++;
}
int tpid = id[s[0] - 'A'];
if (s[1] != '-') {
if (!flg[s[1] - 'A']) {
p[np].ns = 0;
p[np].id = s[1] - 'A';
id[s[1] - 'A'] = np;
flg[s[1] - 'A'] = 1;
np++;
}
p[tpid].pt[p[tpid].ns] = id[s[1] - 'A'];
p[tpid].ns++;
}
if (s[2] != '-') {
if (!flg[s[2] - 'A']) {
p[np].ns = 0;
p[np].id = s[2] - 'A';
id[s[2] - 'A'] = np;
flg[s[2] - 'A'] = 1;
np++;
}
p[tpid].pt[p[tpid].ns] = id[s[2] - 'A'];
p[tpid].ns++;
}
}
while (m--) {
scanf("%s", s);
ok = false;
step = 0;
if (~BFS(id[s[0] - 'A'], id[s[1] - 'A'])) {
if (step == 1)
puts("child");
else {
while (step > 2) {
printf("great-");
step--;
}
puts("grandchild");
}
continue;
}
if (BFS(id[s[1] - 'A'], id[s[0] - 'A']) == -1)
puts("-");
else {
if (step == 1)
puts("parent");
else {
while (step > 2) {
printf("great-");
step--;
}
puts("grandparent");
}
}
}
}
return 0;
} 2011.09.25 PS: 上面的代码太挫了。。处理结点编号根本不用转来转去。。今天又敲了一遍。。竟然直接过sample直接AC。。
//2009年浙江大学计算机及软件工程研究生机试题 找出直系亲属
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node {
int ns, pt[30];
}p[30];
int n, m, stp, q[1000][2];
int BFS(int x, int y) {
int l = 0, r = 1, i;
q[l][0] = x;
q[l][1] = 0;
while(l < r) {
int tp = q[l][0];
for(i = 0; i < p[tp].ns; ++i) {
if(p[tp].pt[i] == y) {
stp = q[l][1] + 1;
return 1;
}
else {
q[r][0] = p[tp].pt[i];
q[r][1] = q[l][1] + 1;
++r;
}
}
++l;
}
return 0;
}
int main() {
int i, j, tp;
char s[5];
while(scanf("%d %d", &n, &m), n | m) {
for(i = 0; i < 26; ++i) {
p[i].ns = 0;
for(j = 0; j < 30; ++j) p[i].pt[j] = -1;
}
for(i = 0; i < n; ++i) {
scanf("%s", s);
if(s[1] != '-') {
tp = s[1] - 'A';
p[tp].pt[p[tp].ns++] = s[0] - 'A';
}
if(s[2] != '-') {
tp = s[2] - 'A';
p[tp].pt[p[tp].ns++] = s[0] - 'A';
}
}
while(m--) {
scanf("%s", s);
stp = 0;
if(BFS(s[0] - 'A', s[1] - 'A')) {
if(stp == 1) puts("parent");
else {
for(i = 0; i < stp - 2; ++i) {
printf("great-");
}
puts("grandparent");
}
}
else if(BFS(s[1] - 'A', s[0] - 'A')) {
if(stp == 1) puts("child");
else {
for(i = 0; i < stp - 2; ++i) {
printf("great-");
}
puts("grandchild");
}
}
else
puts("-");
}
}
return 0;
}
|