教练我也要玩崩铁

LuoFeng_Nanami · 2025-09-21 20:45:28 · 题解

我们不妨假设每次删去的，都是极长子串的第一个字符。

对于一个合法的串，显然它的所有前缀都是合法的。

考虑一个不合法的，以 1 开头的串：消到某个时刻它的开头是 0，我们在原串中找到这个 0 的位置，把这段前缀拉出来看：

这个串形如 1\dots0，并且 1 的个数小于 0 的个数。这是因为，在 1 消完的时刻及之前，最后的一段 0 并不会被消完，而每次被消去的 0 和 1 的个数是相等的。

并且我们还知道，从这个 0 开始，之后的串都不合法。所以，我们就推得了临界情况：第一个 0 的个数大于 1 的个数的前缀之前，都是合法的，这个前缀及之后，都是不合法的。同理，我们也可以推出以 0 开头的串的结论。

接下来我们考虑如何刻画这个性质：

记 0 位的权值为 -1，1 位的权值为 1，记录第 i 个位置上的前缀和 sum_i，和后面第一个 sum_x > sum_{i - 1} 的位置 x（即 x \in [i, n] 中第一个 x，使串 [i, x] 中 1 个数大于 0 个数）为 a_i，第一个 sum_x < sum_{i - 1} 的位置 x（即 x \in [i, n] 中第一个 x，使串 [i, x] 中 0 个数大于 1 个数）为 b_i。特别的，若 a_i 或 b_i 不存在，我们认定其为 n + 1（即后面都合法）。

所以若 S_i = 1，以 i 为开头的合法串有 a_i - i 个，若 S_i = 0，以 i 为开头的合法串有 b_i - i 个。

求 a 数组和 b 数组可以用单调栈在 O(n) 的时间内求出。

:::info[code]

cin >> _;
while(_--) {
    cin >> str + 1;
    int n = strlen(str + 1);
    ll ans = 0;
    F(i, 1, n) 
        sum[i] = sum[i - 1] + (str[i] == '0' ? -1 : 1);
    F(i, 0, n) {
        while(top && sum[i] > sum[stk[top]]) 
            a[stk[top--]] = i;
        stk[++top] = i;
    } 
    while(top) a[stk[top--]] = n + 1;
    F(i, 0, n) {
        while(top && sum[i] < sum[stk[top]]) 
            b[stk[top--]] = i; 
        stk[++top] = i;
    } 
    while(top) b[stk[top--]] = n + 1;
    F(i, 1, n) { 
        if(str[i] == '0') 
            ans += (ll)(a[i - 1] - i);
        else ans += (ll)(b[i - 1] - i);
    }
    cout << ans << '\n';
}

:::