首页 > 其他 > 详细

165C.Another Problem on Strings

时间:2019-08-06 14:14:39      阅读:71      评论:0      收藏:0      [点我收藏+]

codeforces百题计划第一周(4)

观察

发现对于k!=0时,对于包含k个1的区间,第一个1左边的0和第k个1右边的0时可选可不选的,那么对于包含当前k个1的区间,找到包含最有0的所有不同情况就时对于包含当前k个1的所有区间

记录每个1的位置,cnt[i]

每个1左右0的个数,l[i],r[i]

对于每个包含k个1的区间就是 (r[i]+1)*(l[i-k+1]+1)

这种题就不要怕麻烦,怕麻烦是写不出来的,硬刚就对了

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=1e6+5;
 5 typedef long long ll;
 6 const ll INF=1e18;
 7 ll c[maxn];
 8 ll l[maxn];
 9 ll r[maxn];
10 ll C(int kk)
11 {
12     ll res=1;
13         for(int i=kk;i>=1;i--)
14         {
15             res=kk*res;
16         }
17     return res;
18 } 
19 int main()
20 {
21     int k;cin>>k;
22     string str;cin>>str;
23     
24     if(k==0)
25     {
26         ll s=0;ll res=0;
27         for(int i=0;i<str.size();i++)
28         {
29             if(str[i]==0) s++;
30          
31         else
32         {
33             res+=(s*(s+1)/2);
34             s=0;
35         }
36     }
37         res+=(s*(s+1)/2);
38         cout <<res<<endl;
39         return 0;
40     }
41     
42     int ct=0;int cnt=0;
43     for(int i=0;i<str.size();i++){
44         if(str[i]==0) ct++;         
45         else if(str[i]==1) 
46         {
47             r[cnt]=ct;
48             c[++cnt]=i;
49             l[cnt]=ct;
50             ct=0;
51         }
52     }    
53     r[cnt]=ct;
54     ll ans=0;
55     /*for(int i=1;i<=cnt;i++)
56     {
57         cout <<c[i]<<" "<<l[i]<<" "<<r[i]<<endl;
58     }*/
59     for(int i=k;i<=cnt;i++)
60     {
61         ans+=(r[i]+1)*(l[i-k+1]+1);
62     }
63     cout <<ans<<endl;
64     return 0;
65 } 
66 
67 //记录每个1的位置,然后从cnt==k开始,再记录每个1左右有几个0,那么就是右*左 

 

165C.Another Problem on Strings

原文:https://www.cnblogs.com/Msmw/p/11308262.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!