题解 「EZEC-6」加减

$\sum\limits_{i=1}^{n}i=\frac{n\times(n+1)}{2}$，$\sum\limits_{i=2}^{n+1}i=\frac{n\times(n+3)}{2}$， 若 $m\ge\frac{n\times(n+3)}{2}$，可以给出构造解： $2,3,\dots,n-1,n,m-\frac{(n-1)\times(n+2)}{2}$，无法表示出 $m-1$。 ------------ 若 $m<\frac{n\times(n+1)}{2}$，无法分为 $n$ 个不相同的正整数，显然无解。 ------------ 若 $\frac{n\times(n+1)}{2}\le m<\frac{n\times(n+3)}{2}$， 假设有解，不妨认为构造出来的序列 $a$ 单调递增， 设 $m=\frac{n\times(n+1)}{2}+t$，那么所有由 $n$ 个不相同的正整数组成且和为 $m$ 的单调递增的序列均可以这么得到：有一个初始为 $1,2,\dots,n-1,n$ 的序列，每次给一个数加 $1$，加 $t$ 次，中途需要保持序列单调递增，这相当于进行若干次后缀加，总的增量为 $t$。 结论： 若 $n\ge4$，对于得到的任意一个序列 $a$，和任意一个 $2\le i\le n$，都有 $(\sum\limits_{j=1}^{i-1}a_j)+1\ge a_i$。 证明： $t<\frac{n\times(n+3)}{2}-\frac{n\times(n+1)}{2}$，即 $t<n$， 如果要使上述结论不成立，设要使得它在 $i$ 的位置不成立，显然一直给 $a_i$ 加 $1$ 是最优的，给 $a_i$ 加 $1$ 的需要进行 $n-i+1$ 次加法，$a_i$ 最多能被加 $\lfloor\frac{t}{n-i+1}\rfloor\le \lfloor\frac{n-1}{n-i+1}\rfloor$ 次， 现在需要证明 $a_i>(\sum\limits_{j=1}^{i-1}a_j)+1$ 是不可能的， 即证明 $i+\lfloor\frac{n-1}{n-i+1}\rfloor\le \frac{i\times(i-1)}{2}+1$， 假设现在 $i$ 已经固定，则 $n=i$ 时，$\lfloor\frac{n-1}{n-i+1}\rfloor$ 最大，它的值为 $i-1$， 现在需要证明 $i+i-1\le\frac{i\times(i-1)}{2}+1$， 即 $4i-4\le i^2-i$， 在 $i\ge4$ 时，即 $n\ge4$ 时，上式成立，证毕。 接下来可以利用这个结论完成本题证明： 若 $n<4$，暴力枚举可得无解，若 $n\ge4$： 因为 $t<n$，后缀加无法对 $a_1$ 造成影响，所以 $a_1=1$，第一个数可以表示出区间 $[1,1]$ 内的所有正整数，假设目前已经得到了 $a_1$ 至 $a_x$ 可以表示区间 $[1,s]$ 内的所有正整数且 $s=\sum\limits_{i=1}^xa_i$，则加入 $a_{x+1}$ 后一定可以表示区间 $[a_{x+1},a_{x+1}+s]$ 内的所有正整数，由之前的结论可得：$s+1\ge a_{x+1}$，那么 $[1,s]\cup[a_{x+1},a_{x+1}+s]=[1,a_{x+1}+s]$，当前的区间右端点仍为已加入的所有数的和，最后将 $a_n$ 加入后，一定可以表示区间 $[1,\sum\limits_{i=1}^na_i]$ 内所有正整数，即可以表示出区间 $[1,m]$ 内所有正整数。 所以当 $\frac{n\times(n+1)}{2}\le m<\frac{n\times(n+3)}{2}$ 时，无解。 code： ```cpp #include<bits/stdc++.h> using namespace std; int read(){ int w=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')w=w*10+c-48,c=getchar(); return w; } int T,n,m; signed main(){ T=read(); while(T--){ n=read(),m=read(); if(n*(n+3)/2>m){ puts("-1"); continue; } for(int i=2;i<=n;i++) printf("%d ",i); printf("%d\n%d\n",m-(n-1)*(n+2)/2,m-1); } return 0; } ```