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