2015
09-17

Unshuffle

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square.
Given a square string, in which each character occurs no more than four times, unshuffle it into two identical strings.

First line, number of test cases, T.
Following are 2*T lines. For every two lines, the first line is n, length of the square string; the second line is the string. Each character is a positive integer no larger than n.

T<=10, n<=2000.

First line, number of test cases, T.
Following are 2*T lines. For every two lines, the first line is n, length of the square string; the second line is the string. Each character is a positive integer no larger than n.

T<=10, n<=2000.

1
8
1 2 3 1 2 4 3 4

00011011

#include <cstdio>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn =2000+5;
int str1[maxn],str2[maxn];
int a[maxn],vis[maxn];
int n;
bool flag;
void dfs(int cur,int cnt1,int cnt2,int num)
{
if(flag) return ;
if(cnt1>n/2) return ;
if(cnt1==n/2&&cnt2==n/2){
flag=1;
for(int i=0; i<n; i++)
printf("%d",vis[i]);
printf("\n");
return;
}
if(a[cur]==str1[num])
{
str2[cnt2]=a[cur];
if(num+1<=cnt1) vis[cur]=1,dfs(cur+1,cnt1,cnt2+1,num+1);
vis[cur]=0;

}
str1[cnt1]=a[cur];
dfs(cur+1,cnt1+1,cnt2,num);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(vis,0,sizeof(vis));
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
str1[0]=a[0];
flag=0;
dfs(1,1,0,0);
}
return 0;
}