Educational Codeforces Round 72 (Rated for Div. 2) C题

C. The Number Of Good Substrings

Problem Description：

You are given a binary string s (recall that a string is binary if each character is either 0 or 1).
Let f(t) be the decimal representation of integer t written in binary form (possibly with leading zeroes). For example f(011)=3,f(00101)=5,f(00001)=1,f(10)=2,f(000)=0 and f(000100)=4.
The substring sl,sl+1,…,sr is good if r−l+1=f(sl…sr).
For example string s=1011 has 5 good substrings: s1…s1=1, s3…s3=1, s4…s4=1, s1…s2=10 and s2…s4=011.
Your task is to calculate the number of good substrings of string s.
You have to answer t independent queries.
Input
The first line contains one integer t (1≤t≤1000) — the number of queries.
The only line of each query contains string s (1≤|s|≤2⋅105), consisting of only digits 0 and 1.
It is guaranteed that ∑i=1t|si|≤2⋅105.
Output
For each query print one integer — the number of good substrings of string s.

Input

Output

题意：求子串的个数。子串需要满足：长度与二进制数相同。

思路：先求每个1前面的0的个数，分别从1当前位置开始遍历字符串.计算f()函数值是否满足条件（长度==f（）函数值）.

AC代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed  main(){

    int _;

    cin>>_;

    while(_--){

        string s;

        cin>>s;

        int ans=;

        int zero=;

        int len=s.size();

        int sum=;// 计算f函数

        for(int i=;i<len;i++){

            if(s[i]==''){// 1的前面0 的个数

                zero++;

            }else{

                sum=;

                int cnt=;

                for(int j=i;j<len;j++){

                    sum=sum*+s[j]-'';// f()函数值

                    cnt++;// 长度

                    if(sum>=len+){// f()>=字符串长度

                        break;

                    }

                    if(cnt+zero>=sum){ // 满足条件

                        ans++;

                    }

                }

                zero=;

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

Educational Codeforces Round 72 (Rated for Div. 2) C题

Problem Description：

最新文章

热门文章