Noi+

· · 生活·游记

Noi+

寄了，感谢眉目清·秀出题人。

总结一下，T2 没磕出来，花了若干时间徘徊于 T2T3，没有果断跳。

是的，没有果断地以 9.8m/s 地加速度跳，我就失算了。

打开 T1，瞄一眼，怎么又双叒叕是贪心，因为反悔贪心打傻了，一眼反悔贪心，先晾着，看看 T2。

T2 一看，云里雾里的，这也是题？一看出题人就长得眉目清·秀，甚至不是 dp，也晾着。

T3 一看，更不得了了，乍看一眼以为是神秘构造，在瞄一眼感觉像是 dp，又像树上背包。

看一眼 T4，神秘大 ds，如此新颖，就连纯粹的暴力连 4 分都没有，大毒瘤。

此时已经 8:45 了，回去打 T1。

先想了想，肯定选 x+y 最小的，因为要反悔，于是想到先全选 x+y 最小的，在反悔撤销，每次撤销一堆看能否选 x 较小的其他糖果。

随便打了一个垃圾东西，轻松过掉第六个小样例，结果挂第四个了，仔细一看，最小的 x+y 是 1,37，如果把 37 撤掉就能接着选，又判了以下，都过了，因此就不管了。

已经 9:30 了（大概），看 T2。仔细摸了一遍样例，发现选了不优的一定是形如最大的两个 w=1 的 a 之和不如一个 w=2 单选，并且是最后选，所以会炸。

所以先打了个 m=2 的部分分，就是先排个序，然后判一下每个数作为 w=2 被篡了的方案，写错了好多遍，打完已经 10:20 了，又调了个暴力就 10:40 了，检查一下，只有 48 分。

然后去想 T3，很明显每个子树覆盖的是一段前缀和中间的一段，开始打 dp，就硬打，因为推出式子了，也就五次方复杂度。

没打出来，浪费了 1 个小时，于是果断打状压。

打着打着，状压也炸了，仔细一想，式子没错，原来还要维护可达性，但是心态已经炸了，干脆先把状压暴力调出来，结果又化了半小时。

然后去想 T4，想了个线段树优化暴力，O(qn^2\log n)，就是之间区间取 max，但是要跑 10s 才能过 n=3000，于是每个段存了个 min，优化一下要跑 3s，直接不管了，因为只剩 45 分钟了。

接着看 T4，放弃。

接着看 T3，放弃了，太难调了。

接着看 T2，放弃推式子了，又不是 dp，只能应算，但是我没从 m=2 推广出充要，我就是废物。

接着看 T1，放弃对拍，暴力打了 15 分钟，结果没拍上，只剩 15 分钟了，不管了。

情欲赤橙黄绿青蓝紫青鱼告诫我只剩 15 分钟就啥也不要干了。

摆了，如此简单的 T2 我竟没做出来，T1 打了个非常假的做法，满脑子反悔贪心与 dp。

好伤心，在信息学方面被暴虐，YYZ1208 带 debuff 依旧爆切 T2，T3 推出 O(n^3)，我们根本就不是同一个级别的。

好伤心，T2 差一点推出充要，T3 没想到可以直接数有多少个贡献到祖先，T4 依旧毫无思路，就连 T1 也有极大概率挂掉。

哎，谨此记我的可怜 noip 邮寄。

哎，明日方舟好玩，还是羽毛笔好涩，但我好像也不适合玩，半周年歪了三个一个都没中（其中还有一次是双黄毁心态）。