2020-08-04

http://icpc.upc.edu.cn/problem.php?cid=1404&pid=5

题目描述

设X是有N个不相同整数的集合。把X中每个数用两次，排成一个长度为2N的数列S，要求S中任意一个数i与另一个与它相同的i之间正好间隔i个数字。

输入

第1行一个整数N(I≤N≤8)；
第2行有N个整数（每个数不相同，并且在0到16之间），表示集合中的数。

输出

输出一个满足上面要求的长度为2N的数列；若有多个解，输出字典序最小的；若没有解，输出-1。

样例输入

5
0 1 2 3 4 

样例输出

0 0 2 3 4 2 1 3 1 4 

DFS搜索每一种情况即可。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include 
using namespace std;
typedef long long ll;
int vis[100]={0};
int data[100]={0};
int n;
int a[100]={0};
int dfs(int k)
{
    if(k==2*n+1)
    {
        for(int i=1;i<=2*n;i++)
        {
            cout<<data[i]<<' ';
        }
        cout<<endl;
        exit(0);
    }
    if(data[k]==-1)
    {
        for(int l=0;l<n;l++)
        {
            int i=a[l];
            if(k+i+1<=2*n&&!vis[i]&&data[k]==-1&&data[k+i+1]==-1)
            {
                data[k]=data[k+i+1]=i;
                vis[i]=1;
                dfs(k+1);
                vis[i]=0;
                data[k]=data[k+i+1]=-1;
            }
        }
    }
    else
        dfs(k+1);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    memset(data,-1,sizeof(data));
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    dfs(1);
    cout<<-1<<endl;
    return 0;
}