首页 > ACM题库 > HDU-杭电 > HDU 4665-Unshuffle[解题报告]HOJ
2015
09-17

HDU 4665-Unshuffle[解题报告]HOJ

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