[CF]1478C Nezzar and Symmetric Array

题意：

有\(2n\)个两两不同的数，每个数一定有另外一个数为它的相反数，定义\(d_i\)为第\(i\)个数到别的数的距离和。
现在已知\(d_i\)，询问是否存在合法的数列可以生成\(d\)数列。

题解：

可以在数轴上画出这些数。
显然\(d\)数列必须是对称，且从原点向右单调递增。
于是可以排序判断每个数是否恰好出现两次。
去重后就是单调递增数列。

然后我们可以列出\(a_i\)的方程。
首先

倒着进行一遍高斯消元就行了。
由于后面系数相同，直接计算后缀和就可以直接消元了。
判断数列是否单调递减并且大于\(0\)即可（不能等于\(0\)因为\(0==-0\)）

#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
	char c; int num, f = 1;
	while(c = getchar(),!isdigit(c)) if(c == ‘-‘) f = -1; num = c - ‘0‘;
	while(c = getchar(), isdigit(c)) num = num * 10 + c - ‘0‘;
	return f * num;
}
const int N = 3e5 + 1009;
int n, a[N], minn;
void work() { 
	n = read(); minn = 1ll << 61;
	for(int i = 1; i <= 2 * n; i++) a[i] = read();
	sort(a + 1, a + 1 + 2 * n);
	for(int i = 1; i <= n; i++) {
		if(a[i * 2] != a[i * 2 - 1] || (i >= 2 && a[i * 2] == a[i * 2 - 2])) {
			printf("NO\n");
			return ;
		}
	}
	for(int i = 1; i <= 2 * n; i += 2) 
		a[i / 2 + 1] = a[i];
	int del = 0;
	for(int i = n; i; i--) {
		a[i] -= del;
		if(a[i] <= 0 || a[i] % (i * 2) != 0) {
			printf("NO\n");
			return ;
		}
		del += 2 * (a[i] / (i * 2));
		if(a[i] / (i * 2) >= minn) {
			printf("NO\n");
			return ;
		}
		minn = a[i] / (i * 2);
	}
	printf("YES\n");
}
signed main()
{
	int Case = read();
	while(Case--) work();
	return 0;
}

[CF]1478C Nezzar and Symmetric Array

原文：https://www.cnblogs.com/onglublog/p/14375687.html