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