自动搬运

查看原文

来自洛谷，原作者为

	Rnfcr 这个家伙很懒，什么也没留下

搬运于2025-08-24 23:11:11，当前版本为作者最后更新于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;
}