GDKOI 2023 游记 Day2

lzqy_ · 2023-03-12 19:50:44 · 个人记录

这场挂的分也算勉强能接受。虽然也有很大遗憾，但这显然是OI赛制难以避免的特性了。

姑且就算不翻不挂吧。

-1h

比昨天更困了。

qq上找了好几个人帮我带咖啡，但是都没理我（

0~0.2h

看了遍题，还是觉得A>B>C /qd/qd/qd

看到有两道树，觉得能翻盘，但是看到概率给我干蒙了。

（谁能想到最后脱离大众分居然靠的概率题

0.2~2.5h

在AC里随便挑了一题开。不是很相信自己的判断，于是还是准备开A。

分了四种情况讨论的一下，发现本质都是解同一个三元一次方程组。对于每个节点处理出前三长的链之后就是个三位偏序的构造问题。

但是代码非常难写，写完拍完之后已经只有 1.5h 了。很慌，代码能力简直普及组水平。

2.5～2.7h

因为时间太紧，所以只是大概想了想C，发现难度比我第一遍读题预设的要高。而剩下的时间也不足够一档一档部分分地打了，所以决定到时候回来拿 10 暴力分就行。

2.7h～3.5h

于是决定冲 B。n \le 8 是平凡的，矩阵快速幂就可以。对于 K 比较小的数据，发现 dp 转移式子中，从 i,j 转移到 k,u 时， f_{i,j} 的转移系数和 k,u 无关，所以就是正反两个高维前缀和，分别跑 2K 次正的 FWT 和 反过来的 FWT 就行了。

不过 FWT 早忘光了。现推了一下，还好一遍写对。

但是好像冲不过 K \le 10^3 的部分分，卡了挺久也没用。

3.5h～3.6h

忍住了继续卡常的欲望，回去补了 C 的暴力。

3.7h～4h

前面卡常卡魔怔了，矩阵快速幂都没写，甚至 n=1 的分都没拿。不过剩下的时间并不能保证写对，权衡了以下决定继续卡常。

极限数据用时卡少了 7s，但还是没卡进去。

总结

估分：

这场题其实还挺符合我的风格的，就是可惜 A 调了太久，导致 BC 都是奔着暴力分去的。比较可惜。如果时间足够，多个五六十还是没问题的。

代码能力太差。比较遗憾。

后记

滚榜出成绩了。

A cdq 里面写sort被卡了一个点，好似（

后两题都还算正常了。

不过最后讲题也没说 K \le 10^3 是给什么做法的/qd/qd/qd

感觉有点敷衍（

两场比赛打下来都是时间不够，要练代码能力了（悲