0%

Nezzar and Symmetric Array

Nezzar and Symmetric Array

cf1478c
题中求的值相当于一个数轴上点到其他点距离的和,则一个点到一对(对称)点的距离:

  • 若此点在两点间,为两对称点距离
  • 否则为此点到原点距离两倍
  • 对自己可同样处理 如果将原来的值从小到大排列,可以发现,从最大值开始可以依次解出每个值,都正即可。
    一直wa7,发现新写的没判断成对与否。。。
    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
    #include<bits/stdc++.h>
    #define MP make_pair
    #define per() int idkvwo;cin>>idkvwo;while(idkvwo--)
    using namespace std;
    typedef long long ll;

    const int inf=0x3f3f3f3f;
    const ll INF = 0x3f3f3f3f3f3f3f3fll;
    inline int read(){int ret = 0, sgn = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')sgn = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){ret = ret*10 + ch - '0';ch = getchar();}return ret*sgn;}
    struct ui{int fir;int sec;bool operator<(const ui b)const{return this->fir<b.fir;}};
    const int maxn=1e5+100;
    bool cmp(ll a,ll b){
    return a>b;
    }
    ll in[maxn];
    int main()
    {
    std::ios::sync_with_stdio(false);std::cin.tie(0);
    per(){
    ll n;cin>>n;
    n*=2;
    map<ll,ll> ma;
    ll tmp;
    ll tag=1;
    ll tot=0;
    for(ll i=1;i<=n;++i){
    cin>>tmp;
    if(ma[tmp]==0){
    in[++tot]=tmp;
    ma[tmp]+=1;
    }else if(ma[tmp]==1){
    ma[tmp]++;
    }else{
    tag=0;
    }
    }
    for(auto i:ma){
    if(i.second==1){
    tag=0;break;
    }
    }
    if(tag==0){
    cout<<"NO"<<endl;
    continue;
    }
    n/=2;
    sort(in+1,in+1+n,cmp);
    ll now=0;
    for(ll i=1;i<=n;++i){
    ll tt=(in[i]-now)/(2*(n-i+1));
    if(tt<=0||in[i]%2==1||(in[i]-now)%(2*(n-i+1))!=0){
    tag=0;
    break;
    }
    now+=tt*2;
    }
    if(tag){
    cout<<"YES"<<endl;
    }else cout<<"NO"<<endl;
    }
    return 0;
    }