2019佳木斯集训 Day6

　　数学题,主要就是找规律,不难

　　思路:我们首先确定a的数量是不会变的,所以我们只能

把a推到最后面,而后我们得出结论在遇到一个b时ans就加上

2的(前面已经遇到的a的数量)次方-1即可,还是很好推的.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 char a[2000010];
 4 long long two[2000010],twoo[2000010];
 5 const long long mod=1000000007;
 6 long long top,len,ans;
 7 int main(){
 8     scanf("%s",a+1);
 9     len=strlen(a+1);
10     two[1]=twoo[1]=1;
11     for(register int i=2;i<=len;i++) twoo[i]=(twoo[i-1]*2)%mod;
12     for(register int i=1;i<=len;i++){
13         if(i>=2) two[i]=(two[i-1]+twoo[i])%mod;
14         if(a[i]=='a') top++;
15         else if(a[i]=='b') ans+=two[top]-1;
16         ans%=mod;
17     }
18     printf("%lld",ans+len-top);
19     return 0;
20 }

T1-优美的字符串

　　还是数学题,这谁顶得住啊~~~~~

　　考试时思路对,不过差了太多细节导致只水到

了10分.

　　思路:我们可知n小于2的1000次方,所以第一次操作后

得到的值必然小于1000,我们预处理1000以内所有值到1需要的操作

次数,然后遍历字符串,找到1时把他干掉,所以他后面位数就可以拿来随便

取1或是0,同时记录当前点之前有多少个1,在之后计算时,要多计算

之前的1的总数,计算当前可取点数+以前的1的数量==k时,ans+=len-当前所取到

的i位中取后面要取1的数量即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 long long ans;
 4 int len,noww;
 5 int two[11];
 6 int now[1010];
 7 const long long mod=1000000007;
 8 long long a[1010][1010];
 9 char s[1010];
10 bool ac;
11 int k,tot;
12 int main(){
13     scanf("%s",s+1);
14     len=strlen(s+1);
15     for(register int i=1;i<=len;i++) if(s[i]=='0'){ac=1;break;}
16     for(register int i=1;i<=len;i++)
17     for(register int j=0;j<=i;j++){
18         if(i==j||j==0){a[i][j]=1;continue;}
19         else if(j==1){a[i][j]=i;continue;}
20         else a[i][j]=a[i-1][j-1]+a[i-1][j];
21         a[i][j]%=mod;
22     }
23     //cout<<a[5][3];
24     two[1]=1;
25     now[1]=0;
26     for(register int i=2;i<=10;i++) two[i]=two[i-1]*2;
27     for(register int i=2;i<=1000;i++){
28         int num=i;
29         noww=0;
30         for(register int j=10;j>=1;j--) if(two[j]<=num) noww++,num-=two[j];
31         now[i]=now[noww]+1;
32     }
33     scanf("%d",&k);
34     if(k==0){
35         printf("1");
36         return 0;
37     }
38     if(k==1){
39         printf("%d",len-1);
40         return 0;
41     }
42     k--;
43     for(register int i=1;i<=len;i++){
44         if(s[i]=='1'){
45             int lens=len-i;
46             for(register int j=0;j<=lens;j++) if(now[j+tot]==k) ans+=a[lens][j];
47             ans%=mod;
48             tot++;
49         }
50     }
51     if(now[tot]==k) ans++;
52     printf("%lld",ans);
53     return 0;
54 }

T2-数字谜题

　　不会会~~~~~

　　end;