Codeforces Round #195 (Div. 2) 解题报告

problem A. Vasily the Bear and Triangle

题目：http://codeforces.com/problemset/problem/336/A

思路：水题，，虽然没大看懂什么意思，但随便写了写就过了。。。。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int x,y;
10     scanf("%d%d",&x,&y);
11     int ax,ay;
12     ax=x;
13     if(x<0)
14         ax=-x;
15     ay=y;
16     if(y<0)
17         ay=-y;
18     int s=ax+ay;
19     if(x<0)
20     {
21         if(y<0)
22             printf("%d 0 0 %d
",-s,-s);
23         else
24         {
25             printf("%d 0 0 %d
",-s,s);
26         }
27     }
28     else
29     {
30         if(y<0)
31             printf("0 %d %d 0
",-s,s);
32         else
33         {
34             printf("0 %d %d 0
",s,s);
35         }
36     }
37     return 0;
38 }

View Code

problem B. Vasily the Bear and Fly

题目：http://codeforces.com/problemset/problem/336/B

思路：从1~m号圆圆心分别到m+1~2m号圆圆心的最短距离的平均值

计算竖列相差i个圆计算次数每次距离

i=0 m 2R

i=1 2m-2 2R+sqrt(2)*R

i>=2 2m-2i 2*i-2+sqrt（8）*R

次数乘距离相加除以m*m即可

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int main()
 7 {
 8     int m,r;
 9     scanf("%d%d",&m,&r);
10     double dm=m;
11     double dr=r;
12     double sum;
13     int i;
14     double p=sqrt(2.0)*dr;
15     double pp=sqrt(8.0)*dr;
16     sum=dm*2*dr;
17     for(i=1; i<m; i++)
18     {
19         int u=2*i;
20         if(i<2)
21         sum+=(2*dm-u)*(u*dr+p);
22         else
23         sum+=(2*dm-u)*((u-2)*dr+pp);
24     }
25     sum/=(dm*dm);
26     printf("%.10f
",sum);
27 
28     return 0;
29 }

View Code

problem C. Vasily the Bear and Sequence

题目：http://codeforces.com/contest/336/problem/C

思路：从大到小枚举v，若data[j]&1<<i!=0,,,则证明满足条件否则不行，，，得到的sum若能整除1<<i,,,则找到。。。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=100010;
 6 int data[maxn];
 7 int main()
 8 {
 9     int n;
10     while(scanf("%d",&n)!=EOF)
11     {
12         int i,j;
13         for(i=1; i<=n; i++)
14         {
15             scanf("%d",&data[i]);
16         }
17         int sum;
18         int num;
19         for(i=29; i>=0; i--)
20         {
21             int m=1<<i;
22             sum=-1;
23             num=0;
24             for(j=1; j<=n; j++)
25             {
26                 if((data[j]&m)!=0)
27                 {
28                     if(sum==-1)
29                         sum=data[j];
30                     else
31                         sum&=data[j];
32                     num++;
33                 }
34             }
35             int k=0;
36             if(sum%m==0)
37             {
38                 printf("%d
",num);
39                 for(i=1;i<=n;i++)
40                 {
41                     if((data[i]&m)!=0)
42                     {
43                         k++;
44                         if(k!=num)
45                         printf("%d ",data[i]);
46                         else
47                         printf("%d
",data[i]);
48                     }
49 
50                 }
51                 break;
52             }
53         }
54     }
55     return 0;
56 }

View Code

problem D. Vasily the Bear and Beautiful Strings

题目：http://codeforces.com/contest/336/problem/D

思路：g值=string

0 =1__(指第一位只要为1，后面随便排列最后即可得到g值为0,(下同))

1 =01__

　　　 0 =001__

1 =0001__

......=........

即可发现规律，，，，注意1的个数只有1的时候需要特判

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 #define LL __int64
  7 const int maxn=100010;
  8 const int mod=1000000007;
  9 int n0,n1,g;
 10 LL fac[maxn*2];
 11 void init()//处理i的阶乘
 12 {
 13     int i;
 14     fac[1]=1;
 15     for(i=2; i<=maxn*2-5; i++)
 16     {
 17         fac[i]=i*fac[i-1];
 18         fac[i]%=mod;
 19     }
 20 }
 21 //求p^n
 22 LL poow(LL p,LL n)
 23 {
 24     LL sp=1;
 25     while(n>0)
 26     {
 27         if(n%2==1)
 28             sp=sp*p%mod;
 29         n/=2;
 30         p=p*p%mod;
 31     }
 32     return sp;
 33 }
 34 //在a与mod互质的情况，根据费马小定理，求a的逆元
 35 LL inv(LL a)
 36 {
 37     return poow(a,mod-2);
 38 }
 39 //求组合数
 40 LL c(int n,int k)
 41 {
 42     LL res;
 43     if(n==k)
 44         return 1;
 45     if(k==0)
 46         return 1;
 47     res=fac[n]*inv(fac[n-k]*fac[k]%mod);
 48     res%=mod;
 49     return res;
 50 }
 51 int main()
 52 {
 53     init();
 54     while(scanf("%d%d%d",&n0,&n1,&g)!=EOF)
 55     {
 56         int num1,num0;
 57         int i;
 58         LL ans=0;
 59         if(n0==0)
 60         {
 61             if(n1==1)
 62             {
 63                 if(g==0)
 64                     printf("0
");
 65                 else
 66                     printf("1
");
 67             }
 68             else
 69             {
 70                 if(g==0)
 71                     printf("1
");
 72                 else
 73                     printf("0
");
 74             }
 75             continue;
 76         }
 77         if(n1==0)
 78         {
 79             if(n0%2==1)
 80             {
 81                 if(g==0)
 82                     printf("1
");
 83                 else
 84                     printf("0
");
 85             }
 86             else
 87             {
 88                 if(g==0)
 89                     printf("0
");
 90                 else
 91                     printf("1
");
 92             }
 93             continue;
 94         }
 95         if(g==0)
 96         {
 97             for(i=0; i<=n0; i+=2)//偶数个0加上1个1时候，后面随便排列
 98             {
 99                 num1=1;
100                 num0=i;
101                 if(n0+n1-(num0+num1)>0)
102                 {
103                     ans+=c(n0+n1-(num0+num1),n0-num0);
104                 }
105                 ans%=mod;
106 
107             }
108             if(n1==1)//特判1的个数为1的时候
109             {
110                 if(n0%2==1)//当0的个数为奇数是才会最终成为0
111                     ans++;
112             }
113         }
114         else
115         {
116             for(i=1; i<=n0; i+=2)//奇数个0加上1个1时候，后面随便排列
117             {
118                 num1=1;
119                 num0=i;
120                 if(n0+n1-(num0+num1)>0)
121                 {
122                     ans+=c(n0+n1-(num0+num1),n0-num0);
123                 }
124                 ans%=mod;
125 
126             }
127             if(n1==1)//特判1的个数为1的时候
128             {
129                 if(n0%2==0)//当0的个数为偶数是才会最终成为1
130                     ans++;
131             }
132         }
133         printf("%I64d
",ans);
134     }
135     return 0;
136 }

View Code