题意:给一个01字符串s,找出s包含恰好k个1的连续字串个数

解法:

显然是简单的双指针or二分的题,但由于k=0的存在,使得双指针的边界条件十分难写,所以应该选择二分!

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29); int k;
ll sum[maxn];
char s[maxn]; void solve(){
scanf("%s",s+1);
int n=strlen(s+1);
sum[0]=0;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+s[i]-'0';
ll res=0;
for(int i=1;i<=n;i++){
int l=lower_bound(sum+i,sum+n+1,k+sum[i-1])-sum;
int r=upper_bound(sum+i,sum+n+1,k+sum[i-1])-sum;
if(l==n+1) break;
res+=r-l;
}
cout<<res<<endl;
} int main(){
// freopen("in.txt","r",stdin);
while(cin>>k) solve();
return 0;
}

最新文章

  1. HTML特殊转义字符列表
  2. 焦点问题onfocus=”this.blur()”代替方法(转)
  3. 为什么要urlencode
  4. ionic项目的一些简单操作
  5. POJ3280 - Cheapest Palindrome(区间DP)
  6. Android实时监听网络状态(1)
  7. box-size
  8. 地牢逃脱 (BFS)
  9. 常用yum操作命令
  10. Liunx 特殊权限 suid sgid t
  11. iOS12
  12. Java中的静态变量、静态方法问题
  13. 雷林鹏分享:使用 CSS 显示 XML
  14. OAuth和OpenID的区别
  15. c sharp dll
  16. list的方法、操作
  17. [转]生成 Excel.dll
  18. YBT 6 数学基础
  19. 利用C#改写JAVA中的Base64.DecodeBase64以及Inflater解码
  20. 15 并发编程-(IO模型)

热门文章

  1. oculus 安装其他盘方法
  2. Dockerfile构建python项目
  3. TensorFlow中使用tf.keras.callbacks.EarlyStopping防止训练过拟合
  4. 时间序列分析2.X AR与MA
  5. CLIP 读书笔记
  6. JRebel for IDEA插件 激活
  7. idea快捷的输出常用语句
  8. 安全测试-WEB安全渗透测试基础知识(一)
  9. Mac新手必看Mac入门基本知识图文教程
  10. [Err] [Dtf] 1044 - Access denied for user &#39;root&#39;@&#39;localhost&#39; to database &#39;information_schema&#39;