[游记] WC2021

· · 个人记录

讲课啥的都记不得了，只记得随机化算法没有前途和 ccf 的广告了

这些边我不加（小声），这些边我不加（大声），暴力怎么做？！暴力是不是！加边！加边！加边！然后并查集查询！

直接快进到考场

为啥华二紫竹比我们学校初中加高中大至少5倍啊

我，sxw，def，lgd，return 一起走还走迷路了

压缩包密码是新年快乐好评

开场半个小时稍微看了看三道题，大概 T2 是最阳间的，T3 是最好拿分的

然后开始做 T2

然后发现没有问号有一个 \mathcal O(n|E|) 的大模拟，然后写掉了，过了样例

又想了想用计数器维护每个数出现了几次然后暴力转移就有一个 \mathcal O(nm^2|E|) 的dp，用前缀和优化就可以做到 \mathcal O(nm|E|)

写完过了样例就大概两个半小时了（菜 UM 菜）

接下来花了 10min 写了 T3 的 20pts 暴力就去想 T1 去了

发现有一个类似 floyd 的转移，每次更新再暴力向外扩展，加上一点剪枝

稍微分析了一下复杂度，感觉是 \mathcal O(n^3+m^2) 的（为啥大家复杂度都这么高啊，感觉大概率是我假了吧）

写完大概就剩 1h 了

然后感觉 T1 没前途了，回去想 T3 去了

看了眼 T3 的大样例，感觉答案不会很大，就打了一个斐波那契数列的表，加上求逆，大概能过 40pts

估分：32+70+40=142，实际得分 40+70+40=150，Ag

谁让我NOIp考的那么差的，不然都有可能混个市队/dk/dk

考场上 T2 n|E|=2.5\times 10^9 算成了 2.5\times 10^8，还以为能过 85pts（

菜 UM 菜