NOIP 2022 VP 白给记

· · 个人记录

在我的博客获得更好的阅读体验

NOIP 2022 VP 白给记

Day -?

浙江 NOIP 初中生不能参加。
【数据删除】你【数据删除】【数据删除】了！！

Day 0

机房里陷入了最后的狂欢。

然而 NOIP 是他们的，我什么也没有。

傍晚 17:00 他们出发，所以 16:25 吃晚饭，我也跟着去了。
气氛挺压抑的，大部分人都知道 NOIP 之后他们就退役了，挺伤感的。

晚上给每个人发了 NOIP RP++,Score++，结果傻逼 QQ 给我号冻了……
QQ 你【数据删除】什么时候【数据删除】啊？

Day 1

模拟赛，然而我是出题人。

赛时没什么大锅，测出来分也挺好看，区分度有 38。
然而因为数据全是随的被一车乱搞过了，于是就是经典的赛后加强数据（逃
数据加强后区分度只有 28 了，难蚌。

Day 3

上午偷学，下午 VP。

按照 td 的意思 12:10 就该去另一个机房了，结果饭吃完已经 12:16 了，难蚌。
傻逼 td 没有装好 gcc，要自己装，更难蚌了。
12:30 开始，我还在配 Sublime 结果大家都开打了，周围都是啪啪啪啪啪的键盘声，很慌。

配完 Sublime 开题，看完 T1 和 T2 题面后去想 T1，想了一会只会 O(n^2m)，小丑了。
又过了一会会 O(nm) 了，直接开写。

写完后又看了眼 T3 题面，权衡了下发现 T2 绝对是个阿拉丁题于是开 T3。
首先一眼想到缩点，缩完后是一棵树，考虑树上怎么统计答案，想了一会大概只能树形 DP。
发现如果确定军营后就会有一个子图上的边必选，剩下的随便选，于是状态一定和点有关。
一开始设计了个 dp_i 表示仅考虑以 i 为根的子树内的答案，然后测样例发现寄了。想了一下发现合并答案的时候子树到根的边的状态不确定。于是又思考了一下发现如果有多于一棵子树（根节点视为单独的一棵子树）内有军营，那么这些子树到根的边必选，否则可选可不选，于是设计出 dp_{i,1} 所选的所有小子树都与根相连的答案，dp_{i,0} 表示所选的小子树不与根连通的答案（因为不一定连通，所以只能选一棵小子树。）的状态。
于是容易写出状态转移方程：

dp_{u,0} = dp_{u,0} \times 2^{size_v+1} + dp_{v,0} \times 2^{size_u+1} + dp_{v,1} \times 2^{size_u} dp_{u,1} = dp_{u,1} \times 2^{size_v+1} + dp_{u,1} \times dp_{v,1} + dp_{v,1} \times 2^{size_u}

然后就做完了。用时 1h30min 左右。

再看眼 T4 题面，感觉很可做？然而肝了半个小时还是不会，回去看 T2，才发现是个几把构造。k=2n-2 很好想，然后就不会了。一直罚坐，无果，就写了两个暴力。

还剩半个小时，继续想，还是一个也不会，开摆！
预计得分：100+15+100+20=235

结束了，打算复刻经典场面，于是大吼一声：我爆蛋了，我没上 250！

上洛谷测，T2 F 了，0 分！

lanos F 了 95 分还是以 5 分的巨大差距吊打了我，太强了，狂暴膜拜！！

问号，看了眼 InfOJ 测出来的结果，这个分在浙江 rk54？【数据删除】【数据删除】，你还我 NOIP！！！