|
|
Posted on 2011-06-23 15:46 Uriel 閱讀(1062) 評論(0) 編輯 收藏 引用 所屬分類: 考研&保研復試上機題
昨天開始做的ZJU 2011年保研復試題, 早就聽鯨魚隊長說過題目超水的, 就想著速度水過, 結果被Diff那題卡了快2天, 后來問了鯨魚隊長, 去年考試現場貌似真木有人做出來... (個人認為這題題目說的真不清楚... PE到抓狂...這題下面再細說) 1. Twin Prime Conjecture 水題, 給你一個整數n (n < 1e5), 問<n的數中有多少對素數, 滿足它們的差為2 先線性篩素數, 然后預處理出所有n (n < 1e5) 中, <n的滿足條件的素數對數, 然后對于每個Query, 直接輸出
 //浙大計算機研究生保研復試上機考試-2011年 Twin Prime Conjecture
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100010
int lenPr, record[N], prime[N], sum[N], ans[N];
  void init()  {
 memset(record, 0, sizeof(record));
lenPr = 0;
record[0] = 1;
record[1] = 1;
  for (int i = 2; i <= 100000; ++i) {
if (!record[i]){
++lenPr;
prime[lenPr - 1] = i;
 }
for(int j = 0; j <= lenPr - 1; ++j) {
if (i * prime[j] > 100000) break;
record[i * prime[j]] = 1;
if (!(i % prime[j])) break;
}
}
 }
int main() {
int i, n, pre;
init();
int cnt = 0;
pre = 2;
for(i = 0; i <= 100000; ++i) {
if(!record[i]) {
if(i - pre == 2) ans[i] = ++cnt;
else
ans[i] = cnt;
pre = i;
}
else
ans[i] = cnt;
}
while(scanf("%d", &n), n > 0) {
printf("%d\n", ans[n]);
}
return 0;
}2. Is It Symmetric 水題, 判斷一個數是否是回文數, 該數可做任意多次循環左移/右移操作 暴力之, 假設數的長度為len, 做len次, 每次循環左移一位, 然后判斷
//浙大計算機研究生保研復試上機考試-2011年 Is It Symmetric
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int l, ll;
char s[200], ss[200];
int main() {
int i, j;
while(scanf("%s", s), s[0] != '#') {
l = strlen(s);
ll = l >> 1;
for(i = 0; i < l; ++i) {
memset(ss, 0x00, sizeof(ss));
for(j = i; j < l; ++j) ss[j - i] = s[j];
for(j = 0; j < i; ++j) ss[j + l - i] = s[j];
for(j = 0; j < ll; ++j) {
if(ss[j] != ss[l - j - 1]) break;
}
if(j == ll) break;
}
if(i == l) puts("NO");
else
printf("YES %d\n", (i + ll) % l);
}
return 0;
} 3. Magic Coupon 貪心, coupons 和 product value的所有正數值從大到小排序, 大的和大的相乘, 小的和小的相乘; 所有負值從小到大排序, 也是小的和小的相乘(絕對值大的), 大的和大的相乘 注意用__int64, 包括coupons和product value的值, 否則相乘時會越界(WA 3次才發現, 弱啊... ...)
//浙大計算機研究生保研復試上機考試-2011年 Magic Coupon
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1000010
#define I __int64
struct M{
I val;
}p[N], q[N];
bool cmp1(M a, M b) {
return a.val < b.val;
}
int nc, np;
I ans;
int main() {
int i, j;
while(scanf("%d", &nc), nc >= 0) {
for(i = 0; i < nc; ++i) {
scanf("%I64d", &p[i].val);
}
sort(p, p + nc, cmp1);
scanf("%d", &np);
for(i = 0; i < np; ++i) {
scanf("%I64d", &q[i].val);
}
sort(q, q + np, cmp1);
ans = 0;
for(i = nc - 1, j = np - 1; i >= 0, j >= 0; --i, --j) {
if(!(p[i].val > 0 && q[j].val > 0)) break;
ans += p[i].val * q[j].val;
}
for(i = 0, j = 0; i < nc, j < np; ++i, ++j) {
if(!(p[i].val < 0 && q[j].val < 0)) break;
ans += p[i].val * q[j].val;
}
printf("%I64d\n", ans);
}
return 0;
} 4. Diff 卡了快2天, 題目真的是沒有說清楚多行的時候應該怎么輸出啊...!! 一開始看了很久都沒有理解最后一個sample, 好不容易想出一種能說得通的理解方式, 敲了半天, 果斷WA (還有幾次TLE是WA得頭昏了, freopen忘記去掉了...), 昨天網上改來改去終于WA變成PE, 就PE到死也莫名了... ... 實在無奈, 今天搜到一個解題報告, www.cnblogs.com/while2/archive/2011/03/14/1983524.html 對拍之后發現有幾個多行的case輸出不同, 但是對解題報告為什么那樣輸出理解不能... ... 猥瑣地用小號試了下解題報告的代碼, 完美地AC了, 于是把輸出的那里改成解題報告的那種思路了... ... 改完對拍了下, 還是有一些數據不同... 交了下, 竟然就AC了, 莫名啊... = =|| PE的代碼, 依然莫名中... 路過的大牛有空指教的話不甚感激
//浙大計算機研究生保研復試上機考試-2011年 Diff
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 5010
int n, m, l1, l2, fi, fj, nt, dp[N][N], flg[N][N], f[N], g[N];
char s[100], ss1[N], ss2[N], common[N];
void LCS(char *a, char *b) {
int i, j;
bool ok = false;
fi = fj = 0;
for(i = 0; i <= l1; ++i) dp[i][0] = 0;
for(i = 0; i <= l1; ++i) dp[0][i] = 0;
for(i = 1; i <= l1; ++i)
for(j = 1; j <= l2; ++j)
if(a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
flg[i][j] = 1;
}
else {
if(dp[i - 1][j] > dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
flg[i][j] = 2;
}
else {
dp[i][j] = dp[i][j - 1];
flg[i][j] = 3;
}
}
return;
}
void traceback(int i, int j) {
while(i > 0 && j > 0) {
if(flg[i][j] == 1) {
--i; --j;
common[nt++] = ss1[i];
}
else if(flg[i][j] == 2) {
--i;
}
else if(flg[i][j] == 3) {
--j;
}
}
}
int main() {
//freopen("d:\\in.txt", "r", stdin);
//freopen("d:\\out.txt", "w", stdout);
int i, j, pos, line;
bool ff, nl;
while(scanf("%d", &n), n >= 0) {
scanf("%d", &m);
getchar();
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
memset(ss1, 0x00, sizeof(ss1));
memset(ss2, 0x00, sizeof(ss2));
memset(common, 0x00, sizeof(common));
for(i = 0; i < n; ++i) {
gets(s);
strcat(ss1, s);
f[strlen(ss1)] = 1;
}
for(i = 0; i < m; ++i) {
gets(s);
strcat(ss2, s);
g[strlen(ss2)] = 1;
}
l1 = strlen(ss1), l2 = strlen(ss2);
LCS(ss1, ss2);
if(dp[l1][l2] == 0) puts("Totally different");
else if(dp[l1][l2] == l1 && l1 == l2) puts("No difference found");
else {
nt = 0;
traceback(l1, l2);
printf("%d\n", dp[l1][l2]);
i = 1, j = 1; pos = nt - 1; line = 2;
puts("line #1");
nl = false;
while(pos >= 0) {
ff = false;
while(ss1[i - 1] != common[pos]) {
putchar(ss1[i - 1]);
ff = true;
nl = true;
if(f[i]) {
printf("-\nline #%d\n", line++);
++i;
ff = false;
nl = false;
goto M;
}
++i;
}
if(ff) {
putchar('-');
nl = true;
ff = false;
}
if(f[i] && nl && i < l1) {
printf("\nline #%d\n", line++);
nl = false;
}
else if(f[i] && nl && i == l1) {
puts("");
nl = false;
}
++i;
ff = false;
while(ss2[j - 1] != common[pos]) {
ff = true;
putchar(ss2[j - 1]);
nl = true;
if(g[j]) {
putchar('+');
puts("");
nl = false;
ff =false;
}
++j;
}
if(ff) {
putchar('+');
ff = false;
}
else if(g[j] && nl) {
puts("");
nl = false;
}
++j;
if(i > l1 || j > l2) break;
pos--;
M: ;
}
ff = false;
while(i <= l1) {
ff = true;
putchar(ss1[i - 1]);
nl = true;
if(f[i]) {
putchar('-');
nl = true;
if(i < l1) {
printf("\nline #%d\n", line++);
nl = false;
}
ff =false;
}
++i;
}
if(ff) {
putchar('-');
nl = true;
}
ff = false;
while(j <= l2) {
ff = true;
putchar(ss2[j - 1]);
nl = true;
if(g[j]) {
putchar('+');
nl = true;
if(j < l2) {
puts("");
nl = false;
}
ff = false;
}
++j;
}
if(ff) putchar('+');
if(nl)puts("");
}
}
return 0;
} AC的代碼
//浙大計算機研究生保研復試上機考試-2011年 Diff
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 5010
int n, m, l1, l2, nt, na, line, dp[N][N], flg[N][N], f[2][N], ned[2], usd[2];
char s[100], ss[2][N], common[N], ans[2 * N], mark[3] = "-+";
void LCS(char *a, char *b) {
int i, j;
bool ok = false;
for(i = 0; i <= l1; ++i) dp[i][0] = 0;
for(i = 0; i <= l2; ++i) dp[0][i] = 0;
for(i = 1; i <= l1; ++i)
for(j = 1; j <= l2; ++j)
if(a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
flg[i][j] = 1;
}
else {
if(dp[i - 1][j] > dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
flg[i][j] = 2;
}
else {
dp[i][j] = dp[i][j - 1];
flg[i][j] = 3;
}
}
return;
}
void traceback(int i, int j) {
while(i > 0 && j > 0) {
if(flg[i][j] == 1) {
common[nt++] = ss[0][i - 1];
--i; --j;
}
else if(flg[i][j] == 2) --i;
else
--j;
}
}
void addmk(int i) {
if(na != 0 && ans[na - 1] != '+' && ans[na - 1] != '-')
ans[na++] = mark[i];
}
void addline(int i) {
if(na != 0 && ans[na - 1] != '\n') {
addmk(i);
printf("%s\n", ans);
if(!i) printf("line #%d\n", line++);
na = 0; memset(ans, 0x00, sizeof(ans));
}
}
void checked(int i, int idx) {
if(ned[i] > usd[i] && idx == f[i][usd[i]]) {
usd[i]++;
addline(i);
}
}
void out(int i, int &idx, char ed) {
if(ss[i][idx] == ed) {
++idx;
checked(i, idx);
return;
}
while(ss[i][idx] != ed) {
ans[na++] = ss[i][idx];
++idx;
checked(i, idx);
}
++idx;
addmk(i);
checked(i, idx);
return;
}
int main() {
//freopen("d:\\in.txt", "r", stdin);
//freopen("d:\\out.txt", "w", stdout);
int i, j;
while(scanf("%d", &n), n >= 0) {
scanf("%d", &m);
getchar();
memset(f, 0, sizeof(f));
memset(ss, 0x00, sizeof(ss));
memset(ans, 0x00, sizeof(ans));
memset(common, 0x00, sizeof(common));
ned[0] = ned[1] = 0;
for(i = 0; i < n; ++i) {
gets(s);
strcat(ss[0], s);
if(i < n - 1)f[0][ned[0]++] = strlen(ss[0]);
}
for(i = 0; i < m; ++i) {
gets(s);
strcat(ss[1], s);
if(i < m - 1)f[1][ned[1]++] = strlen(ss[1]);
}
if(!strcmp(ss[0], ss[1])) {
puts("No difference found");
continue;
}
l1 = strlen(ss[0]); l2 = strlen(ss[1]);
LCS(ss[0], ss[1]);
if(!dp[l1][l2]) {
puts("Totally different");
continue;
}
nt = na = 0;
memset(ans, 0x00, sizeof(ans));
printf("%d\n", dp[l1][l2]);
traceback(l1, l2);
i = 0, j = 0; line = 2;
usd[0] = usd[1] = 0;
printf ("line #1\n");
while(nt > 0) {
char ch = common[nt - 1];
nt--;
out(0, i, ch);
out(1, j, ch);
}
out(0, i, 0);
out(1, j, 0);
printf("%s\n", ans);
}
return 0;
} 我AC的代碼跟解題報告跑出來結果不同的數據: 1 1 ababab babab 1 1 //前兩組數據一樣, 但解題報告的代碼跑出來的第一次多一個回車... ababab babab 2 2 fdasf sdfdsg fhgfh dfhfdhfd 4 4 sdf tre ghjdf wtrwt erte wet ytrye eqtqe
|