CSP-S 2023 T2 消消乐 题解

前言：关于今年提高

意料之中而又意料之外的挂分。感觉，之前训练了那么久，这些题在考场还是没法做出来。真就，每题都是暴力。这道题反正就是大众部分分 35 pts。我也不是那种可以化悲愤为动力的人，很难受啊，写这篇文章的时候的前一天晚上（考后晚上）哭了一会儿。其实还是对自己有期望的，但讲真期望一直不是很高。其实非常羡慕那些可以化悲愤为动力的人，但是我只能把悲愤吞下去内耗然后继续原地开摆。

个人精神状态不适合在这个场合进行太多讨论；那么既然都过去了，咱还是来看一下这个题怎么做好了！

正文

这道题是 CF1223F 的一道原题。题意大致是，给你一串字符，相邻的两个相同的可以消去（消去之后字符串会接着拼起来），然后就这么一直消；问有多少个连续字串可以这么消完的。

这个题有点像括号序列的匹配。

首先很显然你需要最贪婪地出栈/入栈，那么对于 aaaa 这种你只需要 ()() 而不是 (()) 要不然有可能不是最优。

如果你拿栈去做匹配的话，你可以发现一个性质（其实就是这个性质比较难想），如果在匹配到某一个字符时，这个栈的形态在之前出现过，那么说明这个字符到当时那个地方是可以完全删除的。

那么这个时候你只需要维护一个栈的哈希然后判断之前有没有出现过就行了。

然后这个代码就很简单了。

Code:

#include <iostream>
#include <map>
#include <random>
#include <stack>
#include <chrono>
using namespace std;
using _lx_hash_t = unsigned long long;

map<pair<_lx_hash_t, int>, int> vis;

_lx_hash_t stk_hash; // + 维护 stk, ^ 维护 stk 内的值
char stk[2000006];
int stk_top = 0;
long long ans = 0;

_lx_hash_t sz_hash[2000006], char_hash[256];
inline _lx_hash_t _lx_hash(int stksize, char ch) { return sz_hash[stksize] * char_hash[ch]; }

int main()
{
    string s;
    int n;
    cin >> n >> s;
    s = "$" + s;
    vis[{ 0, 0 }] = 1;
    mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 0; i <= n; i++)
        sz_hash[i] = mt();
    for (int i = 0; i < 256; i++)
        char_hash[i] = mt();
    for (int i = 1; i <= n; i++) {
        // 出栈
        if (stk_top && stk[stk_top] == s[i]) {
            stk_hash ^= _lx_hash(stk_top, s[i]);
            --stk_top;
        } else {
            // 入栈
            stk[++stk_top] = s[i];
            stk_hash ^= _lx_hash(stk_top, s[i]);
        }
        ans = ans + vis[{ stk_hash, stk_top }];
        vis[{ stk_hash, stk_top }]++;
    }
    cout << ans << '\n';
}