题目

题目描述

最近Ori收到了Efi的一个礼物，具体如下:
一开始Ori有$n$个$01$串，这些串的总长为$S$，之后Efi会进行$m$次操作，第$i$次操作为$a_i,b_i$，表示将编号为$b_i$的$01$串接在编号为$a_i$的$01$串后面，形成编号为$n+i$个$01$串。Efi为了检验Ori是否有正确进行这些操作，一次操作结束之后Efi会叫Ori找到一个正整数$k$，使得所有长度为$k$的$01$串（一共$2^k$个）都在新增加的第$n+i$个$01$串中。

输入格式

第一行：两个整数$n,m$
接下来$n$行：每行一个$01$串，分别代表编号从$1 \sim n$的$01$串
接下来$m$行：$a_i,b_i$表示一次操作

输出格式

一共$m$行：每行输出一个$k$代表答案

样例

样例输入

样例输出

1
2
3

1
2
0

样例解释

第一次操作之后新产生的$01$串为$0110$，$00$没在串中出现过，因此答案为$1$。
第二次操作之后为$01100$，答案为$2$。
第三次操作之后为$1111111111$，答案为$0$。

数据范围与提示

对于$10 \%$的数据，$n$个$01$串都由$0$组成
对于$30 \%$的数据，编号为$a_i$的$01$串长度为$1$
对于$30 \%$的数据，$a_i=1$
以上部分分不相交
对于$100\%$的数据，有$n \leqslant 100,m \leqslant 100,1 \leqslant a_i,b_i \leqslant n+i-1,S \leqslant 100$（注意这里$S$之表示$n$个串的长度和）。

题解

首先，我们可以计算得出，答案不大于14（我不知道怎么证明，但是我就是觉得答案小于这个数，事实证明我是对的，而且或许还比我估计的小）
因此，我们只需要保存字符串的前14位和后14位就可以了
首先，在输入字符串时，我们可以枚举这个字符传中的所有长度小于等于14的子串，把这些子串打上标记，看看对于这个字符串来说，它的$k$是多少
接着，对于每次合并字符串的操作，它的前十四位和后十四为就不说了，直接由$a$串和$b$串传递，对于他的所有长度小于等于14的子串的处理，合并前的两个串的长度小于等于14的子串一样还有，主要是中间两段字符串相交的地方，就枚举前面那个字符串的后14位，和后面那个字符串的前14位，并且还必须总长度小于等于14（不然就炸内存了）的所有串，也标记一遍，就可以了
具体的实现可以看程序

#include<iostream>
#include<cstring>
using namespace std;
int n,m,ans,len[210],q[210][20],h[210][20],v[210][32770];
char s[110];
int main()
{
    cin>>n>>m;
    for(int i=1,ns;i<=n;i++){
        cin>>s;
        ns=strlen(s),len[i]=min(ns,14);
        for(int j=1;j<=len[i];j++) q[i][j]=s[j-1]-'0',h[i][j]=s[ns-j]-'0';
        for(int j=ns-1;j>=0;j--) for(int k=j,sum=0;k>=max(0,j-14);k--){
            sum+=(1<<(j-k))*(s[k]-'0');
            v[i][sum+(1<<(j-k+1))]=1;
        }//标记所有长度小于等于14的子串
    }
    for(int i=1,a,b,k,l,flag;i<=m;i++){
        cin>>a>>b,n++,ans=0;
        for(int i=1;i<=len[a];i++) q[n][i]=q[a][i];//前14位直接传递
        for(int i=1;i<=len[b];i++) h[n][i]=h[b][i];//后14位直接传递
        l=0,k=len[a];
        while(k<14&&l<=len[b]) q[n][++k]=q[b][++l];//前14位直接传递
        l=0,k=len[b];
        while(k<14&&l<=len[a]) h[n][++k]=h[a][++l];//后14位直接传递
        len[n]=min(len[a]+len[b],14);
        for(int i=0;i<(1<<15);i++) v[n][i]=(v[a][i]|v[b][i]);//标记原来两个串的长度小于等于14子串
        for(int i=1,s=0;i<=len[a];i++){
            s+=h[a][i]*(1<<(i-1));
            for(int j=1,sum=0;j<=len[b]&&i+j<=14;j++) sum=(sum<<1)+q[b][j],v[n][s*(1<<j)+(1<<(i+j))+sum]=1;
        }//标记中间两段字符串相交的地方的长度小于等于14的子串
        for(int j=14;j;j--){
            flag=1;
            for(int k=0;k<(1<<j);k++) if(!v[n][k+(1<<j)]){flag=0;break;}
            if(flag){ans=j;break;}
        }//求k
        cout<<ans<<endl;
    }
}