【GMOJ4282】平方数游戏

题目

题目链接：https://gmoj.net/senior/#main/show/4282

思路

考虑到任意 8 个连续的数必然存在以下方案将和变为 0：

[a^2-(a+1)^2-(a+2)^2+(a+3)^2-(a+4)^2+(a+5)^2+(a+6)^2-(a+7)^2 ]

而通过模拟退火可以得到 (1sim 15) 的答案，发现 (8sim 15) 的结果全部为 (0) 或 (1)，通过奇偶性容易得出这已经是最优解了。
所以打出 (1sim 15) 的表，后面每 (8) 个数为一组做即可。
时间复杂度 (O(n))。

代码

#include <bits/stdc++.h>
using namespace std;

int n;

void check(int n)
{
	if (n==1) printf("1
1 ");
	if (n==2) printf("3
1 -1 ");
	if (n==3) printf("5
1 1 -1 ");
	if (n==4) printf("2
1 1 1 -1 ");
	if (n==5) printf("3
-1 1 -1 -1 1 ");
	if (n==6) printf("1
-1 1 -1 1 1 -1 ");
	if (n==7) printf("0
-1 -1 1 -1 1 1 -1 ");
	if (n==8) printf("0
-1 1 1 -1 1 -1 -1 1 ");
	if (n==9) printf("1
-1 1 1 1 -1 -1 1 1 -1 ");
	if (n==10) printf("1
-1 1 -1 -1 1 -1 -1 1 -1 1 ");
	if (n==11) printf("0
1 -1 1 1 1 -1 -1 -1 1 -1 1 ");
	if (n==12) printf("0
1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 ");
	if (n==13) printf("1
-1 1 -1 1 1 1 -1 1 -1 -1 1 1 -1 ");
	if (n==14) printf("1
-1 1 1 -1 -1 1 1 1 1 -1 1 1 -1 -1 ");
	if (n==15) printf("0
-1 1 -1 1 -1 1 1 -1 1 -1 1 1 1 -1 -1 ");
}

int main()
{
	freopen("five.in","r",stdin);
	freopen("five.out","w",stdout);
	scanf("%d",&n);
	if (n<=15) check(n);
	else
	{
		check(n%8+8);
		for (int i=1;i<n/8;i++)
			printf("1 -1 -1 1 -1 1 1 -1 ");
	}
	return 0;
}