CF1305E Kuroni and the Score Distribution 做题记录

构造一个序列 $a$ 满足以下条件：

1. 长度为 $n$ 。
2. $\forall i, 1\leq a_i\leq 10^9$ 。
3. $\forall i>1,a_i>a_{i-1}$。
4. 满足 $i<j<k$ 且 $a_i+a_j=a_k$ 的三元组 $(i,j,k)$ 数量恰好为 $m$。

$1\le n\leq 5000$，$0\le m\leq 10^9$。

考虑填入正整数序列。

$1,2,3,4,5,6,7,8,9$，贡献为 $0,0,1,1,2,2,3,3,4,4$，不难发现这样构造的三元组是最多的，因为 $i$ 前面的 $i-1$ 个数除了中间那个都会参与贡献。

那么如果这样构造都不够就不合法，否则一直填直到总是 $\ge m$，假设多了 $w$ 个，不难发现最后填到的这个位置每 $+2$ 三元组个数就会 $-1$，所以当前位置直接加上 $2w$ 即可。

如果最后没有填满 $n$ 个数，假设最大数为 $v$，那么依次填入 $3v,5v,7v,9v,\dots$ 即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=5005;

int n,m;
int a[S];

int main()
{
	scanf("%d%d",&n,&m);
	int tot=0;
	for(int i=1;i<=n;i++)
	{
		 a[i]=i;
		 tot+=(i-1)/2;
		 if(tot>=m)
		 {
		 	int w=tot-m;
		 	a[i]+=w*2;
		 	for(int j=i+1;j<=n;j++) a[j]=a[i]*((j-i)*2+1);
		 	for(int j=1;j<=n;j++) printf("%d ",a[j]);
		 	printf("\n");
		 	return 0;
		 }
	}
	puts("-1");
	return 0;
}