CF2121G G. Gangsta题解

G. Gangsta

题目翻译

​ 题目给我们一个长度为n的二进制字符串s，我们要计算s所有子数组中函数f值，f（s）的值是二进制字符串中最多的相同字符的个数。

思路

​ 我们考虑如何暴力的做这道题目，定义状态dp[i][j]表示以i为结尾1的个数减去0的个数等于j的子段的数量，ans[i]表示以i为结尾的所有子段做的贡献。我们考虑拓展到i + 1,首先ans[i]的贡献在i + 1时一定会产生，然后考虑新增的贡献，假设此时s[i] == ‘1’，那么原先dp[i][j]中j >= 0的都会新增贡献，s[i] == ‘0’时也是同理。但是这个dp暴力维护的时间复杂度是O（n ^ 2)的。

​ 考虑如何优雅的维护，我们发现遇到1时，实际上原先1的个数减去0的个数为-1的子段变成了为0的子段，我们可以标记一个offset来表示实际上此时为子段中1的个数减去0的个数的位置，我们注意到每次offset只会变动1个位置，我们可以O（1)的维护出大于它的（也就是上面dp中j >= 0）的个数，可以快速算出此时新增的贡献,注意别忘了还要加上ans[i]的贡献（也就是右端点位于上一个位置的贡献）。遇到0时也是同理。实际上这个维护思路我觉得有点类似长链刨分优化dp。时间复杂度O(n)

​ 举个例子，对于10011，初始offset为0，考虑第一个元素1，此时count数组中count[0] += 1,offset -= 1,此时offset为-1，所有count[j] (j > -1)都会做贡献，此时新增贡献1。考虑第二个元素0，此时count[-1] += 1, offset += 1,，此时offset为0，所有count[j] (j < 0)都会做新增贡献，此时新增贡献1，注意此时右端点在位置2的总贡献还要加上右端点为1位置的1，实际总贡献为2。

代码

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
void solve(){
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    s = "@" + s;
    std::vector<int> count(2 * n + 10, 0);
    ll smal = 0;
    ll big = 0;
    int offset = n;
    ll ans = 0;
    ll last = 0;
    for(int i = 1; i <= n; i++){
        ll res = 0;
        if(s[i] == '0'){
            count[offset] += 1;
            smal += count[offset];
            offset += 1;
            big -= count[offset];
            res += smal;
        }
        else{
            count[offset] += 1;
            big += count[offset];
            offset -= 1;
            smal -= count[offset];
            res += big;
        }
        ll now = last + res;
        ans += now;
        last = now;
    }
    std::cout << ans << endl;
}