Simple Subsequence Problem[AGC024F][Dp][序列自动机]

题目

Luogu

思路

如何有效判断 $T$ 是 $S$ 的子序列？
我们可以建立出 $S$ 的序列自动机然后用 $T$ 跑，如果是非空节点即可
注意序列自动机中定义:
$tran{s}_{u,c}：$ $u$ 后面第一个 $c$ 的位置
毫无疑问，这样我们匹配出的 $T$ 在 $S$ 中是第一个
注意到是 $01$ 串，意味着我们可以预处理出所有 $nxt$
但是 $01$ 和 $001$ 是有区别的，实现的时候每个数最高位+1位置为 $1$ 进行区别
比如 $trans[1|1001][0]=1|01,trans[1|1001][1]=1|1$ 因为是后面，不算自己
我们尝试这样定义状态：
$f_{S_1,S_2}：$ 已经完成匹配的串为 $S_1$ ，还需要匹配 $S_2$
每次转移也就是 $f_{S_1,S_2}?>f_{S_1|(0/1),tran{s}_{S_2,0/1}}$
注意可以让 $S_2=?$ 来结束
然后枚举 $f_{S_1,0}$ 检验即可
实现的时候是将 $S_1,S_2$ 合并起来的，节约空间
时间复杂度 $n{2}^n$

代码

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=0,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define mp make_pair
const int MAXN=22;
int len[(1<<MAXN)+5],f[MAXN+5][(1<<MAXN)+5],tr[(1<<MAXN)+5][2];
int main(){
    //最高位+1为1 f[i][A|B]:B=1x,|B|=i+1,生成的子序列为A还剩下匹配为B的串的数量int n=read(),k=read();for(int i=0;i<=n;i++)for(int j=0;j<(1<<i);j++)scanf("%1d",&f[i][(3<<i)|j]);len[0]=-1;for(int i=1;i<(1<<(n+2));i++)len[i]=len[i>>1]+1;for(int i=2;i<(1<<(n+2));i++)if((i>>(len[i]-1))&1){
    tr[i][1]=(i^(1<<len[i]));tr[i][0]=tr[tr[i][1]][0];}else{
    tr[i][0]=(i^(3<<(len[i]-1)));tr[i][1]=tr[tr[i][0]][1];}for(int i=n;i>=1;i--)for(int S=(1<<i);S<(1<<(n+2));S++)if(f[i][S]){
    int A=S>>(i+1),B=(S&((1<<i)-1))|(1<<i);if(tr[B][0])f[len[tr[B][0]]][((A<<1)<<(len[tr[B][0]]+1))|tr[B][0]]+=f[i][S];if(tr[B][1])f[len[tr[B][1]]][((A<<1|1)<<(len[tr[B][1]]+1))|tr[B][1]]+=f[i][S];f[0][(A<<1)|1]+=f[i][S];}int ans=1;for(int S=2;S<(1<<(n+2));S++)if(f[0][S]>=k&&len[ans]<len[S>>1])ans=(S>>1);int bit=n;while(!((ans>>bit)&1)) bit--;while(bit)bit--,putchar('0'+((ans>>bit)&1));puts("");return 0;
}