NOIP2017 小结

Day0

傍晚来到衢州登记+入宿，然后看完了一部《叶问2》？？？晚上又看了一会儿《超凡魔术师》…很快晚上就过去了，感觉啥也没复习

Day1

考前交流了一发ExGCD，于是D1T1就写了ExGCD做法-_-，知道正解之后一脸懵逼……

T2大模拟很快就糊过去了，花了两小时刚T3却一直在考虑缩点后dp……菜如我滚粗。

下午就开始颓废。四处乱串之后去其他房间一起观看了《奇异博士》&《月球》（话说点播电视不错嘛）（天天看电影吃枣药丸）晚上点了金拱门外卖同时观赏《爱情公寓3》（药丸

Day2

T1完全没考虑到什么爆long long啊double炸精度啊啥的，从容用了double……

T2糊了个假的prim就不管了，果然GG

T3花了两个半小时没搞出来……最后连暴力都没打满……30滚粗。

下午高(m)高(m)兴(p)兴地回到学校，想必滚粗了

NOIP2017，完。

以下是题解

D1T1 小凯的疑惑

唔，先讲讲正解吧。对于输入的两个数$a,b$，输出

证明就不用了吧。然而我写了ExGCD，耶……

至于ExGCD么，是这样的，求方程

的一组绝对值最小的解，ExGCD即可。可以发现$x$和$y$一正一负。这样通过变换可以得到另一组解$x’,y’$，且$x$与$x’$正负性相反，$y$与$y’$正负性也相反。这样我们就可以发现，对于任何一个值，如果有$ap+bq=W (p \geq 0, q \geq 0)$，且$p-x \geq 0 (x \geq 0,y \leq 0)$，同时$x,y$满足$ax+by=1$，那么就有$a(p-x)+b(q-y)=W-1$。那么我们只需要构造最小的一组$p,q$，使得$p-x < 0, q-y’ < 0$，其中$p,q,x,y’ \geq 0$，那么答案就是$ap+bq-1$。也就是说，需要找到一种合法方式（设所构成的值为$W$）使得$W-1$不能通过上述变换构成，那么这就是答案。

想必这个过程证明是不严谨的，但我当时在考场上就是这么想的，并与暴力对拍验证了一下，就写了这个。

（btw，这题不清真啊，D1T1居然不是一眼题，居然卡了一堆人，这不是我心中的D1T1……

D1T2 时间复杂度

思考难度不大诶……不过容易写挂，还有一些坑点。比如：

1. 被跳过的循环里也有可能CE，需要判（题面里也写了

2. 循环中的变量可能会有n到n，这是O(1)的。

3. 一个循环被跳过了，那么里面的循环也都被跳过了（可能会忘记实现

4. 同一层中如果前面的循环被跳过了，那么后面的循环并非也被跳过了

于是我开了两个栈，一个存时间复杂度，一个存这层循环是否都被跳过，边读边判断即可，复杂度$O(n)$。

D2T1 奶酪

简单的空间距离判断+并查集或者BFS。

出考场发现double可能会被炸精度，瞬间方了……还好出题人没卡。

D2T2 宝藏

Prim贪心是错的。本来看到$n \leq 12$就知道是道状压，然后还是写了Prim……45分滚粗

状压DP。$dp[i][j]$表示生成树深度为$i$，状态为$j$的最小花费，转移：

$cost[i][j]$表示状态$i$到状态$j$的花费（不管深度）。预处理即可。

转移是$O(3^n \times n)$的，要枚举补集。