HDU 3784 继续xxx定律 & HDU 2578 Dating with girls(1)

做3748之前要先做xxx定律对于一个数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成 3*n+ 1后砍掉一半，直到该数变为1为止。

当n为3时，我们在验证xxx定律的过程中会得到一个序列，3，5，8，4，2，1，将3称为关键数，5，8，4，2称为覆盖数。现在输入n个数字a[i]，根据关键数与覆盖数的理论，我们只需要验证其中部分数就可以确定所有数满足xxx定律，输出输入的n个数中的关键数。如果其中有多个关键数的话按照其输入顺序的逆序输出。

所以只需把n个数都当做关键数，一一标记a[i]的覆盖数，最后在这数列中找到未被标记的，逆序输出。

15 ms

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 using namespace std;
 5 int main()
 6 {
 7   int a[1005],b[10005],i,n,x,y,c[130000]; //a为原数列，b为未被标记的数列,c为标记，记得c要开很大，因为要（x*3+1）/2可能很大
 8   while(~scanf("%d",&n)&&n)
 9   {
10     memset(c,0,sizeof(c));   //清零
11     for(i=1;i<=n;i++)
12       scanf("%d",&a[i]);
13     for(i=1;i<=n;i++)
14     {
15       x=a[i];
16       if(!c[x])   //未被标记，若已被标记那么x的覆盖数已全被标记
17         while(x!=1)
18         {
19           if(x%2==0)
20           {
21             x/=2;
22             c[x]=1;
23           }
24           else
25           {
26             x=(3*x+1)/2;
27             c[x]=1;
28           }
29         }
30     }
31     y=0;
32     for(i=1;i<=n;i++)
33       if(c[a[i]]==0)   //未被标记
34         b[++y]=a[i];
35     for(i=y;i>=2;i--)  //逆序输出
36       printf("%d ",b[i]);
37     printf("%d
",b[1]);
38   }
39   return 0;
40 }

第二题 2578

大意是：给出n个数，满足x属于n，y属于n，x+y=k的方案数。 PS；1+3和3+1算两种，2+2只算一种

刚开始想用母函数做.....后来发现k<2^31，数组开不了这么大T^T

后来是周XX说用二分= =，想想也是......

然后各种改，错了6次！！！！ 406MS

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iostream>
 5 using namespace std;
 6 int main()
 7 {
 8     int T,n,k,i,a[100005],l,r,sum,x,mid,y;
 9     scanf("%d",&T);
10     while(T--)
11     {
12         sum=0;
13         y=0;
14         scanf("%d%d",&n,&k);
15         for(i=1;i<=n;i++)
16         {
17             scanf("%d",&a[i]);
18             if(k%2==0&&a[i]==k/2)   //如果存在k/2这个数，则方法数+1
19                 y=1;
20         }
21         a[0]=-1;
22         sort(a+1,a+n+1);    //排序
23         for(i=1;i<=n;i++)
24         if(a[i]<(k+1)/2 && a[i]!=a[i-1])      //先1,3；3,1只算一种，不要重复算     ①
25         { 
26             x=k-a[i];    //找y
27             l=0; 
28             r=n+1;     //②
29             mid=(l+r)/2;
30             while(r-l>1)      //③
31             {
32                 mid=(l+r)/2;
33                 if(a[mid]>x)
34                     r=mid;
35                 if(a[mid]<x)
36                     l=mid;
37                 if(a[mid]==x)
38                     break;
39             }
40             if(a[mid]==x)
41                 sum++;
42         }
43         sum=sum*2+y;   //sum*2+是否有x=y这种情况
44         printf("%d
",sum);
45     }
46     return 0;
47 }

做的时候有几个易错的地方： ①②③

还有一组很难过得数据：

3 4

1 2 3

两道这样的题做了那么久.......╭(╯^╰)╮