洛谷P9753 [CSP-S 2023] 消消乐题解

题目链接：P9753 [CSP-S 2023] 消消乐

题意：

小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两个相邻的元素。

现在，他有一个长度为 $n$ 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。

其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。

小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。

输入格式：

输入的第一行包含一个正整数 $n$，表示字符串的长度。

输入的第二行包含一个长度为 $n$ 且仅由小写字母构成的的字符串，表示题目中询问的字符串。

输出格式：

输出一行包含一个整数，表示题目询问的答案。

数据范围：

$1 \leq n \leq 2 \times 10^6$ ，且询问的字符串仅由小写字母构成

解法一：

这个解法适合从 dp 角度出发的思考的同学（~~比如我~~）。

容易发现，若 $s[i\,..k-1]$ 合法，且 $s[k\,..j]$ 合法，则 $s[i\,..j]$ 合法。

考虑 dp。设 $f_i$ 为以 $i$ 结尾的合法子串的数量，答案即为 $\sum_{i=1}^n f_i$

考场上想到这一步就发现好像没法转移，然后转头去想别的方法了。

哎，性质都没用上怎么就不能转移了？我们考察 $s[k\,..j]$ 是一个以 $j$ 结尾的最小合法串，比如 abba 时的场景

可以发现，此时 $f_j = f_{k-1} + 1$ 。比如 $s[i\,..k-1]$ 为 bbcc ，那 $f_j$ 就是 abba, ccabba, bbccabba ，即 $3$ 。

因此可以得到转移方程 $f_i = f_{g_i - 1} + 1$ ，其中 $g_i$ 为最大能使 $s[g_i\, .. i]$ 合法的下标。

根据 $g_i$ 的定义可知，$s_i = s_{g_i}$ ，因此我们可以像 kmp 一样进行如下操作：

$g_i = i$ 为初值
$g_i \gets g_{g_i}-1$
当 $s_i\ne s_{g_i}$ 时，重复2

上面的伪代码可能有些细节问题，但是应该可以理解。

定义的 $g_i$ 和代码的 g[i] 两者间不要混淆，这句话主要是提醒自己。

可能这个初值显得“不符合定义”，但是可以发现，如果存在 $g_i$ ，在循环数次后，$g_i$ 就会变成正确值。

如果不存在 $g_i$ ，那么让 g[i]=i ，或者说定义 $g_i=i$ 不会影响接下来跳的过程。

下图形象地表示了跳的部分过程（不是我画的）

凭感觉也能发现，这个做法常数比较大，看上去似乎有 $\mathcal{O}(n^2)$。

不过实际上复杂度是 $\mathcal{O}(n|\Sigma|)$ ，即 $\mathcal{O}(26n)$ ，我们会在解法二详细说明（代码也在后面）。

在这里我们就假设这个算法看上去不那么靠谱，如何继续优化。

观察上图，可以发现，这些跳的过程不那么连贯。如果令 $h_i = g_i - 1$ ，则跳的过程就变成了下面的样子：

这样跳的连贯了，可是还无法做到“路径压缩”，原因就在于，每次跳的起点和终点不一定字符相同。

那么我们不妨重新定义 $g(i,c)$ 表示 $s_{g(i,c) + 1} = c$ 且能使 $s[g(i,c) + 1 \, .. i]$ 合法的最大下标。

注意到每次修改的有且只有 $g(i,s_i)$ ，我们不妨把把同一条链上的 $g$ 直接合并为 $g(\mathrm{to}_i)$ ，每次就只需修改 $g(\mathrm{to}_i,s_i)$ 了。

这样我们对于每个 $i$ ，只要查询 $g(\mathrm{to}_i,c)$ ，就可以知道「$c$ + 一个合法串」的位置了。

换句话说，对于每个 $i$ ，我们只要询问 $g(\mathrm{to}_{i-1},s_i)$ 就可以达到之前跳 $g_i$ 的效果了。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e6 + 15))

char s[N];
int n,res,dp[N],g[N][26],to[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s + 1);
    for(int i = 1; i <= n; i++)
    {
        to[i] = i;
        int x = g[to[i - 1]][s[i] - 'a'];
        if(x) { to[i] = to[x - 1]; dp[i] = dp[x - 1] + 1; }
        g[to[i]][s[i] - 'a'] = i; res += dp[i];
    }
    cout << res << '\n';
    return 0;
}

解法二：

相信做过括号序列的同学应该能很快发现这个解法

考虑用一个栈，从 $1$ 到 $n$ 遍历每个字母，如果和栈顶相同就弹出。

考虑用一个数组记录遍历每个位置时栈的情况。可以发现，在一些时候，某些栈的情况是完全相同的

我们称栈情况完全相同这些位置等价，显然会有若干个不同的等价类。

并且可以发现，任意选取两个等价的位置，都能构成一个合法串。

因此答案就是 $\sum_{k \in U}\binom{k}{2}$ ，其中 $k$ 为某个等价类的基数（即元素个数）

统计集合基数，那就要用到哈希了。建议用双哈希，毕竟 $n \le 2\times 10^6$ 。（我只知道自然溢出天天被卡）

时间复杂度 $\mathcal{O}(n\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e6 + 15))

const int base[2] = {13, 7};
const int mod[2] = {1000000009, 998244853};

char s[N]; map<pii,int> mp;
int n,top,stk[N]; pii hsh[N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s + 1); mp[{0, 0}] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(top && s[stk[top]] == s[i])
        {
            --top; ++mp[hsh[stk[top]]]; 
            hsh[i] = hsh[stk[top]];
        }else
        {
            stk[++top] = i;
            hsh[i] = {
                (hsh[i - 1].first + s[i]) * base[0] % mod[0],
                (hsh[i - 1].second + s[i]) * base[1] % mod[1]
            };
            ++mp[hsh[i]];
        }
    }
    int res = 0;
    for(auto S : mp) { int x = S.second; if(x) res += x * (x - 1) / 2; }
    cout << res << '\n';
    return 0;
}

这时候我们就可以分析之前解法一的第一个算法的复杂度了

对于任意等价的 $i,j$ ，显然 $s[i+1\,..j]$ 合法。

因此当我们考虑 $g_{j+1}$ 时，一定会经过这个区间，然后到 $[1,i]$ 中找。

而 $j-i \le \mathcal{O}(|\Sigma|)$ ，因此总复杂度为 $\mathcal{O}(n|\Sigma|)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e6 + 15))

int n,res,f[N],g[N]; char s[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s + 1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = i - 1; j > 0; j = g[j] - 1)
            if(s[i] == s[j]) { g[i] = j; break; }
        if(g[i]) { f[i] = f[g[i] - 1] + 1; res += f[i]; }
    }
    cout << res << '\n';
    return 0;
}