C. Nezzar and Symmetric Array（数学）

C. Nezzar and Symmetric Array

题意
思路
这个题是证明是否有ai可以构造出来di，这个题只需要推理一下就好，下面是推理过程。

我们从中可以发现，d数组从大到小排序以后，每一个数其实和a数组的关系很明确，我们只需要判断d数组是否满足我们推的情况就好。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        set<ll>s;
        int n;
        cin>>n;
        for(int i=1 ; i<=2*n ; i++) cin>>a[i];
        sort(a+1,a+1+2*n);
        ll cnt=2*n;
        bool flag1=true;
        ll sum=0;
        for(ll i=2*n ; i>=2 ; i-=2)
        {
           // cout<<a[i]<<" "<<sum<<" "<<a[i]<<" "<<cnt<<endl;
            if((a[i]-sum)%cnt==0&&a[i]>sum&&s.count((a[i]-sum)/cnt)==0&&a[i]==a[i-1])
            {
                s.insert((a[i]-sum)/cnt);
                sum+=((a[i]-sum)/cnt)*2;
            }
            else
            {
                flag1=false;
                break;
            }
            cnt-=2;
        }
        if(flag1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    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

总结
当时一直WA7，没有写出来，挺遗憾的，我当时交C的时候才500多人过这个题，自己的有些代码不严谨导致了错误，早上一改可过了，如果当时这个题写出来，应该能加不少分。