C. The Number Of Good Substrings（思维&位运算）

不念不忘少年蓝@ 2021-07-16 20:06 323阅读 0赞

[题目][Link 1]

题意：给出一串01串，我们要计算其好串的数量。对于sl,sl+1,…,sr 如果r−l+1=f(sl…sr).则其为好串，f(sl…sr)=从sl开始的二进制数值.

思路：直接暴力+位运算，观察一下就能发现我们要求的字符串长度只有2*1e5，而一个二进制数当其长度大于20的话已经大于了2*1e5，所以我们只需全部遍历一遍，每当发现一个1后向后遍历20位即可。而对于每一次是否能形成一个好串只需判断这个位置的前导零的个数+这个数往后的长度是否大于从这个数往后遍历一定长度由二进制转换成十进制的值，模拟一下二进制转换成十进制即可。

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[Max];
    int Mod = 1e9 + 7;
    int sum[Max];
    int main()
    { 
    	FAST;
    	int t;cin >> t;
    	while (t--)
    	{ 
    		string str;cin >> str;
    		str.insert(str.begin(), '-');
    		int n = str.size() - 1, s = 0;
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (str[i] == '0')s++;
    			else
    			{ 
    				sum[i] = s;
    				s = 0;
    			}
    		}
    		int ans = 0;
    		for (int i = 1;i <= n;i++) { 
    			if (str[i] == '0')continue;
    			ll ss = 0;
    			for (int j = i;j <= min(i + 20, n);j++)
    			{ 
    				ss *= 2;
    				if (str[j] == '1')
    					ss++;
    				if (ss <= sum[i] + 1+j-i)ans++;
    			}
    		}
    		cout << ans << endl;
    	}
    }

[Link 1]: https://codeforces.ml/contest/1217/problem/C