NOIP2021 GG 小记

早上起床，有点像上厕所，又好像没有，忍住了，走到考场门口，憋不住了

匆忙打模板，开始看 T1

看到数据范围的第一眼就只到这会是一个 \(O(n)\) 的玩意

考虑把条件列了出来，发现其实就这一个条件：不为十进制含 7 的数的倍数

想到了一个方法叫做所谓”新定义素数“，想到了线性筛

打完，大样例过了，自己随手造了几个小样例，发现好像也没有问题，开始看后面的题

这个时候大概是 9:20 吧

9:40 左右把题目大概都看完了，仔细想了一下 T2

没有头绪，发现暴力选数居然是 \(O(m^n)\) 左右的，暴力分都不给，过分，直接跳了

10:00， T3 第一眼看到那个 \(a_i^{\prime}=a_{i-1}+a_{i+1}-a_i\) 的时候以为是什么带悔贪心，只是需要转化一下题目

10:10，突然发现自己看漏了单增的性质但没有多想

转化了半天，不会，开始着手研究改变一个数 \(a_x\) 之后答案会产生怎样的变化，以图发现一些东西

（下面这部分全是废物）

开始推：设 \(S=\sum a_i\) ，可以得到原贡献为 \(n\sum a_i^2+\frac 1n S^2-2a_iS\)

假设我们改掉 \(a_x\) ，那么新的 \(S^{\prime }\) 和 \(S\) 的差值为：

\[\begin{align} diff&=S^{\prime 2}+\sum(na_i^{\prime 2}-2a_i^{\prime}S^{\prime})-S^2-\sum na_i^2+\sum2a_iS\\ &=S^{\prime 2}-S^2+n[(a_{x-1}+a_{x+1}-a_x)^2-a_x^2]+2\sum (a_iS-a_i^{\prime}S^{\prime})\\ \end{align} \]

?不妨设 \(\Delta = a_{x-1}+a_{x+1}-2a_x\) ，显然 \(S^{\prime}=S+\Delta\) 下面重点考虑后面那个 \(\sum\) 是什么东西

\[\begin{align} 2\sum (a_iS-a_i^{\prime}S^{\prime})&=2(-\Delta S-\Delta\sum a_i^{\prime})\\ &=2(-2\Delta S+\Delta^2) \end{align} \]

所以

\[\begin{align} diff&=\Delta^2-2\Delta S+n[(\Delta+a_x)^2-a_x^2]-4\Delta S+2\Delta^2\\ &=3\Delta^2-6\Delta S+n\Delta^2+2n\Delta a_x\\ &=(3+n)\Delta^2+(-6S+2na_x)\Delta \end{align} \]

10:40 检查完式子推错没有，长舒一口气，开始看这个式子是个什么玩意，发现对原问题好像没有帮助，心态有点小炸

回头看了一眼 T2 ，铸就这场比赛最大的伏笔：

嗯...... 考虑 DP？

woc，好像直接暴力 DP 很好写的样子，分也很多？

好的，那么我待会再写

于是我自信地在草稿纸是那个写下了这样几个字：“T2 考虑 DP 即可”，然后继续想 T3。

10:55 看到 \(a_i\leq 600\) 的值域，想起了 \(CSP2020-J2\) 考场上忘记桶排的恐惧，果断开了一个 \(tong[]\) 数组

开始乱搞，发现相连的一段可以合并，乱证了一个贪心，写上去发现样例都过不了

11:45 放弃 T3 ，回头 打T2暴力 ，发现这个暴力我只需要按递增顺序枚举就可以了，加一个组合数好像可以优化掉

12:05 打完 T2 暴力，直接去打 T4 暴力

13:00 T4 暴力最终还是没有调出来，GG

出考场门，深吸了一口新鲜的空气，扬手看到自己草稿纸上写着：

T 2 考 虑 D P 即 可

人傻了。