codeforces1509 D. Binary Literature (構造+指標)

codeforces1509 D. Binary Literature

原題鏈接

題意：

給定三個長度為 2 ? n 2*n 2?n字串，要求構造一個長度小于等于 3 ? n 3*n 3?n的字串 s s s使得至少有兩個字串是 s s s的子序列，

思路：

本來的思路是列舉兩個字串 a , b a,b a,b， b b b中的 0 / 1 0/1 0/1一定在 a a a里出現過，只需要在 a a a后面拼接上 b b b剩下的部分就行，思路會忽略掉一些正確的情況，
由于給出的字串只有 0 , 1 0,1 0,1，所以一定有兩個字串有長度大于 n n n的全0或全1的公共子序列，只需要將字串中非子序列的部分按次序插入到公共子序列當中就是答案，
感覺不好實作所以去看了題解的第二種思路，
還是由于給出的字串只有 0 , 1 0,1 0,1兩種情況，所以考慮指標的寫法：
p a , p b , p c pa,pb,pc pa,pb,pc分別指向字串 a , b , c a,b,c a,b,c，每次比較任意兩個，有相同字符則將該字符添加到結果字串中，同時對應的指標往后移動，由于字符不是 0 0 0就是 1 1 1，所以一定會有兩個相等，
直到有一個字串全部被加到結果字串里，（假設該字串為 a a a，結束的條件為 p a > 2 ? n pa>2*n pa>2?n）
這時候結果字串的長度為 i d x idx idx，所有的指標至少移動了 2 ? i d x 2*idx 2?idx次，
假設 p a pa pa指標移動了2*n次，所以剩下的 p b , p c pb,pc pb,pc指標移動了 2 ? ( i d x ? n ) 2*(idx-n) 2?(idx?n)次，也就是說肯定有一個指標至少移動了 ( i d x ? n ) (idx-n) (idx?n)次，把這個指標對應的字串的剩余部分加到結果中即可，
添加的字符最多為 2 ? n ? ( i d x ? n ) = 3 ? n ? i d x 2*n-(idx-n)=3*n-idx 2?n?(idx?n)=3?n?idx
結果字串的長度最多為 i d x + 3 ? n ? i d x = 3 n idx+3*n-idx=3n idx+3?n?idx=3n
還有個小細節：陣列至少要開到 3 e 5 3e5 3e5

代碼：

如果用陣列存的話，代碼會簡潔點，下面是我的垃圾代碼

const int maxn =1e6+7;
char a[maxn],b[maxn],c[maxn];
char s[maxn];
int main(){
    int T=read;
    while(T--){
    	int n=read;
    	cin>>a+1>>b+1>>c+1;
    	int pa=1,pb=1,pc=1,idx=0;
    	while(1){
    		if(a[pa]==b[pb]){
    			s[++idx]=a[pa];
    			pa++,pb++;
    			if(pa>2*n||pb>2*n||pc>2*n) break;
    			continue;
    		} 
    		
    		if(b[pb]==c[pc]){
    			s[++idx]=b[pb];
    			pb++,pc++;
    			if(pa>2*n||pb>2*n||pc>2*n) break;
    			continue;
    		}
			
    		if(a[pa]==c[pc]){
    			s[++idx]=a[pa];
    			pa++,pc++;
    			if(pa>2*n||pb>2*n||pc>2*n) break;
    		} 
    	}
    	///cout<<pa<<"*****"<<pb<<"****"<<pc<<endl;
    	int t=idx-n;
    	if(pa>2*n){
    		if(pb>t){
    			for(int i=pb;i<=2*n;i++)
    				s[++idx]=b[i];
    			for(int i=1;i<=idx;i++)
    				cout<<s[i];
    			puts("");
    			continue;
    		}
    		if(pc>t){
    			for(int i=pc;i<=2*n;i++)
    				s[++idx]=c[i];
    			for(int i=1;i<=idx;i++)
    				cout<<s[i];
    			puts("");
    			continue;
    		}
    	}
    	if(pb>2*n){
    		if(pa>t){
    			for(int i=pa;i<=2*n;i++)
    				s[++idx]=a[i];
    			for(int i=1;i<=idx;i++)
    				cout<<s[i];
    			puts("");
    			continue;
    		}
    		if(pc>t){
    			for(int i=pc;i<=2*n;i++)
    				s[++idx]=c[i];
    			for(int i=1;i<=idx;i++)
    				cout<<s[i];
    			puts("");
    			continue;
    		}
    	}
    	if(pc>2*n){
    		if(pb>t){
    			for(int i=pb;i<=2*n;i++)
    				s[++idx]=b[i];
    			for(int i=1;i<=idx;i++)
    				cout<<s[i];
    			puts("");
    			continue;
    		}
    		if(pa>t){
    			for(int i=pa;i<=2*n;i++)
    				s[++idx]=a[i];
    			for(int i=1;i<=idx;i++)
    				cout<<s[i];
    			puts("");
    			continue;
    		}
    	}
    }
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
    return 0;
}