[题解] CF1918G Permutation of Given

Monke_FClBrI · 2025-01-06 13:38:04 · 题解

你们的构造怎么都这么简单。为什么每次做构造题都会被降智。

设 b 为产生的序列。题目要求 a,b 组成的可重集相等，那我干脆让中间一大段都满足 a_i=b_i 好了。随便钦定 a 的头两项，就可以构造出这样一个循环序列：

a = 1 -2 -3 -1 2 3 1 -2 -3 ...
b =   -2 -3 -1 2 3 1 -2    ...

但是这样 b_1 和 b_n 就出问题了。考虑给它拼上一个火车头。

a = c d e x y ...
b = d ? ? ? y ...

这里 x,y 都是已经确定的、在中间一大段的部分。我们尝试让 b 中的三个问号分别填上数字 c,e,x。

考虑 b_2，由于 a_i\ne 0，故 b_2\ne c,b_2\ne e，则 b_2=x。再考虑 b_4，发现 b_4\ne e，则 b_4=c，这样 b_3=e。检查一下，发现逻辑上没问题。于是考虑计算出 c,d,e。可以列出方程组：

解得 c=\dfrac{x+y}2,d=-\dfrac{x+y}2,e=\dfrac{x-y}2，发现 x+y 和 x-y 都不会为 0，完全可行。由于要除以 2，我们令中间一段整体乘 2 即可。末尾也一样处理。

注意这个只适用于 n\ge 8，对于 n<8 的随便构造或者暴力一下即可。

代码

#include<bits/stdc++.h>
#define wrk(x,y) if(n==x)cout<<y"\n",exit(0)
#define pb push_back
#define SZ(x) (int)(x).size()
using namespace std;
const int N=1e6+5;
int n,a[N],b[]={2,-4,-6,-2,4,6};
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    wrk(2,"YES\n1 1");
    wrk(3,"NO");
    wrk(4,"YES\n1 2 -2 -1");
    wrk(5,"NO");
    wrk(6,"YES\n-2 -1 1 -1 1 2");
    wrk(7,"YES\n-5 -4 3 -1 -2 4 1");
    for(int i=4;i<=n-3;i++)a[i]=b[i%6];
    a[1]=(a[4]+a[5])/2;
    a[2]=-a[1];
    a[3]=(a[4]-a[5])/2;
    a[n]=(a[n-3]+a[n-4])/2;
    a[n-1]=-a[n];
    a[n-2]=(a[n-3]-a[n-4])/2;
    cout<<"YES\n";
    for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
    return 0;
}

（逃