P9753 CSP-S2022 消消乐

· · 个人记录

提供一个 \Theta(n) 的做法

详解，一步一步来

由题意，我们可以发现，如果一个串是合法的，消除策略肯定可以能消就消，类似于括号序列，因此可以类比括号序列用栈做。

具体的，我们把字符依次入栈，如果相同就消除，不同就压栈。合法串的充要条件是最后的栈是空栈。

因此我们可以枚举子串然后check

ll check(ll l,ll r)
{
    cnt=0;
    for(int i=l;i<=r;i++)
    {
        if(cnt&&q[cnt]==s[i]) cnt--;
        else q[++cnt]=s[i];
    }
    return (cnt==0);
}

for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
            ans+=check(l,r);

我们可以发现，上面那个过程可以被优化：

对于一个相同的 l ，r+1 最后对应的栈就是 r 最后对应的栈再加入一个数，因此可以直接继承前面的。

for(int l=1;l<=n;l++)
{
    cnt=0;
    for(int r=l;r<=n;r++)
    {
        char x=s[r];
        if(cnt&&q[cnt]==x) cnt--;
        else q[++cnt]=x;
        if(!cnt) ans++;
    }
}

这一挡是随机的分。

显然，你先枚举 r 再枚举 l 也没啥问题，这样就是对于同一个 r 把栈往前推。

然后你会发现，你只需要找到第一个 l 使栈空就可以了

我们记录每一个 i 结尾的答案记为 dp_i

那你找到了那个 l ，可以得出：

dp_r=dp_{l-1}+1;

随机数据应该能过，洛谷 60pts

for(int r=1;r<=n;r++)
{
    cnt=0;
    for(int l=r;l>=1;l--)
    {
        if(cnt&&q[cnt]==s[l]) cnt--;
        else q[++cnt]=s[l];
        if(!cnt)
        {
            dp[r]=dp[l-1]+1;
            ans+=dp[r];
            break;
        } 
    }
}

上面那个条件可以转化为：

找到每个 r 的最大 l ，使 [l,r] 能消完。

考虑怎样快速算。

先考虑使 l=1 往后入栈 ，找到每个 r 的前一个与它深度相同的点。

但这样显然不对，小样例都能hack，因为入栈前你不能确定栈底到这个位置组成的字符串是不是相同。

用 map 吗？显然不可以，2e6维的 map 肯定不可以接受。

这时候你终于想到这是一个字符串题，需要一个字符串算法。

看上面那个东西，是不是可以用 trie树 统计。

具体的：

最大的 l 就是上一个与目前相同的栈底到这个位置组成的字符串对应的编号

这样就做完了，代码有一些细节。

因为每次加入一个点，所以复杂度就是 \Theta(n)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

#define ll long long
#define N 2010000
#define pb push_back

using namespace std;

string s;
int n;
int fa[N],ch[N][27],tot,ji[N];
char f[N];
ll dp[N],ans;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    cin>>s;
    s=' '+s;
    ll p=0;
    for(int i=1;i<=n;i++)
    {
        ll x=s[i]-'a'+1;
        if(f[p]==s[i]) 
        {
            p=fa[p];
            dp[i]=dp[ji[p]]+1;
            ji[p]=i;
            ans+=dp[i];
            continue;
        }
        if(!ch[p][x])
        {
            ch[p][x]=++tot;
            fa[tot]=p;
            f[tot]=s[i];
            p=tot;
            ji[p]=i;
            continue;
        }
        p=ch[p][x];
        dp[i]=dp[ji[p]]+1;
        ji[p]=i;
        ans+=dp[i];
    }
    cout<<ans<<"\n";
    return 0;
}