2023 消消乐 · 方案一枚举区间加栈

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1023 字

字符串 s（长度 n）

2023
栈

正文

// CSP-S 2023 复赛 T2 · 消消乐（方案一：枚举区间 + 栈判定，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2023B
// 题意：字符串 s（长度 n）。若子串可"从外向内两两相同地消除"
//       （相邻同字符可消除，反复），称可消子串。求可消子串个数。
// 思路（区间枚举 + 栈）：
//   对每个子串 [l, r]：用栈模拟消除——逐字符入栈，栈顶相同则弹出；
//   结束时栈空 = 可消。三重循环 O(n^3)：n ≤ 800 的部分分（测试点
//   1~7）约 5e8 稍紧，把内层消除做成增量（固定 l，r 递增时共享栈）
//   → O(n^2)，n ≤ 800 稳过，n = 8000 的点也够呛但值得。
// 复杂度：O(n^2)（固定左端点的增量栈）。
// 易错点：
//   1. 栈回溯：固定 l 扫 r 时栈是增量的，换 l 必须重置；
//   2. 可消 = 栈恰好空，不是栈中剩下的可配对；
//   3. 计数用 long long（n = 2e6 时答案 ~2e12）。
#include <cstdio>
#include <cstring>
using namespace std;

int n;
char s[2000005];

int main() {
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    scanf("%d%s", &n, s + 1);
    long long ans = 0;
    static char stk[2000005];
    for (int l = 1; l <= n; l++) {
        int top = 0;
        for (int r = l; r <= n; r++) {
            if (top > 0 && stk[top] == s[r]) top--;
            else stk[++top] = s[r];
            if (top == 0) ans++;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

2023 消消乐 · 方案一 枚举区间加栈

正文

CSP-S 标程 · 复赛真题的其它内容

2023 消消乐 · 方案一枚举区间加栈