Reverse Sort Sum

落海沉 · 2022-11-15 19:53:21 · 题解

这是一道不错的构造题

首先，明确如果 f_i = 0 那么这里的 ans_i = 0 ，因为如果这里为 1 的话，那么至少排序到第 i 位时，它会加 1，不成立，所以这一位显然为 0。

因为我们需要找 0，所以我们将答案全部赋值成 1。

结论

证明

• 前 i 个数排列时它一直为 1，在 i 后当存在一个点使这一位再次为 0 时，从此点往后所有排列后的结果，ans_i 一直为 0，所以当且仅当从 i 至 i+s_i-1 的 ans 的值都为 1。则第 i+s_i 排序后第 i 位一定是 0，所以第 i+s_i 位一定是 0。

• 如果这一位为 1，那么第 s_i 位为 0，证法与上文相同，留给读者思考。

故代码就很快就出来了，其实不难写。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
const int inf = 0x3f3f3f3f;
const int N = 2e5+5;
int Case,n,s[N],ans[N],cnt;
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];ans[i]=1;
    }
    for(int i=0;i<n;i++){
        if(s[i]==0){
            ans[i]=0;
        }else{
            if(ans[i]==0)s[i]+=i;
            ans[s[i]]=0;
        }
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>Case;
    while(Case--){
        solve();
    }
    return 0;
}

最后祝大家 noip 取得好成绩！