|
Posted on 2011-06-23 15:46 Uriel 阅读(1015) 评论(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
|