Problem Statement
You are given a set $S$ of strings consisting of 0 and 1, and an integer $K$.
Find the longest string that is a subsequence of $K$ or more different strings in $S$. If there are multiple strings that satisfy this condition, find the lexicographically smallest such string.
Here, $S$ is given in the format below:
- The data directly given to you is an integer $N$, and $N+1$ strings $X_0,X_1,...,X_N$. For every $i$ $(0\leq i\leq N)$, the length of $X_i$ is $2^i$.
- For every pair of two integers $(i,j)$ $(0\leq i\leq N,0\leq j\leq 2^i-1)$, the $j$-th character of $X_i$ is
1if and only if the binary representation of $j$ with $i$ digits (possibly with leading zeros) belongs to $S$. Here, the first and last characters in $X_i$ are called the $0$-th and $(2^i-1)$-th characters, respectively. - $S$ does not contain a string with length $N+1$ or more.
Here, a string $A$ is a subsequence of another string $B$ when there exists a sequence of integers $t_1 < ... < t_{|A|}$ such that, for every $i$ $(1\leq i\leq |A|)$, the $i$-th character of $A$ and the $t_i$-th character of $B$ is equal.
Constraints
- $0 \leq N \leq 20$
- $X_i(0\leq i\leq N)$ is a string of length $2^i$ consisting of
0and1. - $1 \leq K \leq |S|$
- $K$ is an integer.
神奇 dp。
记的时候如何区分 1 和 01？统一在前面
考虑暴力怎么做。枚举一个子串，然后数有多少个子串包含这个子串。复杂度 \(4^N\)。
怎么判断一个子串是否是另一个子串的子序列呢？子序列自动机。定义 \(nx_{i,j}\) 为第 \(i\) 位出现的下一个 \(j\) 在哪里，跑就行了。
思考在跑子序列自动机的时候有没有一些重复的状态，发现在某些状态下，已经匹配好的和需要匹配好的串总数是不多的。也就是说，定义 \(dp_{s，t}\) 为已经匹配好的串是 \(s\)，等待匹配的串是 \(t\)，有多少个大串能转化成这种样子。
发现 \(|S|+|T|\le n\)，所以改 dp 定义为 \(dp_{s,i}\) 为串 \(s\)，前 \(i\) 个字符为已经匹配好的，剩下的是等待匹配的。
#include<bits/stdc++.h>
using namespace std;
const int N=2.1e6;
int n,k,m,ln[N],ls[N][21][2],dp[21][N],lg[N],s,ans[N],ret;//dp[i][j]表示总串j,匹配了j位的答案，ls[i][j][k]表示数字i在第j位前的第一个k在第几位
char ch;
int main()
{
for(int i=2;i<N;i++)
lg[i]=lg[i>>1]+1;
scanf("%d%d",&n,&k);
for(int i=0;i<=n;i++)
{
for(int j=0;j<(1<<i);j++)
{
ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
if(ch^48)
dp[0][1<<i|j]++;
}
}
for(int i=1;i<(1<<n+1);i++)
{
m=lg[i],s=i-(1<<m);
ls[i][0][0]=ls[i][0][1]=-1;
for(int j=1;j<=m;j++)
ls[i][j][0]=ls[i][j-1][0],ls[i][j][1]=ls[i][j-1][1],ls[i][j][s>>(j-1)&1]=j-1;
}
// printf("%d %d\n",ls[6][3][0],ls[6][3][1]);
// printf("%d %d\n",ls[6][2][0],ls[6][2][1]);
// printf("%d %d\n",ls[6][1][0],ls[6][1][1]);
for(int i=0;i<=n;i++)//枚举长度
{
for(int j=(1<<i);j<(1<<n+1);j++)
{
m=lg[j];
int k=j>>(m-i);
ans[k]+=dp[i][j];
if(!dp[i][j])
continue;
if(i==m)
continue;
// printf("hjhyyds:%d %d %d\n",i,j,m);
int p=ls[j][m-i][0],q=ls[j][m-i][1];
// printf("%d %d %d %d %d\n",k,(k<<p+1)|(((1<<p+1)-1&j)),(k<<q+1)|((1<<q+1)-1&j),p,q);
if(~p)
dp[i+1][(k<<p+1)|(((1<<p+1)-1&j))]+=dp[i][j];
if(~q)
dp[i+1][(k<<q+1)|((1<<q+1)-1&j)]+=dp[i][j];
}
}
for(int i=1;i<(1<<n+1);i++)
if(ans[i]>=k)
ret=max(ret,lg[i]);
for(int i=1;i<(1<<n+1);i++)
{
if(ans[i]>=k&&lg[i]==ret)
{
for(int j=lg[i]-1;j>=0;j--)
putchar((i>>j&1)+48);
return 0;
}
}
}