C. The Number Of Good Substrings————暴力思维（1600 cf）

短命女 2023-08-17 16:21 81阅读 0赞

[https://codeforces.com/problemset/problem/1217/C][https_codeforces.com_problemset_problem_1217_C]

###### 由题意可知： ######

子串长度 = f（sl… sr），就是good Substring,  
因为字符串长度上线是200000 ， 200000 由18个二进制位就可以表示出来。

所以该题就要统计前导零的个数，  
然后遇到1：  
就开始往后跑20位（这里我开大几位），  
每跑一位， 将其转化为十进制，如果这个数 >= (r-l+1)并且<= (r-l+1+前导零的个数)，那么它就是一个good Substring

#include<iostream>
    using namespace std;
    int main ()
    { 
        string s;
        int t ;
        cin >> t;
        while(t--)
        { 
    
            cin>>s;
            int zero = 0;
            long long int ans=0;
    
            for(int i = 0;i <s.size(); i++)
            { 
                if(s[i]=='0')zero++;
                else
                { 
                    long long  n=0;
                    for(int j =i; j<i+20&& j < s.size(); j++)
                    { 
    
                        n = n*2+s[j]-'0';
                        if(n >= j-i+1&&n <= zero+j-i+1)
                        { 
    
                            ans++;
                        }
                        else
                        { 
    
                            break;
                        }
                    }
                    zero=0;
    
    
                }
    
            }
    
            cout<<ans<<endl;
        }
    
    
    }
    #include<iostream>
    using namespace std;
    int main ()
    { 
        string s;
        int t ;
        cin >> t;
        while(t--)
        { 
    
            cin>>s;
            int zero = 0;
            long long int ans=0;
    
            for(int i = 0;i <s.size(); i++)
            { 
                if(s[i]=='0')zero++;
                else
                { 
                    long long  n=0;
                    for(int j =i; j<i+20&& j < s.size(); j++)
                    { 
    
                        n = n*2+s[j]-'0';
                        if(n >= j-i+1&&n <= zero+j-i+1)
                        { 
    
                            ans++;
                        }
                        else
                        { 
    
                            break;
                        }
                    }
                    zero=0;
    
    
                }
    
            }
    
            cout<<ans<<endl;
        }
    
    
    }

[https_codeforces.com_problemset_problem_1217_C]: https://codeforces.com/problemset/problem/1217/C