【思维题】Codeforce 1217C The Number Of Good Substrings

128 阅读 0 评论 85 点赞

我是靠谱客的博主整齐毛巾，这篇文章主要介绍【思维题】Codeforce 1217C The Number Of Good Substrings，现在分享给大家，希望可以做个参考。

这段时间要沉迷刷题一段时间了，就让CSDN陪我一起吧！

一、题目大意

题目的大致意思是，我们有一个二进制的字符串，并定义满足一下条件的二进制字符串为好串：

该二进制串所表示的十进制数，正好等于该二进制串的位数（可以包含前导零）
求问给定的二进制字符串中，它有多少个满足好串定义的子串。

二、题目思路以及AC代码

这道题我刚开始的思路是字符串匹配，可以用KMP尝试一下，也是可以做的，但是就是会超时，但答案是没有错误的。

后来无奈，就去网上找解答，发现果然大佬还是大佬。

大致的思路是这样的，我们从左到右扫描字符串，同时记录前导零的个数（因为当二进制长度不够的时候可以用前导零补充），当扫描到1的时候，开始进行匹配，利用后续的字符以及此时具有的前导
零的个数，可以得到当前这个1之后的所有好子串。

我举个例子方便大家理解。

比如我们要计算二进制串 010010111。那么我们从左至右扫描，下标从0开始，则扫描到下标为1的时候停止，此时具有1个前导零。

那么该下标为1的字符可以产生的好子串首先是1，它只需要1个长度，所以不需要前导零补充。
然后是2，它需要两个长度，也不需要前导零补充
然后是4，它需要4个长度，而从下标为1开始到下标为3，长度是3，但是有一个前导零，所以也满足
然后是9，它需要9个长度，但加上前导零总共也就5个长度，所以不满足条件。
…

有了上述的例子，相信就很好理解了，下面给出AC代码：

复制代码

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
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main() {

    int T;
    cin >> T;

    while (T--) {
        string s;
        cin >> s;

        int len = s.length();
        int pre = 0;                        // 记录当前的前导零
        int ans = 0;
        for (int i=0;i<len;i++) {
            if (s[i] == '0') pre++;
            else {
                int r = i;                  // 记录遍历到哪里
                int cur = 1;                // 记录当前要匹配的数
                for (int j=1;j<=18;j++) {
                    if (cur <= pre+(r-i+1)) ans++;
                    if (r+1 >= len) break;
                    cur = cur*2 + (s[++r] - '0') ;
                }
                pre = 0;
            }
        }

        cout << ans << endl;
    }

    return 0;
}