洛谷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;
}