标签：记忆化搜索，模拟，位运算
You are given n stringss1, s2, ..., sn consisting of characters 0 and 1.m operations areperformed, on each of them you concatenate two existing strings into a new one.On thei-th operation the concatenationsaisbiis saved into a new stringsn + i(the operations are numbered starting from 1). After each operation you need tofind the maximum positive integerk such that all possible stringsconsisting of 0 and 1 of lengthk (there are 2k suchstrings) are substrings of the new string. If there is no suchk, print 0.
Input
The first line contains single integern(1 ≤ n ≤ 100) — thenumber of strings. The nextn lines contain stringss1, s2, ..., sn (1 ≤ |si| ≤ 100), one per line. The total length of strings is not greater than 100.
The next line contains single integerm(1 ≤ m ≤ 100) — thenumber of operations.m lines follow, each of them contains two integersai abdbi (1 ≤ ai, bi ≤ n + i - 1) — the number of strings that areconcatenated to formsn + i.
Output
Print m lines, each should containone integer — the answer to the question after the correspondingoperation.
Example
Input
5
01
10
101
11111
0
3
1 2
6 5
4 4
Output
1
2
0
Note
On the first operation, a new string "0110"is created. Fork = 1 the two possiblebinary strings of lengthk are "0" and "1", they aresubstrings of the new string. Fork = 2 and greater there exist strings of lengthk that do notappear in this string (fork = 2 such string is "00"). So the answer is 1.
On the second operation the string "01100"is created. Now all strings of lengthk = 2 are present.
On the third operation the string "1111111111"is created. There is no zero, so the answer is 0.
题意：给定n个01字符串，进行m次操作，每次将Sa,Sb，两个字符串合并成为新串Sn+i
求：对于每个新和成的字符串，存在数字k，满足长度为k的01字符全排列都存在于新和成的字符串的子串中，询问k的最大值
分析：
直接模拟就好了，注意求出的每个ans，一定要存储下来，记忆化使用，01字符全排列可以使用位运算加速，不会TLE
代码中取头尾各500，防止MLE
我们合并两个字符串的时候，对答案产生贡献的部分就是两者中间衔接部分
所以我们可以只记录每个字符串的头和尾作为特征来更新答案
对于这种做法答案的正确性，可以有递推式ans[n+i]=max(max(ans[l],ans[r]),work(n+i))保证，满足答案递增（是部分递增，不是全局递增），貌似可以有严谨（xuan xue）的数学证明但是本蒟蒻不会啊，大家有数据也可以hack。
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=206;
int ans[maxn],n,m,l,r;
string s[maxn];
int work(int x){
rep(i,1,10)
rep(j,0,(1<<i)-1){
string t;
rep(k,0,i-1){
if(j&(1<<k))t+='1';
else t+='0';
}
if(s[x].find(t)==-1)return i-1;
}
}
int main()
{
scanf("%d",&n);
rep(i,1,n)cin>>s[i];
scanf("%d",&m);
rep(i,1,m){
scanf("%d%d",&l,&r);
s[n+i]=s[l]+s[r];
if(s[n+i].length()>1000)s[n+i]=s[n+i].substr(0,500)+s[n+i].substr(s[n+i].length()-500,500);
ans[n+i]=max(max(ans[l],ans[r]),work(n+i));
cout<<ans[n+i]<<endl;
}
return 0;
}
