Codeforces868d huge strings

Posted by yjjr's blog on February 6, 2018

标签:记忆化搜索,模拟,位运算

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;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr