Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
    昨天开始做的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, 
0sizeof(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] > 100000break;
            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, 
0x00sizeof(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, 
0sizeof(f));
        memset(g, 
0sizeof(g));
        memset(ss1, 
0x00sizeof(ss1));
        memset(ss2, 
0x00sizeof(ss2));
        memset(common, 
0x00sizeof(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, 0x00sizeof(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, 
0sizeof(f));
        memset(ss, 
0x00sizeof(ss));
        memset(ans, 
0x00sizeof(ans));
        memset(common, 
0x00sizeof(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, 
0x00sizeof(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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理