\(dp\) 题写多了，写道构造题
首先不要被 \(10^9\) 吓到。可以猜出 \(1,2,3,...,n\) 这样的序列能使对数最大。
我们看看每个位置的贡献：
\[0,0,1,1,2,2,3,3,4,4...\]
这样可以暴力算出最大对数，如果还小于 \(k\) 就只能无解。
否则可以猜出一定有答案。
考虑这样一种构造：每次把整个序列增加 \(1\) ，直到不能再加，然后更改最后一个数
正确性？
以 \(n=10\) 为例，贡献的序列是这样的：
\[0,0,1,1,2,2,3,3,4,4\]
\[0,0,0,1,1,2,2,3,3,4;\Delta = 4\]
\[0,0,0,0,1,1,2,2,3,3;\Delta = 4\]
也就是每次整体右移一位，把最右边的扔掉，总数的变化值等于最右边的数的贡献
这样 \(\Delta\) 一定不大于 \(val_{last} + 1\) ，\(val_{last}\) 为移动后最后一位的贡献，即所以 \(k\) 都能达到
最后考虑实现。设序列为\(a\)，则最后一个数为\(a_{n}\)。
整体增加完了之后，自然的想法是直接把最后一位增加 \(2 \times rest\) ，\(rest\) 为当前对数与 \(k\) 的差值，因为观察能够得到，\(a_{n}\) 每增加 \(2\) ，贡献就会变化 \(1\) 。但是，我们发现直接增加是错误的，因为增加\(2\)时，贡献可能减少 \(1\) ，也可能增加 \(1\) 。
当时被这个卡了一会
解决方法很简单。 \(a_{n}\) 是原来前面的两个数的和，我们要把它变成后面的两个数的和。
\(3,4,5,6,7,8\)
在这个序列中，\(8=3+5\) ，但是增加 \(2\) 后 \(10=3+7\) ，贡献反而变大了。可以想办法把它变成 \(5+7\)，这样贡献不变，但后面改变时贡献一定减少。
观察发现把\(a_n\) 改成 \(2 (a_1 + a_{n-1}) - a_n\) 就行了
这题是不是比 D 简单啊...还是我前天太瞌睡了...
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=1000000007;
const double pi=3.1415926535897932,eps=1e-6;
int n,m,mx,a[5005];
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,n) mx += (i-1) / 2;
if(mx < m) {puts("-1");return 0;}
rep(i,1,n) a[i] = i;
rep(i,1,n - 2) {
int nxt = (n - i)/2;//直接计算整体增加1后总对数的变化值
if(mx - nxt >= m) {
mx -= nxt;
rep(j,1,n) a[j]++;
}else break;
}
a[n] = (a[1] + a[n-1]) * 2 - a[n];
a[n] += (mx - m) * 2;
rep(i,1,n) printf("%d ",a[i]);
return 0;
}CodeForces 1305E Kuroni and the Score Distribution 题解
原文：https://www.cnblogs.com/yz-beacon-cwk/p/12418265.html