GDKOI 2021游记
占坑。
qwq
Day 0
考虑了很久打不打CF，还是没打。。
Day 1
挺迟才起床。受到学长oql的鼓励，战力翻倍。
进场。
先把题目都看了一遍。t1什么鬼，最大割构造？。t2是原题，但我当时不会做，还没看题解。。。t3区间回文串，没啥思路，但感觉manacher起码可以骗很多分。但是我已经忘了manacher，已经准备好哈希了。t4题都看不懂。。
T1
想了20+分钟t1还没啥有用的思路，就去看暴力分，发现有个二分图。就想着随机化了。
策略就是随机选点出发，黑白染色。判断是否合法。
打完感觉挺稳。然后手打了个checker，拍了几百组感觉挺稳的。
T2
发现不是用端点来超级钢琴的套路，而是最低点。打个双端队列（其实后来发现单调栈也可以）来找到每个点管辖的区间。
然后二分
T3
哈希判断每个点管辖的区间。
然后就是求
这个不能直接求，听adam说可以用吉老师线段树。
二分答案，就知道对应的区间，然后在判断是否合法就可以了。
T4
一开始看错，还以为是
考场爆
出来发现是个思博任意模数分治NTT。
听说大家找到式子了，可惜的就是被任意模NTT送走了。
如果不继续推，是2log的。
应该有1log做法，懒得想了。
哦，是很难的多项式啊，那没得事了。
考后
估分100+100+100+0=300。
更新：t2挂了，100+40+100+0=240。
rk16
Day 2
考前
打了CF。只做了4道，又爆炸了。好困。。
将进考场又精神起来了。
进场。
看了看题，感觉t1是高斯消元，t2是个可持久化并查集或者LCT之类的，t3一眼就看出来做法，但感觉会卡
题面什么的可以去看xcy的博客
T1
仔细看发现
感觉不太熟练，半个小时左右才写完。中间还有些想错的。
T3
看了20分钟t2感觉不会。这时候我觉得后面的dp是线性的，我在想线性做法。又想了10分钟manacher，想不出来怎么弄了，遂放弃。
改成哈希加二分。然后写了个线性的dp。发现大样例错了，仔细想了一下发现是dp不能线性，要用线段树维护。
打完大概过了1h40min了。
T2
先在脑海中准备了两个暴力想法，一种是线段树暴力，一种是直接dfs暴力。
感觉线段树有点不可优化。
于是去想用LCT维护这个dfs暴力，发现只用管往前连的边。
但是这样忽视了向后的边的作用，很难维护，遂放弃。
此时因为已经过了两个小时了，于是开始打暴力。我不确定直接dfs的正确性，于是打了线段树。
打完对拍了一下，发现都是对的。
考后来自同学的正解：（其实连边就相当于整个区间都联通了）。
可以用线段树维护区间的连通性。查询直接查询最长连续的
T4
还有1h10min左右。
感觉没什么思路，先把暴力打了。
然后分析操作
能过样例，但是过不了大样例。
只剩
但感觉是可以暴力跑堆加主席树加二分答案
有
不知道怎么2log,另外一个操作也不会。
正解是用up来做。
然后就发现每次都只是查询最小值。然后就是
好像用ST表就可以加排除法就可以优化到
考后
估分：
感觉机房很多人都拿到
还能翻盘，不慌。
一些反思：感觉去肝t4的想法不太对，还是应该磕t2的。。
两天加起来
两天rk20。
去纪中rk10。
Day 3
进场。看完四题，以为t2是简单的数据结构。其他都没思路。
开题顺序：3421。
先看了一个小时的题，都没什么思路，主要在看2。
T2
看了两个小时，终于发现一个cdq+fft的做法。
后来发现假了。
打暴力放弃。
后来和oql讨论感觉是分块+fft（cdq用不用差不多）。
T3
打了个暴力。然后想找
放弃。打表都没打，我真是傻逼。
T4
sub1打了个
sub2|3|4当时我以为我会做t2，直接懒得做了。
然后random_shuffle。
T1
想了很久，发现就算求lcm都比较麻烦。
然后打
GG
估分：
T3暴力出奇迹了！