【2020 去世模拟赛 1】Math

( ext{Description})

给出两个整数(μ)(υ),请你构造一个有 (n) 个元素的整数数列(A),满足以下这些条件:

((1)10<=n<=1000)

((2) -10^9<=A[i]<=10^9)

((3) μ=(A[1]+A[2]+...+A[n])/n,即μ恰好是n 个整数的平均值)

((4) υ=[(A[1]-μ)^2+(A[2]-μ)^2+...+(A[n]-μ)^2]/n,即υ恰好是n 个整数的方差。)

输入格式

(1)行:(1) 个整数(T),表示测试数据的组数。接下来(T) 行,每行 (2) 个整数,分别表示(μ)(υ)

输出格式

(1)行:(1) 个整数(n),表示数列的元素个数 第 (2)行:(n) 个整数,表示数列 (A) 答案不唯一,任何合法答案都可接受

输入样例

1 472080

输出样例

11 
34 -7 102 117 16 8 0 130 36 34 47

( ext{Solution})

贴题实在太累了。

首先,我们将 (n) 乘过去,就是平方和了。

我们发现,要使平均数为 (μ),我们构造的数必须是:(μ+a,μ+b,μ+c) 这种形式。(保证 (a+b+c==0))但这样还是不好构造。

其实我们直接将这种关系转化为两两匹配的就行了。可以知道,这样匹配的最低效益是 (2)(加一和减一)。所以,只要我们保证 (v*n) 是偶数就一定可以这样凑出来。那我们直接选偶数 (n) 就行了。

另外,这题看上去数据很大,其实用刚刚的匹配方法,每次选最大的效益,凑出来的数的个数是不会超出范围的。(每次减去一个在自己范围内最大的完全平方数的两倍)

( ext{Code})

#include<cmath>
#include<cstdio>

int T, u, len, n = 20;
long long v, tmp, num[100];

int read() {
	int x = 0, f = 1; char s;
	while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
	while(s >= '0' && s <= '9') {
		x = (x << 1) + (x << 3) + (s ^ 48);
		s = getchar();
	}
	return x * f;
}

int main() {
	freopen("math.in", "r", stdin);
	freopen("math.out", "w", stdout);
	T = read();
	while(T --) {
		u = read(), v = read(); v *= n;
		len = 0;
		for(int i = 1; i <= n; ++ i) num[i] = u;
		while(v) {
			tmp = sqrt(v >> 1);
			num[++ len] = u - tmp, num[++ len] = u + tmp;
			v -= (tmp * tmp << 1);
		}
		printf("%d
", n);
		for(int i = 1; i <= n; ++ i) printf("%lld%c", num[i], (i == n ? '
' : ' '));
	}
	return 0;
} 
原文地址:https://www.cnblogs.com/AWhiteWall/p/13553788.html