P11895

Rnfcr · 2025-03-18 13:18:46 · 题解

首先当 k>\frac{n\times(n+1)}{2} 时无解，因为长度为 n 的数列中的总区间数为 \frac{n\times(n+1)}{2}。

当 k\le \frac{n\times(n+1)}{2} 时 k 总可以被表示为 1 至 n 中若干个互不相同的整数的和，因此可以找到若干个左端点，让这些左端点到 n 间的每一个区间都是好的区间。令数列中左端点项的值为 1 ，其余项为 0 便满足了第一个要求。

设此时的 k-\sum_{i = 1}^{n} a_i \times (n-i+1) 为 b ，找到一个不为左端点且它的前一个位置是左端点的位置，令这个位置的值减去 b ，它的前一个位置加上 b 就满足了第二个要求。当 k<\frac{n\times(n+1)}{2} 时一定找的到这个位置，k=\frac{n\times(n+1)}{2} 时 b 一定为 0，这时便不减去，故一定可以构造出一个合法的解。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,k,choose[200009],ans[200009];
signed main(){
    ios::sync_with_stdio(NULL),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k;
        int b=(n*(n+1))/2;
        if(k>b){
            for(int i=1;i<=n;i++) cout<<"0 ";
            cout<<"\n";
            continue;
        }
        for(int i=n;i;i--){
            if(k>=i){
                k-=i;
                choose[n-i+1]=1;
            }
            else choose[n-i+1]=0;
        }
        int val=1;
        for(int i=n;i>=1;i--){
            if(choose[i]){    
                ans[i]=1;
                b-=val;
            }
            else{
                ans[i]=0;
            }
            val++;
        }
        for(int i=1;i<=n;i++){
            if(choose[i]&&!choose[i+1]){
                ans[i]+=b;
                ans[i+1]-=b;
                break;
            }
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<"\n";
    }
    return 0;
}