WC2021游记

· · 个人记录

Day -1 复习

刷模板刷模板刷模板……

水了一堆SAM和DS的题，重点复习了一下数论（机械键盘真好听(雾)）

有一种强烈的预感要考数论

Day 1 考试

考前

又不能带吃的，烦

排队的时候看到了一堆大佬，默默膜一下增加rp

进考场周围围了一圈大佬的我瑟瑟发抖

感觉上了个厕所就开题了，密码是“XinNianKuaiLe”(来自组委会的rp++)

一看都是传统题，缓了口气，然后嘛……

结果还是三道毒瘤，于是上来就把显然的T3暴力先打了

T1

先搞题意简洁的T1，在草稿纸上画了画，推出一个结论：如果A到B有括号路径，那么A和B可以合并起来当一个点用，最后每个连通块内任意两点间都有合法路径

很naive地写了20行并查集然后样例挂了

又画了一下发现合并后会有连锁反应，所以写了个启发式合并维护一个点的入边集合（一个颜色只存一条边），然后再拿个队列记录更新操作

然后手造大样例T了

冷静分析了一下发现我合并复杂度是max\{sz\}，于是搞了个链表把复杂度优化成了min\{sz\}

T2

看了眼数据范围发现没?的有50分，果断写了个大模拟

然后想了个很暴力的dp，dp\ n次，设f[i][j]表示当前在第i个字符，答案为j的情况数，转移简单推一推，遇到括号的话就枚举括号表达式的答案，然后和其他情况一样处理

两部分加起来应该有70

一看代码有5k

T3

一顿乱推发现就是要求Afib_i+Bfib_{i+1}\equiv 0(mod\ m)

于是m为质数的分就到手了，预处理\frac{fib_i}{fib_i+1}即可（由于这个东西有循环节的，所以答案不会很大，预处理的时候到fib_i=0就可以break了）

然后另外20分就是excrt合并一下，结果考场上没时间，没调出来

赛后

高二的哥哥姐姐貌似都没做出T1，有点慌

T2括号嵌套好像锅了(((A)))这种情况会WA

T3白给20分，第一个暴力部分分没加上去

估分100+70(?)+20

成绩

和估分一模一样（雾

这次算是正常发挥吧，唯一的问题在于最后十分钟心态有些慌乱，白给了20分，果然考试慌不得QAQ