P9753 [CSP-S 2023] 消消乐 题解

· · 题解

更好的阅读体验

考前天天祈祷不考串串和数数结果靠这个翻盘好好好。

为什么都说 D 比 B 简单。

题目传送门

Solution

按照一般的计数 dp 的状态设计，我们不妨设 f_i 为以 i 为右端点的合法子串个数。

最后答案是 \sum_{i=1}^{n} f_i。

考虑合法的子串有哪几种形式，不妨设 A,B 均合法，以及单个字符 c。

那么合法的字串只可能为一下四种形式：

  1. A
  2. AB
  3. cAc
  4. cc

其他所有的都可以规约到这四种。

设 lst_i 为最大的 j 满足 s_{[i,j]} 是合法子串的 j。

那我们的转移便是 f_i = f_{lst_i - 1} + 1。

加 1 是因为要把自己算上，前面的 f_{lst_i - 1} 是在算第二类子串的个数。

对于 lst_i 的计算直接采取暴力跳的方式即可，算法是通过左右相同的上一个相同字符的前一个的保存值转移的，如果上一个不一样，就需要继续向前匹配，如此重复，最多到字符集大小就会出现一次匹配，总复杂度是 O(26n)。

code

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e6 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n;
string s;
LL f[N];
int lst[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> s;
    s = " " + s;
    rep(i, 1, n) {
        lst[0] = -1;
        if(s[i] == s[i - 1]) lst[i] = i - 1;
        else {
            lst[i] = -1;
            int j = i - 1;
            while(lst[j] != -1) {
                j = lst[j] - 1;
                if(s[i] == s[j]) {
                    lst[i] = j;
                    break;
                }
            }
        }
    }
    rep(i, 1, n) if(lst[i] != -1) f[i] = f[lst[i] - 1] + 1;
    LL res = 0;
    rep(i, 1, n) res += f[i];
    cout << res << '\n'; 
    return 0;
}