TYOI 游记

Day 0

行李淋了一路的雨，湿了…… 晚上打开 Day 1 的题单一看 1 蓝，其他都是紫。

Day 1

第一天是单调队列、树状数组、倍增、并查集，最后只会跟着 A 掉一些简单的。

Day 2

第二天上午是普通线段树、主席树、扫描线，然后用树状数组 A 了前 2 题。
下午是最难熬的，是传统势能线段树、吉司机线段树。个人感觉传统势能线段树还是比较简单的，就是线段树上加个剪枝，有一点考验思维，能想到怎么剪枝就过了，否则就会疯狂 TLE，以至于20分钟写了 3 道蓝题。
接着要吐槽一下这个叫吉司机线段树的东西。当时在那认真听了半天，发现码量巨大，于是边听边打，结果讲完后学长直接说了一句：“吉司机线段树一般不考，去把模板题抄一下看看思路就可以了。”？

Day 3

第三天是李超线段树+线段树合并。李超线段树简单来说就是在线段树上~~跑一次函数~~维护斜率。线段树合并就真的不会了。

Day 4

第四天是分块、莫队、整体二分、时间线段树。分块比较暴力，勉强还会。其他玩意就不太行了。

Day 5

平衡树+可持久化数据结构，调到崩溃。

Day 6-7

补题。

Day 8

早上的树上问题还是挺好做的，居然第一次在 TY 题单里看到黄题。
下午的树链剖分就不说了。

Day 9

树上启发式合并？啥玩意。

Day 10

点分治？啥玩意。

Day 11

图论？好东西。
上午讲模板，下午讲最短路。
不过最短路怎么还分那么多种？

Day 12

学了基环树。一开始看到这个高大上的名字以为很难，其实还好，就是找环。
并且直接做了一套 5 倍经验。

Day 13

测试。6 道题 4 小时。
第一题：一眼后缀表达式，直接秒。
第二题：思维题。实质就是要判断选到第 i 个数时，

1-i

是否都存在，只要判断前 i 个数的最大值等不等于 i 就 AC 了。
第三题：最有趣的一道题。我先骗出 3 个样例的答案，再通过特殊性质特判以及暴力，骗到了 40 分。
第四题：感觉正解是 dp + 单调性优化~~事实还真是~~。但是因为没有时间只能打个 dp，没优化，80分。
第五题：暴力 50 分。
总分：100 + 100 + 40 + 80 + 50 = 370
感觉有点小低，看来还得多学学提高算法，并向 zcy 大佬学学 dp(疑似是那场比赛 T3 唯一打出正解的人，其他 A 掉的都是假贪心)。

Day 14

休息。

Day 15

学的是字符串！！！~~啃老本~~疯狂 AC 的时间到了。
温习了一下 AC 自动机与 manacher，似乎又会打了。A 掉了 16 道题，就差 2 道扩展 kmp 和 2 道 manacher 和 5 道难题，

Day 16-17

dp模型，dp优化，dp杂题 —— 全是 dp。
也温习了一下一些 dp 常见模型（数位除外）。

Day 18

数论的世界——容斥原理，怎么感觉跟我 4 年级还是 5 年级认识的那个容斥原理不一样。

Day 19

早上，进入数论的同桌——博弈论的学习，首先把题单中比较简单的 4 道博弈论 A 掉了。然后再学习其他的模型。

下午，结营测试娱乐赛，13 道题 4 个小时？！
深思熟虑一番后还是打算顺序开题。

T1

打开第一道，初赛题？！看了几眼，发现：

第一段一眼 $O(n^2)$
第二段一眼下去像线性筛 $O(n \log n)$
第三段 $j \times j \le n$ ，看上去就是 $O(n \sqrt{n})$ 。
第四段一眼递归，2 分支，没记忆化，时间复杂度明显 $O(2^n)$
最后一段和第四段差不多，不过有了记忆化，忘记时间了（好像是 $O(n)$ )，反正是最快。

最终，抢了个首 A。

T2

本以为 T2 有什么规律（因为初一测试时有一道很像这个，有规律的，不能暴力），没想到这道题的算法就是模拟，暴力模拟每一次修改后的扑克牌顺序，再进行判断，刚好

(n^2 \times t)

，足以通过此题。

T3

T3 本来也是能闪切的，不过一直 TLE，检查了半个多小时，结果最后发现是最短路运行时队首没弹出，笑死。

T4

没时间了，感觉有时间能过。

T5

数学题。

T7

数学题 * 2。

T11

刚开始写了半个正解，然后一直 TLE，最后调着调着突然发现有个东西叫——二分。
然后 A 了。

T9

扎眼一看好像线段树板子，四分钟把板子切出来了，结果没过。

6 道题，不是很理想。总结：还是要多补题，虽然已经学完了提高组的知识，但是还是无法完全融会贯通，要多刷点综合题。

文章操作