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