2024.10.26(Day 1) 记

Day 0

上午打 [cdqz 大团队]（？）的模板大赛，被薄纱。手速慢，还有几发没 AC。

下午写了个线段树 2 的板子，打算写 CRT 板子，发现不会 exgcd 求逆元，于是去重学 exgcd，写了一点博客。

晚上颓了一会儿，查了下 C++ 的 / 和 %，关于 C++ % 到底是怎样的还是没搞清楚，决定先不管，打 exgcd 板子，写 & 调，时间较晚，发现自己下午和晚上没干啥事，红温。好像洗了澡就发现哪错了，遂 AC。

晚上想到去年提高组 T2 的无脑分治做法。然后想起线性（如果认为 unordered_map 的复杂度是 \(O(1)\) 的话）的 Hash 做法。感觉挺有自信的。

Day 1

按计划是要打 CRT 板子、学扫描线、复习李超线段树、想往年真题。

CRT 板子是打了。

扫描线：我对它的细节不清楚，还不太会写，没打板子。

李超线段树大概复习了。

看 & 想了去年和前年 S 组的真题。前年有 [sum hash]（？），去年有字符串哈希，于是猜测今年有 xor hashing。

感觉去年的题比前年简单。但是如果遇到去年那种大模拟，可能今天我还是写不对。

看的过程中遇到两道要用贪心的题我都没想出来。

看了下用 [CLOCKS_PER_SECOND]（？） 来卡时、mt19937 和 [mt19937_64]（？） 给随机数的范围、[random_shuffle]（？）、[shuffle]（？）。

中午美美启动第五人格，看一些规则，美美睡觉。

下午带了准考证身份证 4 支笔，揣了一包葡萄干和一块应该是巧克力饼干就去考了。考场就是七高，应该是几分钟就能到。

进去看到李老师了。考室就在我们机房旁边隔了一个机房的位置，是个大教室。位置很宽敞，显示器很大，鼠标垫巨大，键盘很好用。拿到了巨大的草稿纸。值得一提的是我那个位置有两个鼠标，（应该）因为有一个是坏的。

开考看题，有点紧张导致看得很慢。吃葡萄干，吃了一些感觉不对劲，一看发现好像有点发霉了。赶快不吃了。快到一半的时候吃饼干，发现有点化了。qwq

T1 简单贪心，一小会儿就想出来了。

T2 物理+阅读理解题。草稿纸上推了下式子，分讨，发现直接二分即可。第二问是个贪心，一开始想假了，后来[写的时候]（？）发现是选点被区间覆盖的经典题，但是我记不到结论了，猜了一个按右端点排序后，区间内没点就选右端点的策略。不知道对不对，但是调了一段时间之后过了大样例。一开始大样例没过应该只是因为树状数组忘清空了；多 测 清 空！！！

T3 一眼 DP。两个想法，一个是设 \(f _ i\) 的状态，发现转移要算成段的贡献；可能因为很快有了第二种想法，我没有采用第一种想法。第二种（就是之前那道两个棋子每次移动一个的题）：两种颜色，记处理了前多少为和它们出现的最后位置，\(f _ { i, j, k }\)。显然 \(j, k\) 中一定有一个等于 \(i\)。于是把状态简化变为 \(f _ { i, j }\)。写转移，考虑怎么由 \(f _ { i, j }\) 转出去，两种，一种是移 \(i\) 上的棋子，一种是移 \(j\) 上的棋子。像是可以线段树优化，但是第二种还要跟值有关，于是对每个值记一个 \(mx _ v\)，考虑怎么维护，发现也可以直接用线段树。用了离散化，但值域很小，应该也可以不用。

T4 好麻烦的样子。只写了一个特殊性质的暴力，就是 \(c _ i\) 全是 \(2\) 的幂那个，还写挂了，大样例里对应这个特殊性质的点都没过。

总结：我对物理知识的熟悉程度还不够；（OI 上）细节处理不足，代码能力较差，[不够果断]（？）。

大家的情况来不及写了。后面有空再补。

于是回收标题：于是回家开始上物理课。

今天好像是 warma 的生日。让我们祝她生日快乐！

似乎还是万圣节，小区里的小朋友出动了。

2024.10.26