CrazyEagle
2024-11-25 21:22:43
11.25
周一，停课集训，在北师大台州附中，就是考初赛的地方。讲课的是 noip（lxl），今天其实是第二天了，看到 sgl 的游记发现其实可以很早就开坑所以来写。
昨天打了一整天线段树：早上线段树专场练习赛，下午线段树讲解，晚上补线段树题。现在看到 struct Seg 就想吐。
不过 noip 教的都是很有用的东西。难点主要在区间答案合并以及扫描线的建模。其实我到现在才真正认识了扫描线——至少我发现我之前的认识基本都是错的。
今天早上打了一场模拟赛，没有大样例，感觉是 J 到 S 的难度（分数比我 J 高，100+100+35+100）。
事实上发下数据的时候我看到每道题里都有个 sample 文件夹，显然里面装的是大样例。估计是这边的老师没看到。
11.26:
noip 讲 dp。
这里蚊子真多。而且打都打不到。
早上昏昏欲睡，但与数学课不同的是，这里我还能把内容听进去，但是数学课上想睡觉会导致我听不进一点。
下午 dp 练习赛（IOI赛制），前三道手速，第四道控我快一个小时，第五道压根没看。
晚。
刚刚 noip 当着我们的面把一道蓝改成了紫，然后又改了回来。
“这可以出到普及组，没有用到普及组以外的知识。”
↑ （CF1016F）
update:汪汪队队长1申请降色，说不定你看到这的时候它真的蓝了。
被蓝后的瞬间：
22:51：
蓝勾到手。
11.27：
早上模拟赛。T1 一眼，T2 稍微想了一会儿。
看了眼 T3 T4，（不是很果断地）在 T3 打 DLX（？），效果有但不多（比一般暴力略多），成功浪费了我许多时间。
在考场上一定要记住，如果想到什么非常规且实现复杂的做法（包括但不限于平衡树，DLX，神经网络（真想到这个的话我也喷不了了，这是真神经），网络流倒是可以考虑一下，毕竟 Dinic 码量不大，往年也有给网络流的部分），一定憋住，先去找性质或者去想其他题目。
T4 也不是很会，打了个部分分。
100+100+30+50=280，rk3
这两场明显比 noip 简单。
T3 是逆天性质。
“反正 noip 都是乱搞。”—— lxl
T4 是最长长度限制（给定常数c）的最大区间子段和。正解按长度
告诉我们是原题 P6780，std长达 300+ 行的黑，给我干哪去了？
下午讲得比较杂，图上 DP，状压，数位，倍增优化什么的。似乎本来打算讲矩阵加速，但同机房的人除了我与汪汪队队长1都说不知道？
lxl 在讲 P6218 的时候故意把“圆数”读成某二字游戏，给他自己整绷不住了。
数位 DP 入门了，孩子们。
调了一晚上P3953逛公园，现在脑子轰轰的。
11.28，图论
01最短路用双端队列实际上是极端特化的。一般化一点可以在答案值域的每个点上开一个队列。Dijkstra 是用 priority_queue 来挑选
图上常见的图灵奖问题：最大团，最大独立集，最小边覆盖，旅行商，哈密顿回，图染色。看到这些就不要硬想，去找性质。
一些图上不好搞但树上比较好搞的题可以考虑怎么扒出一棵生成树去做，并大胆猜测不用验证证明它是可行的。
中午打了一下知道原理但一直没写过的线段树优化建图。
基环树问题好像一直没写过，一定要抽空写一下。
下午图论树论练习赛。noip 终于摸清我们有多菜了，五道都相对简单。
因为 C（灾后重建，Floyd）D（车站分级，拓扑排序）都做过，先开的 CD（但首 A 一个都没抢到，悲）。
然后把 B（简单广搜）做了，去创 E。以为只是简单树上背包，WA了一发发现是基环树。由前一段可知，这是我第一次写基环树题。拿感觉硬干干过去了。
最后开 A，在遍历树的过程中维护一个指向地址的指针。然后创过去了。想到维护地址的灵感其实来源于看过但没写过的长链剖分。现在想想维护下标指针应该也行。
突然发现 T1 是 CSPS2019 的题（括号树），成功揭露我从来不做真题的罪行。
（晚）
唔，集训要结束力（本来明天还有比赛，但考虑到这离温中有点远就直接回温中了）。打算向 noip 要签名。
19:43：noip 签名到手，回头跟万宏老师的签名放在一起。
复习了一下线段树和网络流，本来想复习 Splay 但发现一点不会，寻思着应该不考，要用我也可以动态开点权值线段树（就是内存大个十几二十倍而已）。
11.29：
好紧张 qwq
打了一晚上空洞，把蜂巢补上开了三门。而我明天就要开我在OI路上的三门了。
(好不容易走到了三门底被祖师爷赶出去了qwq)
11.30
嘶……从哪开始写呢?
我在T1代码里留下了一小段话，估计有望出现在浙江迷惑行为上。
T1打的是一个贪心，样例都过。但是搓了整整一个半小时，心态已经有点崩。
T2DP，也调了好久，样例也都过，只是不知道为什么都说矩阵快速幂，我是
T3看一眼题就感到不可想，直接冲T4。线段树维护一个区间的LCA还是比较好写的，用这个拿了点暴力分，小样例也都能过。
因为是班里唯二停课的，家长倒是没什么(我在T1留的话里提到家长可能不支持，现在想老妈应该会支持我，老爸说不定)，主要是老师难办，万一没考好会被当反面例子，再加上身为班长停掉文化课去冲竞赛还拿不到好成绩，回到文化课又不如别人，压力有些大。
今年的OI之路也算告一段落了。如果从我学C++开始算或许有一年半，但从真正的信息学竞赛开始算——从我注册洛谷开始——连一年都没有(导致我到目前都还不能更正我的 Vessel 拼写，不过我打算改其它名字了)，就算这一场出了什么差错，我……呃，说不遗憾也不会吧，但我对我这一年的努力也很满足了。
upd on 12.6:
100+100+0+32，符合预期。
T3 没有 puts('1')，希望这不会影响到拿省一