jzoj4282-[NOIP2015模拟10.29B组]平方数游戏【构造】

正题

---

题目大意

构造一个$a_i=\{1,-1\}$使得最小化$$|\sum _{i=1}^n{a}_i{i}^2|$$

---

解题思路

我们发现有对于一段连续的$x^2-(x+1{)}^2-(x+2{)}^2+(x+3{)}^2=4$，那么就有$$x^2-(x+1{)}^2-(x+2{)}^2+(x+3{)}^2-(x+4{)}^2+(x+5{)}^2+(x+6{)}^2-(x+7{)}^2=0$$

那么我们对于连续$8$个就可以抵消掉，特判掉$1\sim 5$，然后预处理出$6\sim 13$的答案然后后面都按这么填取$0$即可。

---

$code$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int main()
{
//	freopen("five.in","r",stdin);
//	freopen("five.out","w",stdout);
	scanf("%d",&n);
	if(n==1)printf("1\n-1");
	else if(n==2)printf("3\n1 -1");
	else if(n==3)printf("4\n1 1 -1");
	else if(n==4)printf("2\n1 1 1 -1");
	else if(n==5)printf("3\n-1 1 1 1 -1");
	else{
		if(n%4==1||n%4==2)printf("1\n");
		else printf("0\n");
		if(n%8==6) printf("1 1 -1 1 1 -1"),n-=6;
		else if(n%8==7) printf("-1 -1 1 -1 1 1 -1"),n-=7;
		else if(n%8==0) printf("1 -1 -1 1 -1 1 1 -1"),n-=8;
		else if(n%8==1) printf("1 1 -1 -1 1 -1 1 1 -1"),n-=9;
		else if(n%8==2) printf("1 -1 -1 -1 1 1 1 -1 1 -1"),n-=10;
		else if(n%8==3) printf("-1 1 -1 -1 -1 1 1 1 -1 1 -1"),n-=11;
		else if(n%8==4) printf("-1 1 -1 -1 -1 1 -1 1 -1 1 1 -1"),n-=12;
		else if(n%8==5) printf("-1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 -1"),n-=13;
		for(;n;n-=8)printf(" 1 -1 -1 1 -1 1 1 -1"); 
	}
}

本文地址：https://blog.csdn.net/Mr_wuyongcong/article/details/109242173