Codeforces Round #698 (Div. 2) C - Nezzar and Symmetric Array (找规律）_codeforces div698 c

题意：定义一下对称序列，对于序列的每个元素，它和它的相反数均存在于这个序列中。然后按照题目的要求定义数组d，问你给定一个数组d，能否找到一个序列a来生成数组d。

思路：一开始并没有什么思路，但是看到数据和对称的性质，手写几组数据就会发现，假如一个绝对值较大的数和两个绝对值较小的对称数做差绝对值求和的话，就会发现结果是等于这个大的绝对值的两倍的，例如4,-4,2，2,1，-1。

既然是两倍，那么d数组中的数一定是偶数，并且是成对出现的，不符合这种情况的可以直接输出NO。然后，我们去找d数组的最大值$d_{max}$，$d_{max}/2n$就是a数组的最大的值，因为这个数和其他每个数组做差求和都是自己的两倍,再找次大值$d_i$,可知$(d_i-2\ast a)/2(n-1)$就是第二个a，然后每次都更新一下a，加等于商，如果某一次不是整除或者分母小于等于0，都是不合法答案，输出NO，否则就是YES。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
#define pb push_back
#define MP make_pair
ll d[MAXN],a[MAXN];
map<ll,int>mp;
// bool cmp(ll x,ll y){ return x > y; }
//找到一个规律就是 大的一个数和小的两个数绝对值相加 结果总是等于大的数的绝对值的两倍
int main(){
	int T;scanf("%d",&T);
	while(T--){
		mp.clear();
		int n,flag = 0;scanf("%d",&n);
		n *= 2;
		for(int i = 1;i <= n;i ++){
			scanf("%lld",&d[i]);
			mp[d[i]]++;
			if(d[i] & 1) flag = 1;
		}
		for(auto it = mp.begin();it != mp.end();it ++){
			if(it -> second != 2) {
				flag = 1;break;
			}
		}
		if(flag) {//奇数和不是成对出现的情况 一定是NO的
			printf("NO\n");continue;
		}
		sort(d + 1,d + 1 + n);
		int f = 0;
		ll last = 0;
		// for(int i = 1;i <= n;i += 2) cout<<d[i]<<' ';cout<<'\n';
		for(int i = n;i >= 2;i -= 2){
			if(d[i] > 2 * last){
				ll mod = (d[i] - last*2) % i;
				if(mod) {
					f = 1;
					break;
				}
				last += (d[i] - last*2) / i;
			}
			else {
				f = 1;
				break;
			}
		}
		if(f) puts("NO");
		else puts("YES");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53