The Number Of Good Substrings</center>
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⋅1e5), consisting of only digits 0 and 1.

It is guaranteed that ∑i=1t|si|≤2⋅1e5.

Output
For each query print one integer — the number of good substrings of string s.

Example
input
4
0110
0101
00001000
0001000
output
4
3
4
3

Problem solving:
这道题真的很有意思。它就是给你一个只有0跟1组成的字符串，然后问在它的子串中有多少个串，以二进制形式表示的值跟它的长度是相等的。这里有一点我们需要知道就是你可以在前面补零。所以我们可以直接遍历字符串，找到1的时候在处理。并且2的20次方就已经超过了2e5，所以我们只需要处理到最多20位之后就不会有满足情况的子串出现了。这一步很重要。
首先我们在遍历的时候就处理0的个数。然后直到我们遇到一，以这个1为起点，往后延申最多20位，用你构造出来的二进制形式的值跟当前子串的长度的差值跟前面0的个数的关系。如果0的个数够多，那么就一定可以有一个满足情况的子串出现。因为我们往前补不论多少0，结果都是不会变的。
Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int    n;
    string s;
    cin >> n;
    while (n--)
    {
        cin >> s;
        int mid = 0, ans = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '0')//遇到1之前累计0的个数
                mid++;
            else
            {
                ans++;//1本身就满足，所以先加一
                int cnt = 1;
                for (int j = i + 1; j < min(i + 20, (int) s.size()); j++)
                {
                    if (s[j] == '0')//如果新加的二进制位是0，在原来的值的基础上乘2就行
                        cnt *= 2;
                    else//如果是1，还得加上。这就类似于位运算的一个模拟
                        cnt = cnt * 2 + 1;  \
                    if (mid >= (cnt - j + i - 1))//如果0的个数大于当前子串的值与当前子串的长度的差值，说明这个可以构造成功，答案加一
                        ans++;
                }
                mid = 0;//每次遇到1之后就把之前记录的0的个数清空
            }
        }
        cout << ans << endl;
    }
}
赏