[Codeforces 1217.C] The Number Of Good Substrings

原题

思路

  1. 二进制长度与数值大小的关系问题。
    1. 考虑给一个二进制数增加一个MSB (Most Significant Bit),显然数值增长的速度(接近指数)远超过长度增长的速度(线性)。
    2. 所以一个good string,高位必然有大量连续的0,来弥补长度的损失。例如长度为8,表示8的二进制数:0b0000_1000。可以以此为切入点。
  2. 考虑暴力的方式。不加优化,遍历每个子串是否符合要求的时间复杂度为$O(n^2)$,对于$10^5$量级的数据显然过大。
    1. 字符串中连续0的个数象征着对长度的弥补能力。
    2. 考虑以s[i]结尾的子串:
      1. 如果s[i] == '1',那么"1"即是一个好子串;反之,"0"则不是。
      2. 我们关心字符串中的'1',因为只有'1'对数值的增长有贡献,然后我们再通过连续'0'的数量判断是否足以将长度补偿至好子串。
      3. 可以用增量的思路去想,每次去找下一个左边的'1',同时考虑中间连续'0'的个数,再结合简单的位运算,即可找出所有以s[i]结尾的好子串。
      4. 如果离线计算各位置连续'0'的数量,那么计算s[i]结尾的好子串数量最差只需要$O(\log n)$的复杂度(此时整个数组的长度都不足以补偿数值的增长了)。
  3. 故优化后的暴力搜索只需要$O(n\log n)$的时间复杂度。

Code

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
* https://codeforces.com/problemset/problem/1217/C
* C. The Number Of Good Substrings
*/
#include <bits/stdc++.h>
using namespace std;
/*
* Solution goes here.
*/
int log2(int x) {
if (x <= 1) return 0;
return 1 + log2(x>>1);
}
int numberOfGoodSubstrings(string& s) {
int n = s.size();
vector<int> contZeros(n+1);
int count = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '0') ++count;
else count = 0;
contZeros[i+1] = count;
}
// consider the number of good substrings end at index i
int res = s[0] == '1' ? 1 : 0;
for (int i = 1; i < n; ++i) {
int max_len = i + 1;
int left_flag = max(0, i - log2(max_len));
int j = i;
int x = 0;
while (j >= left_flag) {
if (s[j] == '1') {
x += 1<<(i-j);
if (x > max_len) break;
if (contZeros[j] >= x-(i-j+1)) ++res;
}
j -= contZeros[j] + 1;
}
}
return res;
}