NOIP 2018

吐槽

一天普及一天省选，弄到一起就出成了一套提高组试题。

Day1

原题大作战。 然而我一题都没做过。

总的来说 Day1 比去年好像容易点（不然我也不会留出一个多小时给每道题造数据对拍）。

T1

CCF 直接把 2013 的题原封不动搬到了 Day1T1 。

一开始想着递归，发现会被卡成 \(O(n^2)\) ， 再想 DP 的时候简化一下式子就直接可以扫一遍出结果。

T2

bzoj 权限题。

如果一种货币能被其它若干货币代替，就扔掉。 设 f[i] 表示价值为 i 的货币是否会被代替，做一遍完全背包就好了。

T3

bzoj 权限题。

听说可以二分加贪心，不过我考场想的比较复杂 是二分答案再 DP ，DP 转移再套一层用链表维护的 DP 。

首先容易想到二分答案，二分一个答案 mid 后求最多可以有多少条赛道满足长度不小于 mid ， 若有不少于 m 条，则答案可行。

求赛道数量可以 DP ，设 f[u] 为 u 的子树中满足条件的赛道的数量， g[u] 表示在满足 f[u] 最大的前提下 u 向下不经过赛道的最长路径长。

转移的时候先把 u 的儿子 v 的 f[v] 累加，同时将所有 g[v]+w 存起来（w 表示 u 到 v 的长度）。

对于 g[v]+w 大于等于 mid 的直接把 f[u]++ 然后扔掉，于是只需要考虑小于 mid 的 g[v]+w 的贡献。

两个不同的 g[v]+w 若大于等于 mid 就同样可以作为一条赛道让 f[u]++ ，先排序然后再次 DP 统计这样的赛道数量， 然后若所有的 g[v]+w 都有另外一个构成赛道， g[u]=0 ，否则 g[u] 等于剩下的最大的 g[v]+w 。

Day2

Day1 的比赛对我造成了巨大的影响，Day1 考完后信心爆棚， 以 AKIOI 的自信 走进 Day2 考场。

结果什么题都死磕正解，到最后连暴力都没打全。

看题，WTF?

看完 T1 我以为是个稠密无向图，想了好久感觉是要求一种特殊的生成树，感觉巨不可做。 顿时有点小慌，突然想到考前教练提醒要看完题，说不定后面的题反而简单。

嗯，有道理，直接翻到 T2 ，推了波结论认定是一道状压 DP，松了口气。

不急，再看 T3 ，哦，好像树形 DP ，但是 m 个询问难住了我。

于是认定 T2 比较容易，开始死磕 T2 ，打完状压后跑了遍 2,2 的样例，诶过了。 再跑一遍 3,3 ，输出 144 ，于是手推了 3,3 的样例发现还是 144 , 意识到推的结论有误，瞬间慌的一批。 推了好久才发现了问题，得到正确的结论后发现对于新结论状压 DP 似乎变得不可行。

这个时候考试已经过了一个小时多了。慌。

换换思路吧，于是去做 T3 , 想了很久 DP 最后写了个平方复杂度的， 跑过了所有样例就没管了，没多少时间了，又回去看 T1 。

往回看了看 T1 里 m 的数据范围我才发现只有树和换套树两种情况。 那还求个鬼生成树，迅速打掉树的 60 部分分，n 看都没看只知道 \(O(n)\) 稳了。 再去想换套树，感觉差不多，继续 \(O(n)\)做。

结果？一直死磕 T1 的 \(O(n)\) 做法，直到最后考试结束都没写出来。

考试听别人说直接枚举删边 \(O(n^2)\) 就可以过的时候我才意识到 n 只有 5000 ，整个人懵的。

结果 T1 还是 60' ，T3 不晓得哪里炸掉了爆零， 有意思的是 T2 我错误的打法样例都没过在 ccf 的数据里水到了 45' 。