题解 CF1305E 【Kuroni and the Score Distribution】
xht
2020-03-06 13:16:38
要求构造一个长度为 $n$ 的单调上升序列 $a$，使得恰好有 $m$ 个三元组 $(i,j,k)(i < j < k)$ 满足 $a_i + a_j = a_k$。
很傻的一道构造题。
先 $1,2,3,4,5,\dots$ 的填，产生的三元组个数为 $0,0,1,1,2,\dots$。
一直填到第一次个数 $\ge m$ 的位置，假设多了 $k$ 个。
注意到在这个位置上的数每增加 $2$，个数会减 $1$，因此这个位置上的数加上 $2k$ 即可。
后面的不应该再存在满足条件的三元组了，那么填一定间隔下最大的几个数就够了。
如果填完 $n$ 个数，三元组的数量依旧 $< m$，则说明无解，因为这个填数的方法最大化了三元组的数量。
```cpp
const int N = 5e3 + 7;
int n, m, a[N];
int main() {
rd(n), rd(m);
int t = 0;
for (int i = 0; i < n; i++) {
a[i] = i + 1;
t += i >> 1;
if (t >= m) {
a[i] += (t - m) << 1;
for (int j = n - 1, k = 1e9; j > i; j--, k -= i + 2)
a[j] = k;
for (int j = 0; j < n; j++)
print(a[j], " \n"[j==n]);
return 0;
}
}
print(-1);
return 0;
}
```