[CSP-S 2023] 消消乐

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

把前缀消除后的栈状态建成 trie，统计相同状态对来计算可消除子串数。

OJ: luogu

题目 ID: P9753

难度:普及+/提高

标签:字符串栈Trie前缀状态

日期: 2026-07-06 08:46

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定一个只含小写字母的字符串。一次操作可以删除两个相邻且相同的字符，删除后两侧会拼接起来。

如果一个字符串经过若干次这样的操作后可以变成空串，就称它是可消除的。要求统计原串中有多少个非空连续子串是可消除的。

思路

小数据可以直接枚举每个子串，再用栈模拟消除过程：

cpp
// brute.cpp：小数据暴力解，枚举所有子串并用栈模拟相邻相同字符消除。
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

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;

    long long 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(n2)O(n^2) 个，而 n 最大为 2 * 10^6，必须换一个角度统计。

设 R(i) 表示前缀 s[1..i] 经过栈消除后剩下的状态。一个子串 s[l..r] 可消除，当且仅当：

text
R(l - 1) = R(r)

原因是：从前缀 l-1 的消除状态继续读入 s[l..r]，如果中间这段能完全抵消，读完后的状态就会回到原来的状态；反过来，如果状态相同，中间这段对消除栈没有净影响，也就可以消成空串。

因此问题变成：扫描所有前缀，统计相同消除状态出现了多少对。

不能真的把每个栈状态保存成字符串。我们把所有出现过的栈状态建成一棵 trie：

  • 根节点表示空栈；
  • 如果当前字符和栈顶相同，就回到父节点，表示弹栈；
  • 否则从当前状态沿这个字符走到子节点，表示压栈；
  • 每到达一个状态 cur，答案加上这个状态以前出现过的次数。

这样每个前缀只会进行一次压栈或弹栈，所有状态节点数量不超过 n+1。

代码

cpp
// main.cpp：把每个前缀消除后的栈状态放入 trie，统计相同状态出现次数。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000005;

int n;
string s;

int parent_node[MAXN];      // trie 中每个状态的父状态
int first_edge[MAXN];       // 状态向后追加一个字符后的转移链表
int to_node[MAXN], next_edge[MAXN];
char node_char[MAXN], edge_char[MAXN];
long long seen_count[MAXN]; // 每个消除后状态已经出现过多少次
int node_cnt, edge_cnt;

int get_child(int u, char c) {
    for (int e = first_edge[u]; e != 0; e = next_edge[e]) {
        if (edge_char[e] == c) {
            return to_node[e];
        }
    }

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

    edge_cnt++;
    to_node[edge_cnt] = node_cnt;
    edge_char[edge_cnt] = c;
    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;

    long long 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);
        }

        answer += seen_count[cur];
        seen_count[cur]++;
    }

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

复杂度

每个字符只处理一次。trie 中每个节点最多有 26 条字符边，代码用邻接链表查找子边，单次查找最多检查 26 条边。

时间复杂度为 O(26n)O(26n)，可视为 O(n)O(n)；空间复杂度为 O(n)O(n)。

总结

本题的关键是把“某个子串能否消空”转成“两个前缀消除状态是否相同”。栈负责得到前缀状态，trie 负责给每一种栈状态一个稳定编号，最后用出现次数统计答案。