题解 [email protected]洛谷 | [email protected] 【Numbers】

简单构造题。

题意:给定 nn 个数,是否能排成一圈,使相邻两个数差 11


根据题意,为了使相邻两个数差 11,圆圈中 +1+11-1 的次数必定相等才能组成闭环,因此 nn 必须是偶数,对于奇数可以直接输出无解(代码注释 {1})。

然后同样根据相邻两个数差 11 的性质,我们将原数列排序,枚举相邻两个下标的数,如果差大于 11 也输出无解(代码注释 {2})。

之后找到数列最小值,把每个数减去最小值再加 11,即可得到一串与原数列等效的、最小值为 11 的数列,经过前面两个特判,可以保证最大值不超过 10510^5。然后从最小值开始,可以 +1+1 时选择 +1+1,否则看看是否可以 1-1,若不可以就跳出循环。

由于闭环性质,要形成环则最后一个数必定是 22,如果不是 22 则不能成环,输出无解(代码注释 {3})。

否则将整个桶扫一遍,如果有地方不为 00 则代表成环失败,输出无解(代码注释 {4})。

否则即代表我们构造出了一个符合题意的环,输出有解即可。

这样就水过了一道 CF *2000 的构造题(


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 1e5+5, inf = 1e9;

int n, a[N], buc[N], mi = inf;

int main() {
	scanf("%d", &n);
	if(n & 1) return puts("NO"), 0; // {1}
	rep(i, 1, n) scanf("%d", &a[i]), mi = min(mi, a[i]);
	sort(a+1, a+1+n);
	rep(i, 2, n) if(a[i] - a[i-1] > 1) return puts("NO"), 0; // {2}
	rep(i, 1, n) ++buc[a[i]-mi+1];
	int u = 1; --buc[1];
	loop {
		if(buc[u+1]) --buc[++u];
		else if(buc[u-1]) --buc[--u];
		else break;
	}
	if(u != 2) return puts("NO"), 0; // {3}
	rep(i, 0, N-1) if(buc[i]) return puts("NO"), 0; // {4}
	return puts("YES"), 0;
}