输出方案这个idea是小E的

· · 题解

简要题意：给定一个数列，询问最少将数列中多少个数字修改为另一个非负整数，才能使得数列中任意相邻两个数之和都是完全平方数。

算法零

保证 n=2。

那么如果两个数之和是完全平方数，那么不用修改。否则任意修改一个数即可。显然可以满足条件。

期望得分 5 分。

算法一

保证 n=3。

首先如果 a_1+a_2 是完全平方数或者 a_2+a_3 是完全平方数的话，修改另一个数即可。

接下来分析 a_1+a_2 和 a_2+a_3 均不是完全平方数的情况。

明显的，答案不会超过 2。任意修改两个数显然是成立的。

所以我们关注的重点是在何时答案为 1。

同时我们可以发现，如果答案为 1 的话，我们要修改的数一定是 a_2。因为如果修改 a_1 或者 a_3，一定不能满足条件。

那么问题就转化成了给定两个数 a,b，判断是否存在非负整数 c 使得 a+c 和 b+c 均是完全平方数。

首先，在 a=b 时明显存在。运用算法零即可。

在 a\neq b 时，我们不妨设 a<b。令 d=b-a,a+c=x^2,b+c=y^2，则显然 y^2 - x^2 = d。令 u=x+y,v=y-x，则相当于找出 u\times v = d，满足 u,v 的奇偶性相同。

为了使得 c 能是非负数，我们希望 x 和 y 尽可能大。根据 x=\frac{u-v}2,y=\frac{u+v}2，显然 u 越大越有可能满足要求。所以对 d 进行分类：

最后我们将得到的 u 和 v 代入最初的式子计算出 c。如果 d\bmod2=1，计算得到 c=(\frac{b-a+1}{2})^2-b。如果 d\bmod 4=0，计算得到 c=(\frac{b-a+4}{4})^2-b。如果得到的 c\geq 0，那么把 a_2 修改为 c 即可。否则，答案不可能为 1，任意选择两个数进行修改即可。

期望得分 30 分。

算法二

保证 n=4。

如果四个数中存在相邻两个数之和是完全平方数，那么只需要按照算法零或者算法一进行处理即可。

接下来分析四个数中不存在相邻两个数之和是完全平方数的情况。

首先答案不会超过 3。只需要固定 a_1 然后运用三次算法零即可。

接下来考察答案是否可能为 2。

但是你会发现这样需要讨论好几种修改情况。能不能有一种通用的修改方式呢？

能。

接下来我们来证明：给定四个数 p,q,r,s，一定存在只修改 q,r 且使得四个数形成的数组满足条件的修改方式。

我们深入剖析一下这个修改方式。不难发现，修改 q,r 可以被看作是先构造出一个满足 p+q 是完全平方数且按照算法一能得到 r 的一组 q,s，再按照算法一算出 r 的过程。不难发现，我们要证明的就是这样的 q 存在。

首先，我们知道两个数之和是完全平方数，一定满足它们的和对 4 取余的结果是 0 或者 1。就是说，一定存在 q 使得 p+q 是完全平方数，且 |q-s| \bmod 4 \neq 2。

接下来我们只需要保证计算出来的 r 非负即可。那么我们把算法一中算出的 c>0 进行基本的不等式变形，可以得到 q<s 时有 q<s+1-2\sqrt s 或者 q<s+4-4\sqrt s （由余数确定），而 q>s 时有 q>s-1+2\sqrt s 或者 q>s-4+4\sqrt s。

那我们设 a 是满足 a+p 是完全平方数且 a\geq 0 的最小整数，设 b 是满足 b+p 是完全平方数且 b\le 10^8（虽然允许构造的大小是 10^{18}，但是 r 是 q^2 级别的且 10^8 足够）的最大整数。则根据乘法公式有 a\le 10001^2-10000^2=20001,b\ge 10^8-(14143^2-14142^2)=99971715。那么显然 a 和 b 中一定存在满足上面不等式的 q，否则可以得到 8\sqrt s>10^8 的显然错误的结论。

所以我们取 q 为 a,b 中满足不等式的一个即可。如果这时余数不对，那么我们可以取 a 的后一个或者 b 的前一个，也一定满足条件。

于是证明完毕。

当然这里的证明和构造有许多种方式，这里的证明只是其中一种。

于是使用上面的构造方式或者任意一种你喜欢的构造方式即可通过此部分分，期望得分 45 分。

算法三

我们还需要证明一个结论：给定 n(n\ge 4) 个数 a_1,a_2,\ldots ,a_n，那么一定存在修改 a_2,a_3,\ldots,a_{n-1} 的方案。

这个结论的证明是显然的。我们可以按照算法零的方法任意修改 a_2,a_3,\ldots,a_{n-3}，再按照算法二的做法修改 a_{n-2} 和 a_{n-1}。

所以我们就可以引出这个题的正解了。

我们设 f_{i,j} 是修改到第 i 位，当前连续修改的长度是 j 的最少修改次数。由于我们有刚才的结论，j 可以与 2 做最小值，即令 f_{i,2}=\min ^i_{j=2} \{f_{i,j} \}。

接下来考虑转移。首先 f_{i,0} 可以由 f_{i-1,0},f_{i-1,1},f_{i-1,2} 转移而来。f_{i,0}=f_{i-1,0} 的条件显然是连续两个数之和是完全平方数。f_{i,0}=f_{i-1,1} 的条件显然是 a_i 和 a_{i-2} 可以通过算法二得到合法的 a_{i-1}。而根据上面的结论，f_{i,0}=f_{i-1,2} 没有要求。

同时，根据 f_{i,1} 和 f_{i,2} 的定义可以得到 f_{i,1}=f_{i-1,0}+1,f_{i,2}=\min\{f_{i-1,1},f_{i-1,2}\}+1。

于是我们就解决了第一问。那么接下来问题还是如何修改。

首先我们可以倒推一遍这个 DP，得到哪些位置需要修改，哪些位置不需要修改。

显然可以发现每个需要修改的连续段是互相独立的。如果段长为 1 或者 2，采用算法一或者算法二的构造即可。如果段长大于 2，我们只需要按照上面结论的证明方法类似的思路进行构造即可。

期望得分 100 分。