[CSP-S 2023] 消消乐

GitHub跳转原题关系图返回列表

把每个前缀消除后的栈状态做成 trie，可消除子串数等于相同状态的前缀对数。

OJ: luogu

题目 ID: P9753

难度:提高+/省选-

标签:字符串数据结构模拟数学

创建: 2026-07-06 08:46

更新: 2026-10-07 10:45

形式化题目

给定一个长度为 $n$ 、只含小写字母的字符串 $s$ 。

一次操作可以删去一对相邻且相同的字符，剩下的字符拼接在一起。如果一个字符串能经过若干次操作变成空串，就称它是可消除的。

求 $s$ 的非空连续子串中，可消除的子串个数。

样例 $1$ 的 $s=\texttt{accabccb}$ ，可消除的子串是 cc、acca、cc、bccb、accabccb，共 $5$ 个。

暴力解法

思路

直接枚举所有非空连续子串，对每个子串模拟一遍消除：从左到右扫描，栈顶与当前字符相同就弹栈，否则压栈。扫描完后栈为空即为可消除。

模拟时不用真的反复找“相邻相同对”，因为消除顺序不影响最终结果，一次线性扫描的栈模拟就是最终结果。

代码

cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:36
 * update_at: 2026-10-01 22:36
 */
// brute.cpp：小数据暴力解，枚举所有子串并用栈模拟相邻相同字符的消除。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;   // 暴力只服务小数据，n 取到 100 左右

int n;
string s;

// 判断 s[left..right] 能否被完全消除：扫描一遍，栈顶与当前字符相同就弹栈。
bool can_delete(int left, int right) {
    string st;

    for (int i = left; i <= right; i++) {
        if (!st.empty() && st.back() == s[i]) {
            st.pop_back();
        } else {
            st.push_back(s[i]);
        }
    }

    return st.empty();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;

    // 依次枚举所有非空连续子串，能消除就计数。
    ll answer = 0;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            if (can_delete(l, r)) {
                answer++;
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

枚举子串 $O(n^2)$ 个，每个模拟一次 $O(n)$ ，总时间复杂度 $O(n^3)$ ，空间 $O(n)$ 。

瓶颈

$n$ 最大 $2\times10^6$ ， $O(n^3)$ 绝对不可行。真正的困难是：子串数量本身就是 $O(n^2)$ ，所以必须一次性统计，不能逐个子串判断。

正解

思路

前缀消除状态

对每个前缀 $s[0..i]$ 做一次栈模拟，得到的栈内容记为 $R(i)$ 。 $R(i)$ 一定是一个没有相邻相同字符的串（否则还能继续消）。

比如 $s=\texttt{accabccb}$ ：

$i$	$s[i]$	$R(i)$
$-1$	无	$\varepsilon$
$0$	`a`	`a`
$1$	`c`	`ac`
$2$	`c`	`a`
$3$	`a`	$\varepsilon$
$4$	`b`	`b`
$5$	`c`	`bc`
$6$	`c`	`b`
$7$	`b`	$\varepsilon$

关键观察：可消除子串就是两端状态相同的区间

断言：子串 $s[j+1..i]$ 可完全消除，当且仅当 $R(j)=R(i)$ 。

证明。记 $\rho(x)$ 为串 $x$ 消除后的结果。栈模拟的可结合性给出

\rho(xy)=\rho(\rho(x)\,y).

（ $\Rightarrow$ ）若 $\rho(s[j+1..i])=\varepsilon$ ，则

R(i)=\rho(s[0..i])=\rho\bigl(s[0..j]\cdot s[j+1..i]\bigr)=\rho\bigl(R(j)\bigr)=R(j).

（ $\Leftarrow$ ）反过来，把每个字母看成自己的逆元（ $x\cdot x=\varepsilon$ ），约化后的串恰好构成一个群，乘法就是“拼接后约化”。于是

\rho\bigl(R(j)\cdot s[j+1..i]\bigr)=R(j)

两边左乘 $R(j)$ 的逆元，得到 $\rho(s[j+1..i])=\varepsilon$ 。 $\blacksquare$

换句话说：从栈 $R(j)$ 出发处理 $s[j+1..i]$ ，最后又回到 $R(j)$ ，就说明这一段自己在空栈上也一定消得干干净净。

于是问题变成“数相同状态的对”

设状态 $u$ 在所有前缀中出现了 $c_u$ 次，答案就是

\sum_u \binom{c_u}{2}.

所以只要能给每个 $R(i)$ 一个“身份编号”，并统计每个编号出现次数，就能 $O(n)$ 求出答案。

用 trie 表示消除状态

难点在于：从 $R(i-1)$ 到 $R(i)$ 有两条路——

栈顶与 $s[i]$ 相同：弹栈， $R(i)$ 就是 $R(i-1)$ 去掉栈顶；
否则压栈， $R(i)$ 是 $R(i-1)$ 后面接上 $s[i]$ 。

所以状态之间是父子关系，天然构成一棵树：把每个状态看成结点，parent_node[u] 是它去掉栈顶字符后的状态，node_char[u] 是它的栈顶字符。

“在状态 $u$ 后追加字符 $c$ ”就是找 $u$ 的孩子中栈顶字符为 $c$ 的那个结点；没有就新建。根结点 $0$ 表示空栈。这样一个状态最多 $26$ 个孩子，查找很快。

最后扫一遍：维护当前状态 cur，每处理一个字符就转到新状态，答案累加 seen_count[cur]，再把它加一。样例中的过程：

$i$	$s[i]$	新状态	本次新增
$0$	`a`	`a`	$0$
$1$	`c`	`ac`	$0$
$2$	`c`	`a`	$1$ （`cc`）
$3$	`a`	$\varepsilon$	$1$ （`acca`）
$4$	`b`	`b`	$0$
$5$	`c`	`bc`	$0$
$6$	`c`	`b`	$1$ （`cc`）
$7$	`b`	$\varepsilon$	$2$ （`bccb`、`accabccb`）

合计 $5$ ，与样例一致。

代码

cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:36
 * update_at: 2026-10-01 22:36
 */
// main.cpp：把每个前缀消除后的栈状态存成 trie 结点，用“同一状态出现次数”统计可消除子串。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2000005;   // n <= 2e6

int n;
string s;

// 每个结点代表一个“消除栈状态”，结点 0 表示空栈。
// parent_node[u]：状态 u 去掉栈顶字符之后的状态；
// node_char[u]：状态 u 的栈顶字符（只有非根结点才有意义）。
int parent_node[MAXN];
char node_char[MAXN];

// 孩子用链式前向星存：一个状态最多有 26 个孩子（追加不同字符各一个）。
int first_edge[MAXN], to_node[MAXN], next_edge[MAXN];
int node_cnt, edge_cnt;

ll seen_count[MAXN];   // seen_count[u]：状态 u 作为前缀消除结果出现过的次数

// 在状态 u 后追加字符 c 得到的状态；已经存在就复用，避免重复建结点。
int get_child(int u, char c) {
    for (int e = first_edge[u]; e != 0; e = next_edge[e]) {
        int v = to_node[e];
        if (node_char[v] == c) {
            return v;
        }
    }

    node_cnt++;
    parent_node[node_cnt] = u;
    node_char[node_cnt] = c;

    edge_cnt++;
    to_node[edge_cnt] = node_cnt;
    next_edge[edge_cnt] = first_edge[u];
    first_edge[u] = edge_cnt;

    return node_cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;

    ll answer = 0;
    int cur = 0;       // 当前前缀消除后的状态，0 表示空栈
    seen_count[0] = 1; // 空前缀是一个合法起点

    for (int i = 0; i < n; i++) {
        char c = s[i];

        if (cur != 0 && node_char[cur] == c) {
            // 栈顶字符和新字符相同，两者一起消去，状态退到父亲。
            cur = parent_node[cur];
        } else {
            // 否则把新字符压栈，得到一个新状态。
            cur = get_child(cur, c);
        }

        // 子串 (j, i] 可完全消除，当且仅当前缀 j 与前缀 i 的消除状态相同。
        answer += seen_count[cur];
        seen_count[cur]++;
    }

    cout << answer << '\n';
    return 0;
}

复杂度

时间复杂度： $O(26n)$ 。每个字符要么压栈要么弹栈，压栈时在至多 $26$ 个孩子里查找。
空间复杂度： $O(n)$ 。每个前缀最多新建一个结点，结点总数不超过 $n+1$ 。

总结

这题的关键是把“这个子串能不能消除”翻译成“两个前缀的消除状态是否相同”：

s[j+1..i]\text{ 可消除}\iff R(j)=R(i).

于是问题从“逐个子串判定”变成“统计相同状态的对数”，复杂度从 $O(n^3)$ 降到 $O(n)$ 。

状态本身是一棵由“压栈 / 弹栈”生成的树，用 trie 表示后，转移就是找孩子或退到父亲，不需要真的维护字符串。

值得注意的是这个消除过程背后是一个群结构（每个字母是自己的逆元），这正是断言里“左乘可消去”的来源。

本文的 main.cpp 已用栈模拟的 brute.cpp 对拍 $600$ 组随机数据（含 $2$ 字母表与 $26$ 字母表），并对二元字母表上长度不超过 $8$ 的全部 $510$ 个串做了穷举核对，题面样例通过。

P9753 [CSP-S 2023] 消消乐

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

text

1
28
accabccb

输出 #1

text

说明/提示

【样例 1 解释】

一共有 $5$ 个可消除的连续子串，分别是 cc、acca、cc、bccb、accabccb。

【样例 2】

见选手目录下的 game/game2.in 与 game/game2.ans。

【样例 3】

见选手目录下的 game/game3.in 与 game/game3.ans。

【样例 4】

见选手目录下的 game/game4.in 与 game/game4.ans。

【数据范围】

对于所有测试数据有： $1 \le n \le 2 \times 10^6$ ，且询问的字符串仅由小写字母构成。

测试点	$n\leq$	特殊性质
$1\sim 5$	$10$	无
$6\sim 7$	$800$	无
$8\sim 10$	$8000$	无
$11\sim 12$	$2\times 10^5$	A
$13\sim 14$	$2\times 10^5$	B
$15\sim 17$	$2\times 10^5$	无
$18\sim 20$	$2\times 10^6$	无

特殊性质 A：字符串中的每个字符独立等概率地从字符集中选择。

特殊性质 B：字符串仅由 a 和 b 构成。