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

harmis_yz · 2023-10-24 17:08:40 · 个人记录

分析

弱智题。

和这题很像。

想到 DP。定义状态函数 \mathit{f}_{i,j} 表示区间 [i,j] 中的答案。这玩意直接暴力 O(n^3) 算区间 DP，能有 35 分。

考虑优化，如果定义 \mathit{f}_{i,j}=0/1 表示子串 [i,j] 能否是一个匹配的，则能用栈搞到 O(n^2)。能有 50 分。

优化不下去了。

放弃这个思路，考虑把状态函数转移到一维的。再重新定义一下：\mathit{f}_{i} 表示以 i 为某个字串开头时，能得到的匹配的子串数量。有转移方程：\mathit{f}_{i}=\mathit{f}_{j+1}+1，其中 [i,j] 是一个匹配的子串。必须保证 j 是 i 右边的第一个能够匹配的位置，因为在转移方程中的 +1 代表区间 [i,j] 的一个匹配子串贡献。若 j 不是，可能出现如 abbaabba 的情况（i=1,j=8)。可以自己理解一下。

对于找第一个 j，如果暴力，可以得到代码：

il void solve(){
    cin>>n>>s;int ans=0;
    for(re int l=0;l<n;++l){
        stack<char> st;
        for(re int r=l;r<n;++r){
            if(st.empty()){
                st.push(s[r]);
                continue;
            }
            char now=st.top();
            if(now==s[r]) st.pop();
            else st.push(s[r]);
            if(st.empty()) vis[l][r]=1;
        }
    }
    for(re int i=n-1;i>=0;--i){
        for(re int j=i+1;j<n;++j){
            if(vis[i][j]){
                f[i]=f[j+1]+1;break;
            }
        }
    }
    for(re int i=0;i<n;++i) ans+=f[i];
    cout<<ans; 
}

很好的一个代码，\mathit{vis} 竟然和第一次优化时候的 \mathit{f} 的作用一样。

考虑预处理每一个 i 对应的 j。定义 \mathit{nxt}_{i} 表示 i 右边第一个 j，使得子串 [i,j] 能够匹配。这里有一个明显但是我觉得不明显的东西，就是 \mathit{nxt}_{i} \ge \mathit{nxt}_{i+1}+1。其中保证 \mathit{nxt}_{i+1} 有答案且 s_i \ne s_{i+1}。那么我们就可以从 i+1 一直跳，每次跳到 \mathit{nxt}_{j}+1，直到判定为无答案或配对成功。求这个的复杂度是 O(n |\sum|) 的，能过。但是在某道加强版上你就会被卡飞。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

const int N=2e6+10;
int n;
string s;
int f[N],nxt[N];

il void solve(){
    cin>>n>>s;int ans=0;
    nxt[n-1]=nxt[n]=-1;
    for(re int i=n-2;i>=0;--i){
        int now=i+1;
        while(s[i]!=s[now]&&~nxt[now]) now=nxt[now]+1;
        if(s[i]==s[now]) nxt[i]=now;
        else nxt[i]=-1;
    }
    for(re int i=n-1;i>=0;--i) if(~nxt[i]) f[i]=f[nxt[i]+1]+1;
    for(re int i=0;i<n;++i) ans+=f[i];
    cout<<ans; 
}

signed main(){
    solve();
    return 0;
}