[题解] CF1918G Permutation of Given

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

设

b

为产生的序列。题目要求

a,b

组成的可重集相等，那我干脆让中间一大段都满足

a_i=b_i

好了。随便钦定

a

的头两项，就可以构造出这样一个循环序列：

CPP

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

但是这样

b_1

和

b_n

就出问题了。考虑给它拼上一个火车头。

CPP

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

。可以列出方程组：

\begin{cases} c+e=x\\ d+x=e\\ e+y=c \end{cases}

解得

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

的随便构造或者暴力一下即可。

代码

CPP

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

（逃

[题解] CF1918G Permutation of Given

文章操作

代码

相关推荐

评论

[题解] CF1918G Permutation of Given