题解：AT_stpc2025_1_g Don't make zero

· · 题解

题意

给定正整数 n 和 x 与数组 a 每一项的正负性，强制在线构造一个长度为 x 的数组 a，满足所有项互不相同，其的任意子序列之和均不为 0。

思路

显然从一个贪心的角度来想，让 a 的任意子序列之和均不为 0，我们可以由大到小或者由小到大来放。 ::::info[提示] 考虑从大到小进行放置，占用 [x-n-1,n] 这个区间。

感性理解一下，将 [x-n-1,n] 这个区间分为小的(负的)，大的(正的)两组，手玩一下较小的 x 即可发现这样做是正确的。 :::: 设正数第一项为 n，负数第一项为 (x-n-1)，每输出一项，让对应的正数/负数 -1 即可。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll R;
ll n,x;
ll p1,f1;
char op;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>R;
    while(R--){
        cin>>n>>x;
        p1=n;
        f1=x-n-1;
        for(int i=1;i<=x;i++){
            cin>>op;
            if(op=='+'){
                cout<<p1<<endl;
                p1--;
            }else if(op=='-'){
                cout<<f1<<endl;
                f1--;
            }else return 0;
        }

    }
    return 0;
}

::::

感谢观看。