复盘
时间安排
- 8:00~8:30写&调T1，过样例
- 8:30~9:10胡T2，过样例
- 9:10~9:40研究T3，写了个错误的DP，FALSE
- 9:40~9:45看了眼T4，骗了点分
- 9:45~10:00摸T3正解，摸了一大半然后（就没有然后了）
部分分
- 正解（100/100）
- 正解（0/100）
- 无
- 骗无解情况（10/？）
失误
T2没写freopen，寄…
题解
T1
选择一个数替换。
替换的数并不能使GCD“更大”，最多只能使GCD不会“更小”。所以并不需要考虑替换的数本身。替换操作就相当于把这个数删除。
于是问题就变成了，求删除一个数后的最大GCD。
已知
\[gcd(a,b,c)==gcd(gcd(a,b),c) \]同理可以把原数列从被删除数处拆分成两半。则删除该数后的数列\(gcd = gcd(gcd(left),gcd(right))\)
并且也由于上述原理，可用前/后缀维护GCD。
最终时间复杂度\(O(n\log{n})\)
T2
从大到小枚，如果在原位置后边就给换了。换的时候更新答案序列。
最终如果没有换成目标状态，或者答案序列长度不为\(n-1\)，则无解。
有解则输出答案序列。
T3
关于平均值的处理，一般有两种。
\[\bar{a} = \frac{\sum{a}}{n}\]或
\[\sum{a_i-\bar{a}}=0 \] 标签：20230704,10,gcd,T2,T3,赛后,100,复盘,GCD From： https://www.cnblogs.com/meteor2008/p/17525683.html