C. The Number Of Good Substrings
题意
给出一个01串
问有多少子串满足
r-l+1=十进制的值
即长度=子串所表示的十进制数大小
如011=3 长度为3 且011的值为3 (右侧开始最低位)
题解
因为2^20>最大字符串长度2e5可以剪枝
意思是最长能满足要求的01串不会超过20位
因为2^20>整个字符串长度
预处理每个1之前的0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| # include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;cin>>t;
while(t--){
string s;cin>>s;int n=s.size();
int zero=0;int per[s.size()+5];
for(int i=0;i<n;i++){
if(s[i]=='1'){per[i]=zero;zero=0;}
else zero++;
}int ans=0;
for(int i=0;i<n;i++){
if(s[i]=='0')continue;
int sum=0;int p;
for(p=i;p<min(n,i+20);p++){
if(s[p]=='1')sum=(sum<<1)+1;
else sum<<=1;
if(sum<=p-i+1+per[i])ans++;
}
}
cout<<ans<<endl;
}
}
|