Codeforces Round #272 (Div. 2)

A. Dreamoon and Stairs

题意：给出n层楼梯，m,一次能够上1层或者2层楼梯，问在所有的上楼需要的步数中是否存在m的倍数

找出范围，即为最大步数为n（一次上一级），最小步数为n/2+n%2 在这个范围里找即可

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 int main()
11 {
12     int n, m,i,flag=0,mn,mx;
13     cin>>n>>m;
14     mx=n;
15     mn=n/2+n%2;
16     
17     for(i=mn;i<=mx;i++){
18         if(i%m==0) {
19             flag=1;
20             printf("%d
",i);
21             break;
22         }
23     }
24     if(!flag) printf("-1
");
25 }

View Code

B. Dreamoon and WiFi

题意：给出两个字符串s1,s2 s1中只包含'+','-'（+代表加1，-代表-1） s2中包含'+','-','?'三种，问s1,s2串得到相同的数值的概率

在s1中，令a[0]表示-，a[1]表示+

在s2中，令b[0]表示-，b[1]表示+,b[2]表示问号

分问号的个数为0和不为0来讨论

问号为0是：分别判断加号，减号的个数是否相等即可

问号不为0是，那么所差的加号为a[1]-b[1],即为从b[2]个位置中选出a[1]-a[0]个位置，再用这个除以总的方案数2^b[2]

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 char s1[15],s2[15],a[5],b[5];
10 
11 
12 LL C(int n,int m){
13     if(n<m||n<0||m<0) return 0;
14     if(m<n-m) m=n-m;
15     LL ans=1;
16     for(int i=m+1;i<=n;i++) ans*=i;
17     for(int i=1;i<=n-m;i++) ans/=i;
18     return ans;
19 }
20 
21 int main()
22 {
23     int len1,len2,i,j,pos,pos1,tot,sum,sum1;
24     cin>>s1>>s2;
25     len1=strlen(s1);
26     len2=strlen(s2);
27     
28 //    printf("c(2,3)=%d
",C(2,3));
29     
30     for(i=0;i<len1;i++){
31         if(s1[i]=='+') a[1]++;
32         if(s1[i]=='-') a[0]++;
33     }
34     for(i=0;i<len2;i++){
35         if(s2[i]=='+') b[1]++;
36         else if(s2[i]=='-') b[0]++;
37         else b[2]++;
38     }
39     if(b[2]==0){
40         if(a[0]==b[0]&&a[1]==b[1]) printf("1.000000000000
");
41         else printf("0.000000000000
");
42     }
43     else{
44         pos1=a[1]-b[1];
45         pos=b[2];
46         tot=1;
47         for(i=1;i<=pos;i++)
48         tot*=2;
49         double ans=(C(pos,pos1)*1.0)/tot;
50         printf("%.12lf
",ans);
51     }
52     return 0;
53 }

View Code

C. Dreamoon and Sums

题意：给出a,b,找出符合以下条件的x，div(x,b)/mod(x,b)=k，其中k所在范围是[1,a]，其中mod(x,b)!= 0.求满足这样的条件的x的和

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 LL mod=1000000007;
10 
11 int main()
12 {
13     LL a,b;
14     cin>>a>>b;
15     LL ans1=(a*(a+1)/2%mod*b%mod+a)%mod;
16     LL ans2=b*(b-1)/2%mod;
17     LL ans3=ans1*ans2%mod;
18     cout<<ans3<<"
";
19 }

View Code

c是= =翻译的题解----