WC2021 游记

· · 个人记录

Day1:

上午：《随机化算法》
下午：《随机化算法没有前途》

Day4：

讲了一堆用不上的东西，上午是逻辑和形式化验证，下午教你用多线程并行卡常。

Day5：

想着打三个暴力跑路。

T2 没有 ? 的情况直接写了个 O(n|E|) 的暴力模拟，理论上只有 50pts，然后随手卡了下常。对于有 ? 的情况，拆成 n 个 n=1 的情况的答案的和，就把上面的计算函数复制了一份然后改了改，O(nm^2|E|)，两个做法拼起来 70pts，大概 10:10 写完。

然后开 T3，看到斐波那契数列就顺手敲了个矩乘板子上去，敲完是 10:40 结果发现用不上，就去开 T1 了。

T1 看起来很不可做于是打算写 32pts，直接写了个 dfs，对每个点搜一遍记录到其他点可以达到的括号栈状态，写完测下样例过了就回去写 T3 了。

T3 看了一会发现 F_i=af_i+bf_{i-1}，并且知道有 fib 循环节，但是想了半天还是只会 O(nm)，有想过把这东西移项然后除一下但是没有继续往下想，于是打个 20pts 暴力跑路，写完差不多是 12:10。

剩下的一个多小时我也不知道我干了什么，大概是又想了几个假做法，都是写到一半发现不对，最后什么都没改。

预计得分 32+70+20=122。

下午发现自己 T2 多写个 ++i 导致出现 ..((0))... 或 (...)... 时会 RE，不过据说 ctr 随的数据，希望能过。

Day6：

上午候选队答辩，那个压位 trie 支持 插入删除前驱后继 正好就是我几个月前研究的 64叉树（这也太巧了吧

下午闭幕式公开处刑，从低分往高分念。一直到 122 都没有看到自己名字，感觉是 Fe 了，结果最后是 137，T2 的 O(n|E|) 暴力多艹了 15pts（需要卡亿一点常）。据说 T2 的正解常数大点也会被卡成 85。

Day4 教我们暴力艹题，于是 T2 就被暴力多艹了一档（虽然不是用并行