专栏文章

题解：CF2130B Pathless

TTechnocy
CF2130B题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miol7d2y
此快照首次捕获于
2025/12/02 21:01
3 个月前
此快照最后确认于
2025/12/02 21:01
3 个月前
查看原文

题意

tt 组数据，每组数据给定一个长度为 nn 的数组 ana_n 和一个非负整数 ss，从 a1a_1 开始，向左或向右 11 步任意次，并使 sumsum 加上 aia_i，直至到达 ana_n，问是否有一种排列使得无论怎样移动都无法使 sum=ssum=s，若有，输出任意一种即可，否则输出 −1-1。

思路

我们可以在输入时便记录 ∑i=1nai\sum^n_{i=1}a_i 以及 00，11，22 的个数，然后令 op=s−∑i=1naiop=s-\sum^n_{i=1}a_i。当 op=1op=1 或 op<0op<0 时，我们就可以先输出完所有的 00，再输出完所有的 22，最后输出剩下的 11；否则直接输出 −1-1。

证明

已知 op=s−∑i=1naiop=s-\sum^n_{i=1}a_i，令 sum=∑j=1maijsum=\sum^m_{j=1}a_{i_j}，那么这里我们分 33 种情况进行讨论：
  • op<0op<0：说明哪怕我全程只走一次都会导致 sum>ssum>s，如果我还来回走显然 opop 会更小，因此在该情况下任意排列均正确。
  • op=1op=1：说明 s=sum+1s=sum+1，那么我全程只要有一个 11 和 00 相邻，来回走一下，就会使 sum+1→sum=ssum+1\to sum=s，因此，我们就要让 00 和 11 分隔开，故先输出所有的 00，再输出所有的 22，最后输出所有的 11 即可使得无论如何都满足 sum≠ssum\ne s。
  • op=0op=0 或 op>1op>1：那么此时无论我怎么进行排列，总会有 00，11，22 之间存在相邻，那么进而我就可以得到 22，33，55，然后就可以通过任意个 22，33，55 的组合得到任意大于等于 22 的数，显然就无解了，此时输出 −1-1 即可。
综上所述，当 op<0op<0 或 op=1op=1 时，我们可以通过先输出所有的 00，再输出所有的 22，最后输出所有的 11 即为正确答案，而当 op=0op=0 或 op>1op>1 时，直接输出 −1-1 即可，证毕。

Code

CPP
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define N 1006
using namespace std;
int t,n,s,a[N],sum;
int mp[N];//mp记录0,1,2的个数
inline int read();
int main(){
    t=read();
    while(t--){
        memset(mp,0,sizeof(mp));//多测不清空，亲人两行泪
        sum=0;
        n=read();s=read();
        for(int i=1;i<=n;i++) a[i]=read(),mp[a[i]]++,sum+=a[i];
        s-=sum;
        if(s==1 || s<0){
            for(int i=1;i<=mp[0];i++) cout<<0<<" ";
            for(int i=1;i<=mp[2];i++) cout<<2<<" ";
            for(int i=1;i<=mp[1];i++) cout<<1<<" ";
            cout<<endl;
        }else cout<<-1<<endl;
    }
    return 0;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...