HASC2024 游记 & 总结
Day -2 ~ -1
请了刚毕业的学长来扫盲，强度很高，从线性代数到离线分治，涉及知识点很广，但都是过基础，感觉还不错，作业也都写的差不多，但是整体二分老师过了两遍还是没怎么懂 qaq，想着集训再补吧。
Day 0
集训报到！当天还下了大雨，走路走到学校的，几乎是刚到学校就开始下了，天可黑，雨真就跟泼下来似的。在机房跟同学疯了好大一会。雨稍消停一点了，跟着去报告厅看开幕仪式，欣赏了 JZYZ 宣传视频，有趣。开幕仪式结束，上四楼，开机，然后发现机子怎么这么卡啊！！感觉比前几年在普及和普转提的机子还卡，一看运存只有 2G，，，输入法带不动，IDE 带不动，QQ 带不动，麻了。
晚上在新 OJ 上布置了测试作业，Hello World 和 A+B，光速敲完然后按 F11，好喔，编译时间40秒，，。
回寝室之后也是很快就和室友说上了话，很好。那么，集训，开始力！
Day 1 ~ 3
数据结构和离线分治专题啊，终于是配着代码把整体二分搞懂了，尝试码了两道板子，属于是茅厕顿开，恍然大悟，柳暗花明了。线段树合并也写了几道板子，理解还是挺深的。主席树上课也是听的很懂，只是直到现在还没码，会补的。之后磕出来一道 CDQ 分治的黑，好喔。（有一说一老师拿线性基当大家都会的前置芝士，有点）
Day 4 ~ 5
DP 专题，最痛苦的两天，有种力不从心的感觉，而郑州的比我小一届的 Nine_Suns 大佬 却场切了一堆题，麻了。想到开幕仪式结束的时候，碰到带我们普及的老师，拍了拍我肩膀说，“老了啊，哈哈”。这下真成老头了。只能下课之后一道一道磕，最后还是磕懂不少的，剩下的这几天一点一点补吧。DP 这东西，感觉写多了是有点感觉，但是又感觉一看题，状态转移写着写着就没感觉了，不好喔。
Day 6 ~ 8
图论专题。这位更是重量级。过完基础最短里就是差分约束，有一天时间都在磕[一道黑]([ARC117F] Gateau - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))。上课讲的有点抽象，题解区也没怎么解释 DP 部分，就自己对着代码挠头，在向大佬请教之后属于是又茅厕顿开了，然后没过多长时间就又堵了，就这样通通堵堵，最后一知半解地写了出来。然后感觉还是有点不是很懂，就又自己写了篇题解，加深理解。因为这个题，后边的同余最短路没有很上心听，会补的。
到了最小生成树就更抽象了，前面感觉还不错， Brovka 的部分属于是很透彻，但是没怎么码题。然后到了 Kruskal 重构树就彻底掉线了。大致了解了原理，上题就懵了。后边的最小直径生成树更是个爆冷，于是这部分就在磕前面的 Kruskal 重构树。结果到最后还是没怎么懂，这部分确实要补的多了啊。
图的连通性感觉还好。基础 Tarjan 求点双边双和强连通因为之前学的比较扎实理解比较深所以还好。但是上课没讲 Tarjan 求点双边双，讲的是树上差分求。感觉树差求点双确实好懂又方便，但是求边双感觉不是很好懂，实用性也不如 Tarjan 了 qaq。圆方树由于提前有再看所以听起来感觉也不错，好喔。后边讲欧拉路和欧拉回路的时候也在磕圆方树的题就没上心听嘿嘿，会补的。
一刻也没有为图的连通性的结束而哀悼，立刻赶到战场是——网络流！概念不难理解，EK 也不难懂，那么 Dinic，，，这是什么？老师讲的有点，太快了，，。自己对着 OI-Wiki 看了半天，对着代码仔细推敲，头发挠掉一把，才算是有点小懂。不过这个搞懂之后后边的一堆问题转化就也好懂多了，一堆和最大匹配等价的问题，虽然不知道为什么等价，但感性理解一下还是可以做题的。费用流的部分，由于前面没跟上老师讲的，这里就是自己在看 OI-Wiki，但也算是看懂了，并且看到有复杂度更优的原始对偶算法，就看上劲了，又去补了 Johnson 算法，搞懂了原始对偶，感觉比跑 Bellman-ford 的做法还要好懂（因为我没看懂 Bellman-ford 的代码是怎么消负圈的 qaq），好喔。但是因为在看原始对偶，后边的上下界网络流就没上心听，会补的。
（吐槽一下老师：讲的挺好的，只是语速有点太快了 qaq）
Day 9
模拟赛！
T1
怎么是交互，迷宫右手定则，赛时不会，由于是良心 IOI 赛制，就一通乱搞，水到了 80 分，跑路了。
T2
很水的树形 DP，光速切掉。
T3
怎么是前几天讲的题，光速切掉。赛后才知道是出题人没和前几天讲题的老师协商好，出锅力。
T4
是扫盲的时候有提到的广义串并联 qaq，当时原理是听懂了，但没码，完全不知道怎么实现，就先放弃了，去调 T1，结果 T1 调了半天还是 80，就又拱回来看 T4 了。盯着数据范围看了半天，码了一个 DFS 大暴力，期望得分 20，实际得分 40，暴力出奇迹！然后又加了一个二分图的特殊情况，50 分跑路。
赛后听老师又讲了一下广义串并联，发现这东西好智慧，还要自己推式子啊 qaq。这还是老师出的原创题，膜拜了。
T5
一眼不会，赛时没剩多长时间了，就码了暴力的 BFS，15 分跑路。
赛后听讲才知道是线段树优化建图 + 超级源点 qaq。这个转化感觉很厉害。去补了线段树优化建图，写了几道水紫，也算是补了 Day 2 和 Day 6 的坑。
Day 10 ~ 13
讲课老师是 zhiyangfan，好耶！帆帆好帅！
首先是字符串。之前学过但也忘的差不多了。在帆帆的超绝板书下也是重新过了一遍 KMP，AC自动机，Trie 等基础算法，理解感觉也是更深了。讲 manacher 时有点掉线，会补的会补的（两年集训讲这个都掉线 qaq）。上题之后感觉 字符串的智慧题也不少哇，，。
树上问题感觉有点抽象。树直径的智慧题也好多。树哈希没怎么懂。树剖嘛，写爽了，那一天基本都在写树剖，可恶，怎么能这样，数据结构可是会把人写傻的哇（但是写的确实好爽）！dsu on tree 也挺智慧的，懂是懂了，但感觉这个东西不写题不行啊。基础点分治之前学过也写过，我理解挺深的，所以听起来没什么压力。但到点分树就上强度了属于是，这东西真的好难理解 qaq。后边讲虚树的时候更掉线了，索性就回去磕点分树了，好不容易磕懂一上题发现怎么这么难码，吐了。会补的。
数论，好耶！到 CRT 之前听着都畅通无阻，BSGS 和 exBSGS 倒也能懂，阶和原根的部分就掉线了，数学渣是这样的。筛子感觉还不错，筛积性函数自己在下边有补习，所以还是挺顺的。杜教筛的原理自己手推了推，算是顺下来了，但却不知道具体到题要怎么用，听到帆帆说杜教筛很冷，悬着的心也是稍放下一点。接下来登场的是重量级——莫反。从一头雾水到爽切水蓝，莫反，爽！刚开始看着莫反的一堆式子确实有点吓人，但自己写了之后才发现全是套路，最多不过套一个整除分块，就可以狂写水题了。于是就写了三天的莫反。
组合容斥计数感觉纯智慧呀，二项式反演自己推一推能把证明顺下来。具体怎么用还是看题吧。二项式反演感觉只是解题过程中的一小步转化，重要的还是自己设状态进行 DP 的能力。卡特兰数和格路计数感觉很厉害，这个反射容斥，结合图来看能懂，但是没有上题，不知道具体应用。补充习题里学到了莫队优化多组询问数论题这一逆天 trick，感觉很牛，以后也是多留一手了。
Day 14
概率期望 DP 专题啊。依然是勉强跟上，DP 是这样的。没什么很深的印象和想说的话啊，欠的题很多，加训！
Day 15
OI 赛制模拟赛，痛苦。
T1
没什么思路呀，但看了眼数据范围，部分分给的很足，写了一个暴力状压，和 \(r-l\) 为定值的性质分，80 分跑路。
赛后发现是很水的签到，不是很难想的转化，赛时没仔细想，小亏。
T2
啊啊又不会，码了 12 分的 DFS 大暴力和起点为根的离线 DP，期望得分 35，实际得分 12，DP怎么爆了啊，和题解对了半天都没看出来哪不一样，麻完了。
赛时想到了看每个点作为 \((u,v)\) 这一对点的 LCA 的概率然后计算贡献，但发现不会推，就放弃了。正解还真是这，但还是没看懂题解推的式子，再说吧。
T3
不会已经不奇怪了。拿下暴力的 20 分直接跑路。看着 \(O(nq)\) 的 40 分感觉很可做但不想想了，去看 T4 了。
赛时看着就感觉正解是线段树+智慧合并，但关键转化没想到。还是太急了。
T4
天不负我，终于有数学题了。但不是莫反。这题看起来就让人有质因数分解的冲动，但对着 \(n\) 质因数分解怎么分都分不出头绪。然后考虑到这是智慧找规律构造题，直接打表。
对于每个数的所有合法解做质因数分解， 不难发现一定有一组解可以被拆分为两个质数相乘，并且这两个质数的和等于 \(n+1\)。那么我们假定有这样一对 \(x,y\in\mathbb{P},x+y=n+1\)。往证：\(xy-\varphi(xy)=n\)。
\[\begin{align} xy-\varphi(xy)&=n\\ \iff xy-(x-1)(y-1)&=n\\ \iff xy-xy+x+y-1&=n\\ \iff x+y-1&=n \end{align} \]显然成立。
那么我们考虑枚举 \(1\sim n\) 的所有质数 \(x\)，判断 \(n+1-x\) 是否是质数，若是则直接输出。虽然 \(n\) 的范围是 \(10^9\)，但我赌满足条件的 \(x\) 会很小。赌对了。
但是实际得分 90，被 \(n=1\) 卡掉了，，。
不过还好是保住了 rank4，和上一次模拟赛一模一样啊，都被 D 班大佬薄纱，都比 Nine_Suns 大佬低 20 分。多练吧。
写在最后
暑期集训啊，感觉很美好呢。每天肆意地泡在机房，将 whk 抛之脑后，享受由学习这山一般的知识而生发的纯粹的快乐，有与同学的说笑，也有偶尔的竞争，总之就是非常美好。
回家之后，依然是被压力，被逼着用本就被压榨的三天暑假补 whk，还振振有词地说着什么将来。我不想听。
虽然这一届压力确实很大，刚在集训见识了郑州两位初三大佬的实力，还有初二的 Nine_Suns 也不可忽视。更何况还有一位今年已经进 D 队并且拿银的。
只好不断地逃避，寄身于方寸屏幕间，他人所创造的虚拟世界的一隅，去寻求片刻安宁。
再说吧。
