模拟题组

以下几个题目来自于：浙大计算机研究生保研复试上机考试-2011年题组。

晚上没什么事做着试了一下，没想到是三道模拟题，正巧很久没有做过这种模拟了，不过速度是慢了很多。

hdu 3792 Twin Prime Conjecture

英文是硬伤，借助百度翻译才看懂这是求孪生素数数目的题目。没有n的范围，假设1000000用筛法打表之后求和。一开始对于时间估计过于乐观，求孪生素数没和求和写在一起，超时了一次。

另外：

memset是对每个字节赋值，而int有4字节(32位) 比如这样,memset(a,1,sizeof(a)); 则a中的每个元素都被赋值成为2进制数为，00000001000000010000000100000001，的数转换成10进制就是16843009所以，一般用memset对数组赋0或-1，赋其他的值就要用循环来实现。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAX 1000000
 4 int a[MAX]={1};
 5 int ans[MAX]={0};
 6 int main ()
 7 {
 8     for(int i=2;i<MAX;i++)
 9         a[i]=1;
10     a[0]=a[1]=0;
11     for(int i=2;i<MAX;i++)
12     {
13         if(a[i]==1)
14         {
15             int delt=2;
16             int base=i;
17             for(int k=base*delt;k<MAX;k=base*delt)
18             {
19                 a[k]=0;
20                 delt++;
21             }
22         }
23     }
24     for(int i=2;i<MAX;i++)
25     {
26         if(a[i]==1&&a[i-2]==1)
27             ans[i]=ans[i-1]+1;
28         else
29             ans[i]=ans[i-1];
30     }
31     int n;
32     while(scanf("%d",&n)&&n>0)
33     {
34 
35         printf("%d
",ans[n]);
36     }
37     return 0;
38 }

hdu 3792

hdu 3793 Is It Symmetric

一个循环字符串，找这个圈的对称中心，而且限定了只有一个对称中心，长度小于100。

考虑了一会，没想到什么靠谱的算法，于是还是暴力吧，挨个字符过。TLE了两次，因为没有考虑单个字符的情况，而第一遍改还没改的很完善。

 1 #include<stdio.h>
 2 #include<string.h>
 3 char str[102];
 4 int main()
 5 {
 6     while(scanf("%s",str))
 7     {
 8         int length=strlen(str);
 9         int flag=0;
10         if(length==1&&str[0]=='#')break;
11         if(length==1)
12         {
13             printf("YES %d
",0);
14             flag=1;
15         }
16         else
17         {
18             for(int i=0;i<length;i++)
19             {
20                 int j=1;int max=length/2;
21                 while(str[(i+j)%length]==str[((i-j)+length)%length])
22                 {
23                     if(j==max)
24                     {
25                         flag=1;
26                         printf("YES %d
",i);break;
27                     }
28                     j++;
29                 }
30 
31             }
32         }
33         if(flag==0)
34             printf("NO
");
35     }
36     return 0;
37 }

hdu 3793

hdu 3794 Magic Coupon

才看到题目以为是个dp,结果捉急的英文理解清楚之后发现也是模拟，说好听点是贪心。

排个序，两边算正的结果就加进最后的结果里。代码wa了很多次，后来发现是因为存储的数据也应经超出int的范围了。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 __int64 nc[1000010];
 5 __int64 np[1000010];
 6 int main()
 7 {
 8     __int64 ans;
 9     int c,p;
10     while(scanf("%d",&c))
11     {
12         if(c<0)break;
13         else
14         {
15             int fc=c,fp;
16             ans=0;
17             for(int i=0;i<c;i++)
18                 scanf("%I64d",&nc[i]);
19             sort(nc,nc+c);
20             for(int i=0;i<c;i++)
21                 if(nc[i]>0)
22                 {
23                     fc=i;break;
24                 }
25             scanf("%d",&p);
26             fp=p;
27             for(int i=0;i<p;i++)
28                 scanf("%I64d",&np[i]);
29             sort(np,np+p);
30             for(int i=0;i<p;i++)
31                 if(np[i]>0)
32                 {
33                     fp=i;break;
34                 }
35             int ci=c-1;int pi=p-1;
36             while(ci>=fc&&pi>=fp)
37             {
38                 ans+=nc[ci]*np[pi];
39                 ci--;
40                 pi--;
41             }
42             ci=0,pi=0;
43             while(ci<fc&&pi<fp)
44             {
45                 ans+=nc[ci]*np[pi];
46                 ci++;
47                 pi++;
48             }
49             printf("%I64d
",ans);
50         }
51     }
52 }

hdu 3794

hdu 3795 Diff

题目是有点麻烦，有点麻烦。