2024 暑假集训
暑假集训
Day 0
这是第三次集训了，和之前相比，感觉没有那么欢乐，更多的是在考虑学习上的事情。
同时也有了文化课的负担，需要担心文化课不能落下。
Day 1
Day 1 讲了树状数组和线段树基础。都比较板子，经过学习，对这两种数据结构有了更深的了解。
这俩都比较熟了，还要多写写，记住板子，别写错了。否则调树剖调一个小时发现是线段树写错了就很难受。
Day 2
Day 2 讲了线段树扩展，主要有线段树上二分、动态开点、线段树合并、可持久化、扫描线、优化建图 / DP 等。
线段树二分简单的题比较好写，但是有的题目需要考虑的比较多，比较麻烦。
动态开点比较好理解，线段树合并没写过，要抽时间练练。
可持久化线段树练了一些板子题目，还要找一些不是太板子的题目练一下应用。
扫描线、优化建图这种思想有了一定了解，主要是在代码实现上多练习。
优化 DP 感觉比较难，主要是不会把复杂度较高的 DP 式改写成能用线段树优化的式子，还是要多找点题做做，找找感觉，增加经验。
菜就多练。
Day 3
Day 3 讲了分治算法。有线段树分治、CDQ 分治和整体二分。思想比较简单，应用比较难。
线段树分治难在要把题目的条件转化为这一算法，比较考验思维；CDQ 分治有很多细节，比如合并时的细节、合并的顺序、统计答案的方式等等，要认真考虑才行；整体二分也是难在分治时的细节上，比较难写。总之要多练。
Day 4
Day 5
动态规划老大难，从初一错到高二。
DP 可以和数据结构、二分、容斥等等算法结合，树上 DP、数位 DP 还不是太熟。
DP 还是要多刷题，找感觉，静下心来推式子。
Day 6
图论。
最短路比较好写，有一些题目难在建图；差分约束也一样，板子简单，但是转化题意建图比较难。
同余最短路基本只是了解，还要加强。
最小生成树中要选择合适的算法，尤其是用 Brovka 的思想的题目，这些题目有一些数据结构合并删除等操作，还不是太熟练。
Day 7
连通性。
并查集比较简单，但是遇到不是特别板子的题就比较难写（比如：NOIP2023 T2……），还是要熟悉这种算法的套路，提高认识。
缩点等等那些比较熟了，难在缩完点后在树 / DAG 上的 DP、圆方树这些东西。
欧拉回路也是板子简单，难在建图。
Day 8
网络流。
这玩意板子也不好写，但是功能感觉比较强大。
特别是扩展的有 / 无源汇上下界最小 / 最大费用最小流 / 最大流 / 可行流这种东西，板子还是要多练练。、
建图感觉简单一点，但是有很多细节要考虑。
Day 9
IOI 欢乐赛。
T1 是交互走迷宫，其实会正解，但是写不太对。这种不是太套路的算法还是要多想想，考虑细节。
T2 是期望换根，比较简单。但是用了很长时间才想到。\(O(n^2)\) 算法改到 \(O(n)\) 算法时没改数组大小，RE 了一发。OI 赛制要认真检查数组大小（然鹅 Day 15 的 T2 还是开的第一档数组大小写的第二档的数据，又 RE 了）。
T3 告诉我们认真听课的重要性。
T4 是大图论，正解是做不出来的。但是没想到 50 的暴力，写了个 20 的暴力，看来暴力也要加强。
T5 是建图跑最短路，只会特殊性质。还是因为建图的方案不够优秀，导致时间复杂度比较炸。
Day 10
字符串。
感觉很有收获，对 KMP、Manacher 和 AC-自动机有了更深的认识，不再只是死记板子。
一些比较难的题需要利用这些算法处理的信息计算，以及有的题要有数据结构统计答案等等。
需要多见题，多练练。考场上不能真见着字符串就搞暴力。
Day 11
树上问题。
基础的 LCA、重心的相关性质要加强；树哈希感觉和换根 DP 比较相似，难在实现；重链剖分练的相对多一点，但是要注意线段树别写错了……树上启发式合并感觉比较玄学，难点还是数据结构的合并；点分治板子就很难，但是功能强大，要找个时间多练练板子；虚树没写过，也是要练练板子、学会应用。
Day 12
数论 \(\approx\) 算命。
两个扩欧还好，CRT 也还好，BSGS、阶与原根基本比较寄。
卷积、莫反还能理解，但是式子自己推不出来，还是要多练。
筛子的话线筛还好，杜筛就有点蒙了，整除分块听懂了，但是不会写。
Day 13
广义容斥。还是推式子，不太能推……
格路计数的多重限制也不太会写……
还有一些和莫队、DP 结合的神仙题目，只能说 emm……
感觉这天的比较难，不会的比较多。
Day 14
概率期望。
主要难在算答案的式子，能理解，但是不能想到。有时候正解的式子特别简洁，但是很魔幻。
还是对概率期望的一些性质不太熟悉，难以正确推出合适的式子。
Day 15
NOIP 模拟赛。
T1 推了一下性质，发现正解，十分钟秒掉。
然后看了 T2 和 T3，不太好写，就去写 T4 的暴力分，但是不会写线筛，赛时推了推写出来了。
然后写了 T2 的纯暴力和特殊性质的 DP，35 分，然鹅挂了……
T3 写了个 \(O(nq)\) 的神秘贪心，大样例跑了半个小时小时过了，看出来是线段树但是不会 PushUp。
然后发现了 T4 \(n\) 是质数的性质，同时发现筛到 \(O(n)\) 不一定够用。
期望得分：\(100+35+40+(40\sim60) = (215\sim235)\)；
实际得分：\(100+0+40+50=190,\ \mathrm{rank}=5\)。
总结
学了一些新的知识点，也有一些算是复习。
不管是什么知识点，主要是两部分：
- 板子 有的题板子就比较难，比如网络流、2-SAT 等等，要写一写，熟悉一下。最开始学最短路 / 线段树的时候也觉得板子难，但是多练练，熟悉熟悉就写的顺手一些了。
- 转化 联赛肯定不会考板子，肯定是有转化，比如考察建图、推式子等等。这方面要多练一些题目，找找感觉，发现题目的套路，把板子套到题上。
总之：多练。