Codeforces Round #698 (Div. 2) C - Nezzar and Symmetric Array（数学 + 思维）_codeforces round #698 e

原题链接

题意 ：

就是给一个2 * n 的数组 d , 试推出是否存在一个2 * n 的数组a , 使得对于数组中的任意一个元素x 存在-x ,且满足

思路 ：
这道题是个数学题 ， 可以模拟设一下 。 首先设n = 2 , 原数组为a , b , -a , -b , d数组为m , n 则由公式可知 n = 2 * ( b + b) , m = 2 * (a + b) ，m < n , 再模拟n = 3 , 4（规律很明显） ， 可以发现规律 ， 就是求原数组时要从后往前求 ，先求最大的 ， 再依次往前推
，注意d中元素一定是偶数， 且成对出现 ，求出来a中元素不存在0 ，注意这几个条件判断一下就行了。用set ， 否则会T .

ps : 这道题历经波折 ，比赛的时候交了6发，都错在了数据三 ，然后用set优化了一下 ， 还是错在了数据三 ，然后早上起来再看一遍代码 ， 发现有个数组忘开long long了，气到吐血/(ㄒoㄒ)/~~ ， 错失一百分。

代码 ：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 3e5 + 10 ;
ll a[maxn] ;			//一定要开long long 
ll t , n ;
ll d[maxn] ;
struct myComp
{
	bool operator()(const long long &a,const long long &b)
	{
		return a > b ;
	}
} ;
set<long long , myComp>s;		//从大到小排列 
multiset<ll> ss ;				//查重 ， 判断是否有三个及以上相同 
set<ll,myComp>::iterator it;


int main(){
	ios::sync_with_stdio(false) ;
	cin.tie(0) ;
	cout.tie(0) ;
	scanf("%lld" ,&t) ;
	while(t--){
		s.clear() ;
		ss.clear() ;
		for(int i = 1 ; i <= n ; i++)
			a[i] = 0 ;
		scanf("%lld" , &n) ;
		int flagg = 0 ;
		for(int i = 1 ; i <= 2 * n ; i++){
			ll temp ;
			scanf("%lld" , &temp) ;
			if(temp % 2)		//d中存在奇数 不符合 
				flagg = 1 ;
			s.insert(temp / 2) ;
			ss.insert(temp / 2) ;
			if(ss.count(temp / 2) > 2){
				flagg = 1 ;		//存在3个及以上相同 ， 不符合 
			}
		}
		if(flagg){
			puts("NO") ;
			continue ;
		}
		//cout << "aa" << endl ;
		//cout << "id " << id << endl ;
		int id = s.size() ;
		if(id != n){			//没有n个数 不符合 
			puts("NO") ;
			continue ;
		}
		int flag = 1 ;
		ll sum = 0 ;
		ll cnt = n ;
		for(set<ll,myComp>::iterator it = s.begin(); it != s.end(); it++){
			ll tempp = (*it - sum) ;
			a[cnt] = (*it - sum) / cnt ;
			if(a[cnt] * cnt != (*it - sum)){		//有可能出现小数 
				flag = 0 ;
				break ;
			}
			sum += a[cnt] ;
			cnt-- ;
		}
		if(a[1] <= 0 || flag == 0){
			puts("NO") ;
			continue ;
		}
		flag = 1 ;
		for(int i = 2 ; i <= n ; i++){
			if(a[i] < a[i-1] || a[i] <= 0){		//求出来的都是正数 
				flag = 0 ;
				break ;
			}
		}
		if(flag)	puts("YES") ;
		else	puts("NO") ;
	}
	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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82