专栏文章

教练我也要玩崩铁

LLuoFeng_Nanami
P14060题解参与者 14已保存评论 20

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
20 条
当前快照
1 份
快照标识符
@mintt4qi
此快照首次捕获于
2025/12/02 08:14
3 个月前
此快照最后确认于
2025/12/02 08:14
3 个月前
查看原文
我们不妨假设每次删去的，都是极长子串的第一个字符。
对于一个合法的串，显然它的所有前缀都是合法的。
考虑一个不合法的，以 11 开头的串：消到某个时刻它的开头是 00，我们在原串中找到这个 00 的位置，把这段前缀拉出来看：
这个串形如 1…01\dots0，并且 11 的个数小于 00 的个数。这是因为，在 11 消完的时刻及之前，最后的一段 00 并不会被消完，而每次被消去的 00 和 11 的个数是相等的。
并且我们还知道，从这个 00 开始，之后的串都不合法。所以，我们就推得了临界情况：第一个 00 的个数大于 11 的个数的前缀之前，都是合法的，这个前缀及之后，都是不合法的。同理，我们也可以推出以 00 开头的串的结论。
接下来我们考虑如何刻画这个性质：
记 00 位的权值为 −1-1，11 位的权值为 11，记录第 ii 个位置上的前缀和 sumisum_i，和后面第一个 sumx>sumi−1sum_x > sum_{i - 1} 的位置 xx（即 x∈[i,n]x \in [i, n] 中第一个 xx，使串 [i,x][i, x] 中 11 个数大于 00 个数）为 aia_i，第一个 sumx<sumi−1sum_x < sum_{i - 1} 的位置 xx（即 x∈[i,n]x \in [i, n] 中第一个 xx，使串 [i,x][i, x] 中 00 个数大于 11 个数）为 bib_i。特别的，若 aia_i 或 bib_i 不存在，我们认定其为 n+1n + 1（即后面都合法）。
所以若 Si=1S_i = 1，以 ii 为开头的合法串有 ai−ia_i - i 个，若 Si=0S_i = 0，以 ii 为开头的合法串有 bi−ib_i - i 个。
求 aa 数组和 bb 数组可以用单调栈在 O(n)O(n) 的时间内求出。
codeCPP
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';
}

评论

共 20 条评论，欢迎与作者交流。

正在加载评论...