GDKOI 2022 破防记 Day1

lzqy_ · 2023-03-11 19:10:56 · 个人记录

彩票竞赛谁爱学谁学。

-1h

到六中，面基了两三个人。

很困，感觉状态不是很好。

0~1h

看了遍题，感觉可做程度是 C>B>A，梦回nj模拟赛。

不过还是象征性地先看了看T1。记得矩阵乘法最快只能用一个 n 的二点几次方的科技，但是显然不可能考这个，那应该是一些神秘的乱搞，不太会。

1~2.5h

由于觉得 C>B，所以决定先敲 B 的部分分。

从来都记不得错排的容斥式和递推式，推的很痛苦。

这里浪费了 1.5h 最大的原因是偷懒，没有仔细思考递推的组合意义，而是选择打了个表然后穷举转移方程。最后发现需要数组辅助转移。搞了将近 1h。

敲了 O(nm+Q) 的暴力 dp 走人。

2.5~3h

比赛第一遍看题的时候就觉得C是比较经典的dp套dp，尤其是 n \le 15 的数据范围。直接拆成 n\times \log C 的矩阵，按照数位dp的方法填数。发现填完第 i 行时需要的信息只有每条边是否满足条件以及每个数是否顶着上界。这玩意儿上界是 O(2^{n+m}\log C)，但实际山有用的状态数只有大约 5e5 个，是可以跑得动的。

随便造了组极限数据，发现跑得意外的慢。分析之后发现虽然状态数可以接受，但是从一个状态往后转移的时候，需要 2^n 枚举当前位，也就是说时间复杂度还要乘上一个转移的 2^n。所以就炸了。

想了很久，都没办法优化转移过程，也不能先把内层dp的自动机建出来（因为每一层条件差异太大了，暴力建自动机直接卡满 O(2^{n+m})）。只能先弃了。

3h~3.2h

回头打 A 的暴力。

这次看题的时候发现有一种乱搞是随机撒点判断有无解。也不知道那时候是怎么想的，觉得很难卡，觉得 1-(\frac{n^2-1}{n^2})^n 的概率很大，于是就赶紧写了发随机撒点上去。

3.2h~4h

又回头看了看B，但是感觉递推的时间复杂度瓶颈肯定是卡在 O(nm) 上的，如果想优化一定是从错拍的容斥式出发。由于比较笃定dp的做法是死路，所以没有怎么细想。

于是把所有时间拿来冲C。

由于一层一层转移行不通，所以考虑一个一个地转移。但是由于一个一个地转移还需要关心当前层填了什么，相当于减少了 2^n 的转移复杂度但增加了 2^n 的状态数，所以还是过不了。

重构了很多次，比较麻。n=10 已经到本地的极限了。

再回头看部分分，暴力分的下一档就是 n \le 13。。。

唯一不同于暴力的一档部分分就把 n 减小了 2？？？？

也就是我卡了一场的dp套dp，比爆搜不知道优了多少倍的dp套dp，只能和暴力同分。

比较难蚌。

然后老师又说了一个题意补充。C题捆绑。

赛后

居然是 wxw 的题/jy/jy 磕头了。

出考场冷静了一下，发现 A 随机撒点错误的可能性非常高。不知道场上是哪根筋抽了。

问了月神 B 的做法，果然是容斥推完之后构造生成函数卷积，和我考场上的猜测比较一致。

不过后来听了 wxw 的讲题，std B 的做法居然就是从递推式出发的。这个时候猛的想起来斯特林数列求值的方法。而B的式子和斯特林数基本相同。蚌埠住了。可是我根本不会那两道板题。

最后听了T3的做法，是一个比较中规中矩的容斥，和我考场的做法不能说一模一样，只能说毫不相关（

这也可以解释为什么没有 n 稍微小一点的部分分了。因为std的周边做法根本不存在这一档的时间复杂度。

总结

期望得分：

不过感觉 C 的 n \le 13 不太可能冲过去。

这场 A 和 B 的想题时间基本为零，都在冲C题。但是形同虚设的部分分+捆绑破大防。

如果 C 真的按照 n 分层给分，或者说不捆绑，至少我不会只有大众分。

A 题乱搞随机区分，B 题多项式区分，C题部分分不区分。

只能说是彩票竞赛了。

免责声明：

题本身是好的，组题人也是好的，组出来的比赛也是不差的。

只是技不如人。

再加上这个竞赛本身就他妈彩票。

彩票竞赛。

后记

发成绩了。

感谢A不卡之恩。不过据说多撒几千个点就能过了。比较可惜。

不过还是C比较难蚌。果然CNOI的大样例永远是不可信的。这个 0 分显得我在考场上是个小丑哈哈（

据说人均 180。感觉Day2没有翻盘的希望了捏