CF1599J题解

· · 题解

以下称题目中给出的序列为“原序列”。

首先有一个显而易见的结论，若原序列存在相同的数，那么直接可以得出：相同的数其中一个变成 0，剩下的数不变就是一种答案。

我们发现，对于原序列 a 我们只需要找出其任意一个子序列 t 对应的答案序列即可。找到之后不在 t 内的其他数 a_i 可由 t 内的任意一个数 x 和额外的一个数 a_i-x 得出。

对于一个长度为 3 的序列 [A,B,C]，令答案序列中存在一个数 X，如果表示出 A,B 那么可以计算出另两个数为 A-X,B-A+X，这也就是说要是能表示出 C 就需要满足 X+(B-A+X)=C 即 X=\frac{A-B+C}{2}。这就说明若 A,B,C 之和为偶数就可以表示出一个合法的答案序列。

这就有两种可能：均为偶数或者二奇一偶。

当原序列中存在偶数时：

否则，我们现在的序列中全部是奇数。

这时我们尝试去寻找一个可能的子序列，长度为奇数的子序列不可能成为目标，因为类似上面长度为 3 的序列，他需要元素之和为偶数，奇数个奇数之和为奇数，所以不可能。

于是我们假设有一个长度为 2s 的序列 [a_1,a_2,a_3,\cdots,a_{2s}]，类比上面的做法，令答案序列中存在数 X，可以表示出其他数为

a_1-X,a_2-a_1+X,a_3-a_2+a_1-X,\cdots,(a_{2s-1}-a_{2s-2}\cdots +a_1-X)

需要满足 X+(a_{2s-1}-a_{2s-2}\cdots +a_1-X)=a_{2s}，X 被消掉了，得出

\sum_{i=1}^{s} a_{2i-1} = \sum_{i=1}^{s} a_{2i}

也就是说我们需要在原序列中找出任意两个不完全相同的集合，满足大小和元素和均相等（若有重复元素就同时删去）。

我们发现，对于大小为 S 的子序列，选法有 C_N^S 种，取值的个数最多有 10^6 \times S 种，在 S \geq 28 时，后者小于前者，根据鸽巢原理，一定会出现取值相同的子序列，于是可以得出做法：

可以用哈希表来实现。

using namespace std;
# include<bits/stdc++.h>
# include<bits/extc++.h>
int N;
constexpr int maxn(1002);
int a[maxn];
void work1(){
    if(N==2){
        if(a[1]==a[2]){
            printf("YES\n0 %d\n",a[1]);
            return;
        }else{
            printf("NO\n");
            return;
        }
    }
    if(N==3){
        if(a[1]==a[2]){
            printf("YES\n0 %d %d\n",a[2],a[3]);
            return;
        }else if(a[2]==a[3]){
            printf("YES\n0 %d %d\n",a[1],a[3]);
            return;
        }
    }
    std::vector<int>o,j;
    for(int i=1;i<=N;i++) if(a[i]%2==0) o.push_back(i);else j.push_back(i);
    if(N==3&&j.size()<2){
        puts("NO");
        return;
    }
    int A,B,C;
    if(o.size()>=3){
        A=o[0],B=o[1],C=o[2];
    }else A=o[0],B=j[0],C=j[1];
    int X=(a[A]-a[B]+a[C])>>1;
    puts("YES");
    printf("%d %d %d ",X,a[A]-X,a[B]-a[A]+X);
    for(int i=1;i<=N;i++){
        if(i==A||i==B||i==C) continue;
        printf("%d ",a[i]-X);
    }
}
struct aqua{
    std::vector<int>v;
    aqua(){};
    aqua(std::vector<int>t){v=t;}
};
void print(std::vector<int>A,std::vector<int>B){
    static bool visa[maxn],visb[maxn];
    for(auto x:A) visa[x]=1;
    for(auto x:B) visb[x]=1;
    A.clear(),B.clear();
    for(int i=1;i<=N;i++){
        if(visa[i]^visb[i]){
            if(visa[i]) A.push_back(i);
            else B.push_back(i);
        }
    }
    int X=0;
    puts("YES");
    for(int i=0;i<A.size();i++){
        printf("%d ",X);
        X=a[A[i]]-X;
        printf("%d ",X);
        X=a[B[i]]-X;
    }
    for(int i=1;i<=N;i++){
        if(visa[i]^visb[i]) continue;
        printf("%d ",a[i]);
    }
}
void work2(){
    __gnu_pbds::gp_hash_table<int,int>h[30];
    for(int i=1;i<1<<N;i++){
        int g=__builtin_popcount(i);
        int s=0;
        for(int j=1;j<=N;j++){
            if((i>>(j-1))&1) s+=a[j];
        }
        if(h[g][s]){
            int x=i,y=h[g][s];
            std::vector<int>a,b;
            for(int j=1;j<=N;j++){
                if((x>>(j-1))&1) a.push_back(j);
                if((y>>(j-1))&1) b.push_back(j);
            }
            print(a,b);
            return;
        }
        h[g][s]=i;
    }
    puts("NO");
}
std::vector<int>xl;
__gnu_pbds::gp_hash_table<int,aqua>hs;
void dfs(int d,int now,int z){
    if(d==28){
        if(!hs[z].v.empty()){
            print(hs[z].v,xl);
            exit(0);
        }
        hs[z]=aqua(xl);
        return;
    }
    for(int i=now;i<=N;i++)
        xl[d]=i,dfs(d+1,i+1,z+a[i]);
}
void work3(){
    xl.resize(28);
    dfs(0,1,0);
    puts("NO");
}
int main(){
    std::cin>>N;
    bool fg=0;
    for(int i=1;i<=N;i++) scanf("%d",&a[i]),fg|=a[i]%2==0;
    std::sort(a+1,a+N+1);
    if(fg){
        work1();
        return 0;
    }
    if(N<=28) work2();
    else work3();
   return 0;
}