题解：P16456 [UOI 2026] Intersection of Prefix Sums

· · 题解

这个题到底怎么卡的随机化，好神奇 /zy

我声称构造数据比解决这个题困难多了。

如果元素和恰好是 x 那么前缀和取到全集的时候就爆了，无解。

刻画操作，容易发现等价于初始时对于数轴有一个棋子在 0 上，然后每个数字等价于把棋子向左或向右移动若干步。有一个点不被允许抵达。

考虑往 x 反方向去走，如果最终位置和 0 中间没有 x，那么显然反着走到底然后再折返都不可能抵达 x，一定合法。

那么考虑如果中间有一个 x 的情况。

考虑直奔主题然后再调整，先往 x 去走，优先走短步，如果我们不幸恰好踩中了 x，我们从这个方向里找一个更长的步来替换掉一个短步即可。

因为我们优先选了短步，替换失败当且仅当所有这个方向的步等长。

这个时候考虑调整一下，在开头逆向走一步，这可以等价的看成禁用点正着移了等长的距离。

设正向的步长是 b，我们发现之所以会不合法是因为 x 是 b 的倍数。所以我们找一个逆向的不为 b 倍数的步操作即可。操作不了显然就失败了。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline char get_char(bool op=1){
    if(op)return getchar();
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
    int sum=0,fish=1;
    char c=get_char();
    while((c<'0'||c>'9')&&c!='-')c=get_char();
    if(c=='-')fish=-1,c=get_char();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=get_char();
    return sum*fish;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
int a[100005];
void solve(){
    int n=read(),x=read();
    int sum=0;
    for(int i=1;i<=n;i++)
    cin>>a[i],sum+=a[i];
    if(sum==x){
        cout<<"NO\n";
        return;
    }
    bool flg=0;
    if(x<0){
        sum=-sum;
        flg=1;
        for(int i=1;i<=n;i++)
        a[i]=-a[i];
        x=-x;
    }
    sort(a+1,a+1+n);
    if(sum<x){
        cout<<"YES\n";
        for(int i=1;i<=n;i++)
        if(flg)cout<<-a[i]<<' ';
        else cout<<a[i]<<' ';
        return;
    }
    vector<int>ret;
    sum=0;
    int flc=-1;
    int qwq=0;
    for(int i=1;i<=n-qwq;i++)
    if(a[i]>0){
        if(sum+a[i]==x){
            sum+=a[i];
            ret.push_back(a[i]);
            reverse(ret.begin(),ret.end());
            if(ret[ret.size()-1]!=a[n]){
                sum+=a[n]-ret[ret.size()-1];
                ret.push_back(a[n]);
                swap(ret[ret.size()-1],ret[ret.size()-2]);
                qwq=1;
            }else{
                for(int j=1;j<=n&&a[j]<0;j++)
                if(a[j]%a[n]){
                    sum+=a[j];
                    ret.insert(ret.begin(),a[j]);
                    flc=j;
                    break;
                }
                if(flc==-1){
                    puts("NO");
                    return;
                }
            }
        }else{
            sum+=a[i];
            ret.push_back(a[i]);
        }
    }
    for(int i=1;i<=n;i++)
    if(a[i]<=0&&i!=flc)
    ret.push_back(a[i]);
    cout<<"YES\n";
    for(int i=1;i<=n;i++)
    if(flg)cout<<-ret[i-1]<<' ';
    else cout<<ret[i-1]<<' ';
    cout<<'\n';
}
signed main(){
    int t=read();
    while(t--)solve();
    return 0;
}
// 黑夜给了黑夜的人一道光
// 这翅膀三千丈扇一扇摘月亮
// 深夜诗人跟我一起唱我们啦啦啦啦啦
// 这夜晚为我们而璀璨

// 祝愿所有睡着的人晚安好梦
// 我们戴上耳机祝你听不见这歌声
// 还有点时间赶在天亮之前
// 把这首歌献给夜晚

// 床前明月光谁低头思故乡
// 这星空三千丈编一编做翅膀
// 不管会不会唱
// 今夜请你和我啦啦啦啦啦
// 夜还长我们要（你打算）怎么办

// 黑夜给了黑夜的人一道光
// 这翅膀三千丈扇一扇摘月亮
// 深夜诗人跟我一起唱我们啦啦啦啦啦
// 这夜晚为我们而璀璨
// 这夜晚为我们而璀璨