codeforces 165C Another Problem on Strings 二分or双指针
2024-10-22 04:26:33
题意:给一个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;
}
最新文章
- HTML特殊转义字符列表
- 焦点问题onfocus=”this.blur()”代替方法(转)
- 为什么要urlencode
- ionic项目的一些简单操作
- POJ3280 - Cheapest Palindrome(区间DP)
- Android实时监听网络状态(1)
- box-size
- 地牢逃脱 (BFS)
- 常用yum操作命令
- Liunx 特殊权限 suid sgid t
- iOS12
- Java中的静态变量、静态方法问题
- 雷林鹏分享:使用 CSS 显示 XML
- OAuth和OpenID的区别
- c sharp dll
- list的方法、操作
- [转]生成 Excel.dll
- YBT 6 数学基础
- 利用C#改写JAVA中的Base64.DecodeBase64以及Inflater解码
- 15 并发编程-(IO模型)
热门文章
- oculus 安装其他盘方法
- Dockerfile构建python项目
- TensorFlow中使用tf.keras.callbacks.EarlyStopping防止训练过拟合
- 时间序列分析2.X AR与MA
- CLIP 读书笔记
- JRebel for IDEA插件 激活
- idea快捷的输出常用语句
- 安全测试-WEB安全渗透测试基础知识(一)
- Mac新手必看Mac入门基本知识图文教程
- [Err] [Dtf] 1044 - Access denied for user &#39;root&#39;@&#39;localhost&#39; to database &#39;information_schema&#39;