题意：给出n个01串，m个询问，每次询问将2个串拼接起来，然后求一个最大的k，使得长度为k的01串全部是这2个串的子串（一共2^k）个，拼接的新串可以作为后面询问的原串再次拼接
思路：直接暴力做，每次讲串拼接起来成为新串，然后枚举k，找到最大的可行的k，有一个地方可以记忆化，就是比如a 和b 拼接，如果a的答案是ka，那么a b拼接至少是ka，这样做下去有一个问题，就是空间会炸，因为如果每次自己和自己拼接，那么最大可能是100^100的长度，所以这里用一个技巧，就是每次计算完答案后，如果长度大于2000， 把中间的去掉，只保留前后各1000个字符，因为，比如a的答案为ka， b的答案为kb，若拼接后答案小于ka 或者kb，那么不需要计算，直接可以记忆化得到答案，若拼接后答案大于ka和kb，那么答案一定不是单独在a或者b里面，一定是跨越了a和b的，因为如果在a和b里面就不可能比ka kb大，而跨越a b的长度为1000的部分是完全正确没有缺少或者被删除的，因为输入字符串最多为100个，所以，长度很大的化必然有很多完全重复的部分，1000已经足够大，可以保留到基本上所有出现过的的01串
AC代码：
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl (" ") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const ll mod=1e9+7; const ll INF = 1e18+1LL; const int inf = 1e9+1e8; const double PI=acos(-1.0); const int N=1e5+100; int K[205],k,a,b,n,m; vector<int> vex[205]; string s[205],ss; char sx[205]; void fun0(int x, int t){ int p=0; while(x>0){ sx[p++]=(x&1)+'0'; x>>=1; } for(int i=p; i<t; ++i) sx[i]='0'; sx[t]=' '; } bool fun(int x, int t){ for(int i=0; i<=(1<<x)-1; ++i){ fun0(i,x); ss=sx; //cout<<i<<" "<<ss<<endl; if(s[t].find(ss)==-1) return 0; } return 1; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; mem(K,-1); for(int i=1; i<=n; ++i){ cin>>s[i]; vex[i].pb(i); } cin>>m; for(int i=1; i<=m; ++i){ cin>>a>>b; k=0; s[n+i]=s[a]+s[b]; if(K[a]!=-1 || K[b]!=-1) k=max(K[a], K[b]); //cout<<k<<endl; for(int t=k+1; t<=10; ++t){ if(fun(t, n+i)) k=t; else break; } if(s[n+i].length()>2000) s[n+i]=s[n+i].substr(0,1000)+s[n+i].substr(s[n+i].length()-1000,1000); K[n+i]=k; cout<<k<<endl; } return 0; }