CHiCO酱のGDKOI游记
KiDDOwithTopTree
·
·
个人记录
原本还想着可以趁着这个冬令营去深圳康康的，结果……
唉，不说了不说了。
2021.1.26--PJ Day1
上午
哦豁，这都是些甚么题啊！
第一反应：
T1：大模拟。
T2：神仙东西。
T3：神仙东西。
T4：神仙东西。
我知道了！我一定来错地方了！这里是提高的考试！
T1：
害，判断东西真多。
要不是我眼睛突然好使，要不然就得栽在 T1 了…
不仅要判断 a 部分要没有错，还得判断 r 部分与 c 部分，甚至还要判断最上边那个点…
T2：
害，真变态。
看了看，瓶颈在于如何 O(1) 或 O(logn) 时间查询出来离 x 最近的高度大于 y 的地方是哪些。
可惜我不会…
跑路跑路。
T3：
还算良心…
直觉是排序+双指针，正解也是。
写了 T1 后就写 T3，所以感觉还行…
T4：
还不错。
一看题，嗯，最小生成树呢！
赶紧把树建出来！
然后…
就不会了…
好变态啊！
赶紧想办法啊！
不能在线，那就离线呗。
遍历边权，每一次到一种边权就把这种边权的边全部连上，最后查询 x 所在的集合的大小不就行啦？
哦豁？
貌似是正解哦？
嗯，我做过类似这种题的题目，是这题!
…
但是我真的只想到这个了…
于是乎…
我写了棵 \text {Link Cut Tree}…
然后还要维护最虚子树的子树大小，累得我半死…
幸好没有出锅。
返回 T2：
恩恩，既然 T4 可以离线，那么 T2 也可以试试离线啊！
离线后豁然开朗！
每次水位上升，我们可以判断每个点是否需要和左右两边连接。
不错，妙啊！
只不过出锅了…
期望得分：100+100+100+100=400（雾）
中午
打羽毛球。
回去机房发现他们在讨论题目，结果…
？？？T2 是 离线+单调队列？
啊这…
突然发现自己的 T2 出了好多锅…
- 没开 long long，见了祖宗…
- 判断合并条件是 a_x \le a_{x-1} 和 a_x \le a_{x+1}，结果我写成了 a_x < a_{x-1} 和 a_x < a_{x+1}…
- 忘记判断两个集合相同的情况了…
挺尬的…
T4 嘛…
正解是 离线+并查集…
我这才反应过来：我的 \text {Link Cut Tree} 只有 \text {Link} 没有 \text {Cut}，所以这棵 \text {Link Cut Tree} 的功能就是并查集的功能…
下午
真，全是干货，一点水(li)分(ti)都没有…
听得好累人…
并没有甚么好记的东西呢。
拖堂30分，却还要扩展中国剩余定理没讲…
晚上
出成绩了呢。
实际得分：100+0+100+100=300
我的 \text {Link Cut Tree} 没出锅，感天动地。
我的并查集一分没有，感天动地。
2021.1.27--PJ Day2
上午
今天题目比昨天难了许多呢。
至少对于我来说是的。
T1：简简单单。
快速跳题。（雾）
感觉十分简单，判断尾数即可。
T2：有点神仙。
手玩样例，玩出来了几个判断条件。
直接构造即可。
T3：神仙题目。
看到这题，第一反应就是建出主世界+下界的图，然后跑一遍最短路即可。
然后看到数据发现不对劲。
嗯嗯嗯？那么大玩我呢？
于是乎开始乱碰运气。
想着来一个 dp 试试。
我的状态转移方程设成这样：
f[v][0]=\min(f[u][0]+8 \times w[u][v],f[u][1]+w[u][v]+a[v])
f[v][1]=\min(f[u][1]+w[u][v],f[u][0]+8 \times w[u][v]+a[v])
然后样例就过了…
时复为 O(qn)。
想着是不是要来一个类似 ddp 的东西来加速一下，结果写挂了。愤愤不平地交了普通 dp。
T4：十分神仙。
只有10分钟，只好快速打了部分分，连测试都没有测试。
期望得分：100+100+30+20=250？
中午
照常打羽毛球…
我好菜啊…
T3 是LCA？
一脸懵逼…
T4 是二分图？
两脸懵逼…
你告诉我这是 PJ 算法？
下午
昨天没有水分，今天一堆水分…
例题一大堆…
按时下课，但是没有讲完呢。
放学后
分数出来了呢。
其实早就出了，只是我不知道而已。
实际得分：25+100+0+0=125。
我们仍未知道那天 T1 所出的锅是什么…
T3 竟然没有分？
我感觉 dp 没有问题呢。
晚上
开始蒙题。
有很强烈的预感，明天会出字符串的题目。
所以我打算今晚不看字符串了。
毕竟我每一次感觉某种出题的可能性很高时，就一定不会出这种题。
但我还是打了字符串的题。
2021.1.28--PJ Day3
开始前
压缩包发下来了，只是不能解压而已，但是开始可以看看里面的题目名称的。
？？？triangle 是甚么，感觉在哪里见过？
？？？sakura 又是甚么，好怪啊。
？？？number？考数论？
？？？sequence？考数列？
上午
还真没出字符串…
T1：
好吧，原来 triangle 是三角形…
不就是判断相似嘛，简简单单。
不过这定义有啥用啊…
三个角相等告诉我们是干啥呀…
反正写就对了。
我是不会告诉你们我看成了三条边相等的三角形的。
T2：
哦，sakura 是日语的樱花啊。
不错，我喜欢。
小学时有时没事干就会在家偷偷算自己最差可能考到多少名，所以充分掌握找最差排名的精髓，最好排名同理可得。
可以，题目简单。
是我打的这些题中最短的代码了。
T3：
数据范围是什么鬼东东啊…
我懂了，正解时复为 $O(logn)$！
赶紧想递推式，接着用矩阵乘法优化！
…
结果就想了2.5小时的递推式…
最后交了个 $O(n^3)$ 的暴搜。
T4：
嗯，不错。
只输入一个数字对吧。
打表干嘛，愣着啊！
于是我打了个长度为10的表就跑了。
我的爆搜时复为 $O(n^n)$…
害。
期望得分：100+100+20+30=250？
### 中午
继续打羽毛球。
我大意了啊，没有想到 T1 有精度缺失…
我大意了啊，没有想到 T3 有可能是 $O(\sqrt n)$…
大佬 zjj 为了防止精度缺失大佬高精度…
大佬 cyx 用 Python 打表，最后一题把全部表给打出来了…
大佬 ylb 发现了 T3 正解！
我好菜啊…
### 下午
讲凸包呢。
很好玩呢。
唯一一个嫌时间太长的老师…
### 放学后
成绩出来了呢。
实际得分：15+100+20+30=165。
没想到 T1 爆得那么惨…
zjj 的高精比我们高了10分…
我还是适合数据结构呢。看 Day1，两道数据结构，我都想出来了。~~就是有一题没打出来而已。~~
ddj 告诉我们，明天可以带多点作业过来，PJ 都有人体力不支（说的就是我），那么 TG 感觉不行了就去其他机房写作业就可以了…
然后和 yc 学了学羽毛球。
我好废啊，啥都不会…
### 晚上
刷红题找存在感…
嘤嘤嘤，被虐爆了…
~~本来想打凸包的，结果发现自己觉得很有可能会明天考凸包，于是便不打了。~~
明天多考考数据结构吧哭唧唧。
别再来数论恶心我啦。
## 2021.1.29--TG Day1
真来墨菲定律啊，怕啥来啥。
### 早上
第一反应：
T1：神仙题。
T2：神仙题。
T3：神仙题。
T4：神仙题。
这这这，我是来省选的吗？
T1：
？？？
甚么东西，看不懂…跳跳跳。
T2：
又是甚么东西，跳跳跳。
T3：
呦呵，好像在哪里见过这种题呢。
就是[这题](https://www.luogu.com.cn/problem/P6640)。
~~至少这次我的直觉没错。~~
不就是把**最长公共子串**换成了**最长回文子串**吗，简简单单。
~~事实证明一点也不简单。~~
既然求的是**回文子串**，那肯定就是 $\text{manacher}$ 或者 $\text {PAM}$ 啦。
这位同学，您貌似忘了什么东西…
…
我…不会啊！
淦！
字符串数据结构我就只会 AC自动机 和 后缀自动机…我哪会什么 马拉车 呀！
f**k!
好的，本来会个 $\text {Hash}$ 还能多骗几分，结果发现忘了…
一气之下连暴力都不想打，直接不写跑路。
T4：
我真是预言家呀！
一看就是浓浓的数学风味。
…
够恶心。
啥也不打，跑路！
返回 T1：
思考正解…
想贪心…
第一版：把度数定义为直接相连的边数，找出度数最大的点，把它归到一个集合中。
之前做过某道题，我就是这样想的贪心，然后挂成0分。所以我感觉这不是真贪心，但还是先去看 T2。
去到 T2：
害。
看着就像单调栈，可惜不知道怎么套。
打了暴力直接跑路。
又双叒叕回到 T1：
打开大样例，粘贴…
挂了…
为什么？
我手动模拟，算出来有 bug。
所以第二版贪心就出来了：把度数定义为直接相连的点数，找出度数最大的点，把它归到一个集合中。
很明显，又错了…
感谢大样例！
手动模拟，手造数据。
终于想出 bug 在哪里了。
感觉很不爽。
赶紧加紧造数据，找规律。
于是第三版贪心出来了：和 $\text {Kruskal}$ 差不多的思想。把边权设置为一条边重边的次数。每次优先选择重边次数最多的边，然后用种类并查集（扩展域）来维护两个集合。时复为 $O(mlogm)$。
正确性未知。~~至少我手造数据没错，大样例也没有错得那么离谱。~~
结果就是在 T1 花费了三个多小时打了个正确性未知的诡异贪心…
期望得分：100+20+0+0=120？（雾）
### 中午
发现其他大佬都打了其他题目的部分分，就我一人 T3、T4 交白卷…
yc 和我差不多。他调马拉车调了三个多小时还没有调出来…
继续打羽毛球。
惊喜地发现《工作细胞 Black》居然第三第四集不是 VIP 了。赶紧追番。
~~事实就是我回去时已经快上课了，只能回家追番。~~
T1 真是贪心，只不过不是我的那种贪心而已…
T2 真是单调栈，但是还要加上堆和二分…
T3 真就是我想的那样…
T4 …不做评价。
### 下午
拟阵听得我一脸懵逼。
yc 大佬带着耳机睡着了…
ylb 大佬直接开始写作业…
ly 大佬一边看着一边想着网络流…
后排大佬直接疯癫…
### 晚上
实际得分：60+20+0+0=80。
不错。至少没有爆0。
ddj 告诉我们，明天可以把下午的作业也带来…
PJ 总成绩出来了…我的排名和学号刚好相同…
我好菜啊！
不想写题目，只好刷水。
嘤嘤嘤，没有高级数据结构吗？
## 2021.1.30--TG Day2
…
出题人有毒吧！
昨天马拉车，今天还是马拉车…
…
### 早上
T1：
是概率期望！数论！走人。
然后我连题目都没有看清…
T2：
可做！
就怪了。
第一眼看到连边删边，就想到了 $\text {Link Cut Tree}$…
后面一想，发现 $\text {LCT}$ 貌似只能做双向边…
只好骗分了…
20分可以暴力，还有20分可以 $\text {Tarjan} + \text{Topo}$ 预处理。
打了40分后跑路。
T3：
…
又考回文串！
出题人出来挨打！
先跑再说。
T4：
看着可以拿暴力20分。
先写了 T3 再说。
T3：
写了一种诡异哈希。
毕竟我不记得 $\text {Hash}$ 怎么打了…
时间复杂度 $O(nlogn)$。
跳了三个多小时才过小样例…
然后一上大样例就挂了…
看了十分钟便不想调了…
嘤嘤嘤，昨天 yc 调了三个小时马拉车，今天我调了三个小时哈希…
结果 T4 便啥也没写…
期望得分：0+40+70+0=110。（肯定没有这个分数）
### 中午
继续打羽毛球…
T1 还要逆元…还好我没看。
T2 有亿点神奇。
T3 和我想的一样…回文树上 dp 又是什么鬼…
T4 是数据结构…没看出来就搞笑。
### 下午
老师好勤奋啊。2020年1月2日就把2021年1月30日的 PPT 给写了…
希望今天讲的是人话…
好吧，不是人话…
成绩出的好早啊。
实际得分：0+40+10+0=50。
T3 打了半天，结果爆成10…几乎全部 WA 了…
### 晚上
罔而殆的网课请假了，被迫研究 $\text {manacher}$ 和 $\text {PAM}$…
不过既然我在想这两个东西，那么明天绝对不会考。
~~考了的话 **zyz** cs！~~
我现在有亿点慌。
网络流还不会！
dp 优化还没考！
数据结构考了很多次了！
字符串也考了很多次了！
综上，我明天会砸成0分！
## 2021.1.31--TG Day3
我真是个预言带师！
### 早上
起不来啊…
题目极其变态。
T1：
不会。
T2：
20分暴力应该没有问题。
10分钟打完。
T3：
不会。
T4：
不会。
我啥也不会啊嘤嘤嘤。
于是我用了20分钟看题目，10分钟打代码，3.5小时发呆。
上午就这么过完了…
期望得分：0+20+0+0=20。
### 中午
？？？我居然又双叒叕忘记开long long了…
和 PJ Day1 梦幻联动…
体育馆没开门，只好在室外打球。
好热啊…这哪里是冬天…
打羽毛球打到 13:45 就走了。
为什么走呢？
那肯定是追番啊！
看《工作细胞 Black》。
题解几乎都没听懂…
### 下午
> 我本以为是从入门到如图，结果门都没入就直接入土了。——ylb dalao
直接放弃听讲，去看回文自动机。
实际得分：0+0+0+0=0。
嘤嘤嘤，不开 long long 见祖宗啊！
终于结束了呢！
我的得分：
300 -> 125 -> 165 -> 80 -> 50 -> 0
几乎每天都在退步…
## 总结
果然还是太菜了…
唯一一次考得好是因为数据结构多…
数论简直菜的不行。
希望能够学会数论吧。
精度一定要注意啊！！！