标签：删除 NOIP times VP 2022 Day dp size

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！！！

标签：删除,NOIP,times,VP,2022,Day,dp,size
From： https://www.cnblogs.com/mk-oi/p/NOIP2022VP.html