日志

发表于 2024-10-30 更新于 2024-10-31 阅读次数：本文字数： 20k 阅读时长 ≈ 37 分钟

2024/05/30

完成题目

P3868 [TJOI2009] 猜数字

就是很板的 CRT，复习了一遍 CRT…

P2480 [SDOI2010] 古代猪文

融合了欧拉定理，Lucas 定理，CRT，真的是大杂烩，调了好一会儿

P4774 [NOI2018] 屠龙勇士

是带系数的 exCRT，需要把系数带进去重新推一遍式子，推完就和普通 exCRT 差不多了（还要加上 upper_bound），但是构式题目调了我好久啊啊啊啊啊啊啊啊啊

其他

完成了白板今日专题的更新，花了大半个上午的时间，也算是复习与巩固了。

2024/05/31

完成题目

P2197 【模板】Nim 游戏

学习了博弈论，再来做这道模板题，确实很好理解了

P1288 取数游戏 II

稍微枚举一下情况便可以找到规律

P1290 欧几里德的游戏

暴搜（不是）还是得找规律，暴搜会 TLE 的

P1247 取火柴游戏

很板的 Nim，但是要问第一步怎么取，这真是个好问题… 很容易发现需要让取完以后异或和为 0，那就没什么问题了

P2252 [SHOI2002] 取石子游戏 |【模板】威佐夫博弈

虽然是模板题，但是还是先尝试自己分析，分析出了递推规律，但是明显会 TLE，最后还是看了题解…

其他

完成了白板今日专题的更新，花了大半个上午的时间，是博弈论专题，我感觉自己写一遍印象会更深。

2024/06/02

参加比赛

【LGR-188-Div.3】洛谷基础赛 #12 & Daily OI Round 4

前两道题不是很快地过了，（其实 T2 我盲猜了一个结论，然后就过了？）然后我开始看 T3，发现我是真的不会判重啊… 那不会判重就什么都无法进行下去了… 加上上午有事，我就没做了。最终排名 200+。

2024 百度之星初赛第一场

下午想睡觉… 第一次打百度之星，没什么经验，先环顾了所有题才开始做 T1，开始没认真看数据范围，还以为是背包，写完才发现其实是贪心（可恶），然后干 T2，我感觉是一道结论题，写着写着发现似乎是数学题，但 $n \le 10^7$
，虽然我找到了 $O(n)$ 的算法，但是又乘又除又取模又加的，最后乘法逆元救我狗命（没救成功），反正乱搞一通还是败给了取模…

2024/06/03

完成题目

P5104 红包发红包

这是概率论的题，怎么说呢… 很基础的期望问题，只要了解了基本概念就能做。不过我今天主要不是做的概率论的问题。

P3807 【模板】卢卡斯定理 / Lucas 定理

复习了

P5520 [yLOI2019] 青原樱

排列组合的插板法（真・小学知识）

P3197 [HNOI2008] 越狱

找结论的题，发现共 $m^n$ 种情况，其中不满足条件的 $m \times (m-1)^{(n-1)}$ 种。

P2290 [HNOI2004] 树的计数

Prufer 结论题，对于给定度数为 $d_{1 \sim n}$ 的一棵无根树共有 $\prod _{i=1}^n C_{d_i-1}^{sum}$ 种情况，其中 $sum$ 为剩余的位置数。还有特判。

P4981 父子

Prufer 结论题，对于给定 $n$ 个结点的完全图共有 $n^{n-2}$ 个生成树（无根树），还要转为有根树，对于每个点都可以作为树根故答案为 $n^{n-1}$ 。

2024/06/04

完成题目

P1160 队列安排

做了点小清新的链表，还是手写的

P1449 后缀表达式

使用栈进行解决

P1739 表达式括号匹配

使用栈进行解决

P1981 表达式求值

还是使用栈解决

其它

学习了计算理论基础，并更新了白板专题；初步了解了群论

2024/06/05

完成题目

P3390 【模板】矩阵快速幂

矩阵 + 快速幂，但是没有用重载运算符，感觉用了还挺不错的。

P1939 【模板】矩阵加速（数列）

使用矩阵快速幂进行矩阵加速

P4924 [1007] 魔法少女小 Scarlet

模拟

其它

学习了矩阵，搞了很久，还更新了白板

2024/06/06

参加比赛

模拟赛，OI，但是没有大样例，就很抽象。

T1

板子，what can I say?

T2

思路基本正确，但是没有大样例，what can I say?

T3

最抽象的一集，我使用了一种很奇妙的办法解决 —— 钦定一个点，使用两个指针以不同的速度遍历图，如果两指针在某个时间节点相遇，说明有环。该时间节点一定与环的大小有关，但是有什么关系… 我就不知道了，猜了一下结论，然后发现对了（真的对了吗？），但是还是没有大样例，调不了啊。后来才发现计算得到的环的大小不一定最小，但如果找到最小的环大小，那是正确的，但是跑完 $n$ 个点又会 $TLE$ ，那么… 我就只钦定 $n$ 个点的话，很有可能跑出正确答案而不超时，于是… 就 $AC$ 了？

T4

暴力可拿 $35$ 分

其它

下午补题 + 有同学回来了。

2024/07/12

完成题目

P3370 【模板】字符串哈希、P3375 【模板】KMP 字符串匹配、P3371 【模板】单源最短路径（弱化版）、P4779 【模板】单源最短路径（标准版）

主要复习了一些模板，本来打算复习字符串的，但奈何对它提不起兴趣，于是只复习了俩模板；图论又重新复习了，先复习了单源最短路，用了 Dijkstra，还复习了 Floyd，但是并没有复习已故的 SPFA，虽然应该复习的。

其它

做了一下初赛的题，发现状态不太好。

2024/07/13

完成题目

None.

文化课

今天开家长会，考试成绩不理想，做了反思，下午将考试题目进行分析，做了作业。明天就要上补习班了。。。

2024/07/17

完成题目

P3811 【模板】模意义下的乘法逆元、P5431 【模板】模意义下的乘法逆元 2、P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪、P4777 【模板】扩展中国剩余定理（EXCRT）、P3807 【模板】卢卡斯定理 / Lucas 定理、P3846 [TJOI2007] 可爱的质数 /【模板】BSGS

今日讲了初等数论，好巧我复习过，于是又重新听时更能听懂了，把模板复习了，老师布置的应用题有很多典中典都做过了。

文化课

晚上抽时间把数学和物理复习了一些，做了练习。

2024/07/18

完成题目

P3372 【模板】线段树 1

模板题

P3373 【模板】线段树 2

模板题，但是居然没做（，知道先乘后加就行了

P4513 小白逛公园

求区间最大子段和，维护的东西略多，但也没有什么问题，而且是单点修改不用 Lazy Tag

P4145 上帝造题的七分钟 2 / 花神游历各国

见识到了暴力线段树，由于开根号几次后就成了 1，就不用管了，于是把区间开根号暴改为单点开根号，并剪枝

CF438D The Child and Sequence

类似的剪枝

尝试了：P2572 [SCOI2010] 序列操作

感觉类似求区间最大子段和，但是维护的更多的多，没有两个以上操作同时做的话还好，已经调对了，但两个 Lazy Tag 怎么搞还是没搞清楚。。。

课程

感觉还好，今天开始讲的很详细基础，都能听懂，后面有些就。。。但是下午做题时又仔细思考，好多也是搞懂了，理解更深刻了。码量略大，略感不适。

听说明天要上强度了。。。

文化课

由于一直在尝试 P2572，没有抽出时间。

2024/07/19

完成题目

P3379 【模板】最近公共祖先（LCA）

模板题

P7482 不条理狂诗曲

分治，上课听老师讲了，即求 $max(fl+gr,gl+fr)$ ，维护前缀和

P2391 白雪皑皑

搞不懂，于是用线段树剪枝嗯过了

课程

感觉一般，今天果然上强度了，其实都不是很能听懂，但是又不是完全听不懂，倍增还行，分治开始也好理解，但是做题还是有些迷茫，因为不仅有普通分治，还有 cdq 分治，各种分治。而到三维偏序时虽然也是分治，就完全不明白了。分块的概念也很好理解，~~于是做题就老想用线段树，关键是有些就不能用线段树。~~

文化课

做了数学作业，还差几题。

2024/07/20

完成题目

B3609 [图论与代数结构 701] 强连通分量

模板题，但是用了一种很棒的日本某算法，复杂度 $O(n+m)$ ，但是常数更差一些，但是代码更简洁。

P3366 【模板】最小生成树

还是使用了 Tarjan，我宣布 Tarjan 是最好用的、最难用的算法（

P3387 【模板】缩点

即找强连通分量，再 dfs

P8436 【模板】边双连通分量

找桥，再 dfs；桥：如果 $x$ 到 $y$ 的无向边是桥，当且仅当（充要条件） $dfn_x <low_y$

课程

今天强度还行。

主要讲了图论：最小生成树、强连通分量和边双连通分量问题。但是今天讲的是一个日本算法，代码更加简洁，只需要正反两次 dfs。

下午和晚上主要在写题，把上午讲的模板过掉了，今天有黄绿题，当然也有很多蓝紫（没做。

文化课

交了作业

2024/07/21

完成题目

SP3267 DQUERY - D-query、AT_abc174_f [ABC174F] Range Set Query

普通莫队模板题，学习了莫队，是一种优雅的暴力，利用分块的思想，离线处理数据。

P1903 [国家集训队] 数颜色 / 维护队列

带修莫队模板，加一个 $t$ 轴

P2801 教主的魔法

khz 找的朴素分块题，做了，也是巩固了对分块的理解

P5906 【模板】回滚莫队 & 不删除莫队

尽量不删的莫队，把同一块的 $l$ 放在放一起， $r$ 单调递增，可以只加；然后把 $l$ 再滚回去。

课程

今天强度上升。

又回到了数据结构：莫队以及各种升级莫队。还有树上分治等内容。感觉从回滚莫队的时候有些难懂了，下午晚上就把板子做了。

文化课

今天对于回滚莫队一直不理解，便一直在做，没有做文化课内容。

2024/07/22

完成题目

P3384 【模板】重链剖分 / 树链剖分

模板，但是调了很久，最后发现是线段树写了个 $l-r+1$ 。。。剖重链倒是没什么，就是用 2 次 DFS 罢了，但是之后还要结合别的东西解决问题。

P3258 [JLOI2014] 松鼠的新家

比板子更简单的裸题。

P2146 [NOI2015] 软件包管理器

巧用板子进行修改的题目，但是调了我好久

课程

讲了树链剖分，包括重链剖分与长链剖分，没有讲 LCT

文化课

做了数学

2024/07/23

参加比赛

24 暑假 C 班 day1 暨睿问宗内门弟子半步准提高初期宗门大比

总体：T1 暴力 30 分 T2 部分分加乱搞 30 分 T3 思路假了 25 分 T4 暴力写挂了 0 分共 85 分好成绩

8:00~8:30

开 T1，当然是纯暴力辣自然是一时间没有想出正解 + 错误地评估了 ZR 机子的速度，便只打了暴力，还以为能拿 $50 \sim 70$ 分。

8:30~11:00

看 T2 开始没有看懂题意（，于是看 T3，发现很有思路，至少也能拿 $75 pts$ （蜜汁自信，于是开启了漫漫的死磕之路。。。后来发现做法假了，但是不甘心啊，于是经过漫长的手模，找出来了一些问题，然后打上补丁，然后再打补丁。。。最后还是没有过样例，于是心态崩了

11:00~12:00

决定放弃 T3 转而打部分分，T2 打了一个特殊性质 + 乱搞就交了；T4 发现可以推式子能拿更多分，于是断然放弃 $10$ 分的部分分，但是最后没能推出来式子便挂掉了。。。

$30+30+25+0=85=50th$ 刚刚好排正中间

还是缺少经验，不应该死磕 T3 的（赛后发现 T3 是最难的。。。

对于知识的掌握还不够。

文化课

做了物理、化学

2024/07/24

完成题目

P4767 [IOI2000] 邮局加强版

四边形不等式优化 DP，感觉不如邮局加强版加强版

P4563 [JXOI2018] 守卫

简单区间 DP，通过斜率判断是否看到，找到 $r$ 的能看到的最左点；以此为界，分出其左与右分别 DP

P3478 [POI2008] STA-Station

简单换根 DP，考虑换根时原来的根的子树少了被换的一部分；被换的则多了原来的根的子树作为子树。然后 DFS。

CF794E Choosing Carrot

暴力出奇迹，打表拿省一（考虑 $O(n^2)$ 的朴素 DP，然后就是打表找规律。。。这可是我没看题解自己找到的规律（，这规律简直是又臭又长，不过好歹居然还是 $O(n)$ 的优秀时间复杂度

课程
DP 感觉就是小清新，只需要推式子就行了（或许不是，所以今天感觉格外不错。当然，一切结束在讲到邮局加强版加强版时，wqs 二分太有实力了，于是我听得很迷糊。不过回到寝室后和室友一起重新看了这道题，我就简单口胡了一下，没想到把他给讲懂了，可是我自己还迷糊啊？但是这个代码实现起来有点不太会，于是便只停留在口胡阶段（

另：目前今天的题单排在第四名，不错

文化课

做了化学

2024/07/25

完成题目

P3107 [USACO14OPEN] Odometer S

数位 DP，很麻烦，具体就是考虑求众数的出现次数。细节很多，如考虑前导 0、各占一半等情况

CF573E Bear and Bowling

朴素的 DP 为 $O(n^2)$ ，分块优化可过。

课程

感觉上强度了，讲了状压与数位 DP，而且开始 2 道例题老师把自己都讲晕了。。。后来听数位 DP 到还能听懂了。

其它

收到了百度之星的决赛晋级通知（虽然是递补，这下去北京喽。

文化课

做了物理、化学

2024/07/26

参加比赛

Codeforces Round 962 (Div. 3)

A

入门题

B

入门题，但是 CF 的人机验证卡了我 10min。。。

C

赛时想到了一个天才的想法，那就是用莫队（为什么要用莫队啊可恶！调了我好久才知道 string 最好别用 cin>>a [i] 一类的

D

天才般的题目，直接暴力

完成题目

P3195 [HNOI2008] 玩具装箱

斜率优化 DP，推式子后发现形式上是裸的斜率优化。

P2365 任务安排

仍然是斜率优化，这里保证了 $a_i$ 单调，可用单调队列维护。

P5785 [SDOI2012] 任务安排

上一题的加强版，不保证 $a_i$ 单调，只能用二分查找。

课程

讲了斜率优化、凸优化、李超线段树。只听懂了斜率优化，就只做了斜率优化相关的题目

文化课

做了数学

2024/07/27

完成题目

P4767 [IOI2000] 邮局加强版

再放送！因为今天讲的是四边形不等式

P1707 刷题比赛

矩阵加速优化 DP，只能用恶心来形容，但只要解决了初始矩阵、转移矩阵的问题，问题就迎刃而解了

P3702 [SDOI2017] 序列计数

也是矩阵加速优化 DP，比上一个好一点

课程

讲了四边形不等式、矩阵加速优化、动态 DP。听懂了四边形不等式和矩阵加速优化，并完成了相关的题目

文化课

交了作业

2024/07/28

参加比赛

24 暑假 C 班 day2 之黄泉花火知更鸟椒丘一刀 999

8:00~8:15

感觉 T1 很简单，直接暴力就像是能过，于是写了。虽然感觉是有问题的，但也说不上来。

8:15~9:40

看 T2 对正解没什么思路，于是看上了丰厚的部分分。手模出了一个奇怪的规律，于是就先写了一个换根 DP， $O(n^2)$ （基本跑不满）拿下 30+30 分，然后对 “只有至多一个 c” 特判拿下剩下的 20 分。

9:40~10:40

T4 感觉是线段树一类的，但是赛时却只敢写乱搞做法，拿下奇怪的 20+25+5 的部分分

然后重新看 T1，发现可以被卡到 $O(n^2)$ ，于是赶紧找补，但是发现的奇怪规律离正解还差一点点，最后还是遗憾拿下 70 分。

10:40~11:00

T3 还想写暴力的，但时间不够了，于是就拿了 5 分特殊性质跑路了。

结果

$70+80+5+50=205=35th$ 有所进步吧，这次的题变简单了，分数也高了。但排名是在往前走的。

2024/07/29

完成题目

P3369 【模板】普通平衡树

今天讲了平衡树，使用了 FHQ-Treap 完成，但是对板子很不熟，就像线段树板子一样，还要多打。而且也没有理解 Splay。

P1486 [NOI2004] 郁闷的出纳员

用平衡树的板子改一改，主要就是对整体的工资变化打一个 tag。

课程

讲了平衡树，从二叉查找树引入，讲了替罪羊树（易理解，常数小，但不能翻转，所以很少采用）、FHQ-Treap（也算易理解，常数大，能翻转）、Splay（LCT 有用，可以将复杂度降为单 log），我目前只理解了前两种。后面又讲了 LCT，要用 Splay 就也没懂。

文化课

做了物理、数学

2024/07/30

完成题目

UVA11526 H(n)

讲了整除分块，是一种针对 $\sum_{i=1}^nf(i)g(\lfloor \frac ni \rfloor)$ 的优化，可以将时间复杂度降为 $O(n)$ 。

P10532 [XJTUPC2024] 筛法

其实用不到任何筛法，打表发现答案为 $n^2$ 。

P6810 「MCOI-02」Convex Hull 凸包

推式子题目。

P2522 [HAOI2011] Problem b、P3455 [POI2007] ZAP-Queries、P3455 [POI2007] ZAP-Queries

用到了莫比乌斯函数的性质，再推式子就还好啦。但是其实推式子并不是还好辣。。。

课程

讲了简单的筛法，感觉很好。然后突然就快速过掉了迪利克雷卷积，我就一脸懵了，后来了解了定义和性质后才勉强理解。然后讲了积性函数和完全积性函数，幸亏这个之前了解过。然后就讲了莫比乌斯函数、莫比乌斯反演，只勉强了解了莫比乌斯函数的性质。然后讲了杜教筛，没听懂。。。

文化课

做了化学

2024/07/31

完成题目

在他写的时候，纸质题面终于发下来了，于是赶紧拆开看。我发现了 F 题就是个简单贪心，却因为没开 long long 吃了罚时，后面因为没删调试代码又吃了一发。。。好歹是过掉了。

然后 khz 把我赶下机位去打表验证 D 题，并过掉了。

我就在一旁看题，发现 C 题又是一个简单贪心，但是要卡 $O(n^2)$ 于是便用前缀和 + 二分优化，因为 khz 过了 D 还在机位上，我索性就把思路告诉他然后继续看题了。结果 khz 非要用 lower_bound 实现二分，但实际应该用 upper_bound，于是再喜提两发罚时。

在他写 C 的时候，我又在看题，发现 G 有思路。但后面我上机位过后很快发现是假的（因为把题读错了），于是便暂时弃了。

这时 glhw 告诉我们 L 他会做，于是他便过了 L。

一个小时内，我们拿到了我们这场比赛总分的 $\frac{2}{3}$ ，排名来到 Rank8，是巅峰了。

9:30~11:30

khz 开始想 J 题，并且似乎很有思路；我和 glhw 则瞄准榜上剩下的题目里通过数量最多的 H 下手。H 是个构造题，条件乍一听没什么难的，真正构造起来才知道痛苦。也许是我的问题，这次我花了大约 1 坤时才终于找到了合法的构造方法。然后就过了 H。

khz 说他的 J 似乎很正确，但是据他说复杂度是 $O(n^2)$ 的，过不了。

11:30~13:30

开 G 吧，但是真的感觉没啥思路，最开始想的是贪心去合成更多的上级数字，但是大家都觉得不太对，于是 glhw 拼了命的想出来了一个高级做法，着手去实现，但是最后没有调出来，于是 Rank25 遗憾离场。

后记

我的 H 在错误的方法中兜兜转转，最后实在气不下去了，用了最暴力的方法构造，居然是合法的？？？

khz 的 J 与正解思路是一样的，但是他说想要更低的复杂度要用线段树维护很多值，他懒得写了，实际上并不需要线段树。

事实上 G 的贪心就是最优的，只需要模拟即可。结果赛后大家都认为 G 很难，也许是都想复杂了呢。

文化课

做了数学、化学。

2024/08/05

完成题目

P3375 【模板】KMP

经典重现之我又忘了它。这次听了讲解，感觉对原理更了解了，虽然应该还是会忘。。。

P1368 【模板】最小表示法

用于找出字符串 S 的的循环同构串中字典序最小的一个。使用双指针 $i,j$ 进行匹配，遇到不匹配的情况跳指针即可。

P3805 【模板】manacher

用于找到最长回文，先小技巧两两之间放一个隔板就不用分类讨论了，然后由于对称性，对于 $i<maxright$ 的情况是可以快速得到答案的，否则就暴力枚举。

P10468 兔子与兔子

简单的前缀 hash。

P3919 【模板】可持久化线段树 1（可持久化数组）

存一下历史版本，注意到每次更改只会影响一条链上的节点，就可以大大节省空间了，而且需要动态开点。

P3834 【模板】可持久化线段树 2

经典应用。

课程

讲各种字符串问题，还没有上强度，首先讲了 hash 、 KMP 还有字典树，这些我都会（或者曾经会）。然后讲最小生成法 manacher ，学习了模板。

文化课

做了数学。

2024/08/06

完成题目

P5410 【模板】扩展 KMP/exKMP（Z 函数）

找到了一篇题解可以通过推式子找到解决方法，大致是明白了。

课程

讲了进阶的字符串问题，这下上强度了，讲了 exKMP、AC 自动机还有 PAM，但是好不容易只懂了 exKMP

参加比赛

24 暑假 C 班 - 附加赛 1

是送的比赛，下午的做题时间成了比赛时间

13:30~14:50

T1 先打了一个暴力，然后感觉有结论。首先先加后乘是肯定的。想了一个先排序然后贪心的比较是加好还是乘好的做法。然后感性证明是对的。最后还是不放心，又拍了个几万组都没啥问题。于是就交了。但是发现最后好像会丢失精度，很慌但不知道该怎么办，想了很多没啥用的解决方法，最后发现只要相对精度小于 1e-6 就行了，于是就是虚惊一场。

14:50~15:50

看 T2 除了暴力 DP 没啥想法于是看 T3 看到 20 分的暴力和 20 分的线段树模板。再仔细看看，我想是否能用线段树套平衡树写呢？但是很可惜我不会写。于是只好打了暴力 + 线段树模板。

15:50~16:50

再看 T2，先写了一个究极无敌大抽象的五维 $O(n^7)$ 的 DP，只能拿 20 分。但是由于没开 long long 导致出了问题连样例都没过。还怀疑是连暴力都打错了，最后才发现问题，也没时间优化了，没办法 20 分就 20 分吧。

16:50~17:00

检查！最后居然发现 T3 没取模，极限时间改掉。

赛后

T1 有惊无险拿到 100 分。

T2 好不容易拿到 20 分。

T3 极限丢分：暴力写挂了，只拿到 20 分

T3 本来应该想到分块的，为什么非要纠结树套树啊？而且普通线段树或平衡树改改也能过的啊。。。

总结： $100+20+20=140=40th$ 哎，还是有很多分没拿。

文化课

做了化学、物理。

2024/08/07

完成题目

P3870 [TJOI2009] 开关

分块，调了我很久，才发现是把下标搞错了。

P3396 哈希冲突

虽然我是找的分块的题目，但是居然找到了这道没什么联系的题目，但是也学习到了一些根号暴力一类的思想

课程

讲各种字符串问题，狠狠的上强度，讲的是后缀相关的问题，我就把后缀数组的概念和倍增求搞懂了，下午干脆练了分块。

文化课

做了化学。

2024/08/08

完成题目

P4588 [TJOI2018] 数学计算

线段树的运用，就是单点更改 + 维护区间积。

P2590 [ZJOI2008] 树的统计

树链剖分的模板题改改就好了。

课程

讲了趣题，但感觉不是很有趣。于是做了一些数据结构题。线段树的题调了我 4 个小时，一直以为是线段树写挂了，结果是把 == 写成了 =。。。然后做树链剖分，又调了我超级久，结果是把 qmax 和 qsum 写混了。。。

文化课

今天没有做文化课，一直在调题目。

2024/08/09

参加比赛

24 暑假 C 班 day3

8:45~11:00

T1 没有思路，便打了一个 25 分暴力。然后看其他题目，发现更没有思路，于是把 T2、T4 的暴力打了，各 10 分。然后觉得 T2 可以打表找规律，但是盯了很久，发现自己的注意力并不是很好。然后再倒回来看 T1，发现值域超级小，就开了数组存每个数出现的位置，然后钦定两个数作为交错数，交错遍历数组，求出长度。复杂度一眼看上去像是 $O(n^3)$ ，但实际上均摊了只有 $O(n^2)$ ，于是拿了 56 分的暴力分数。

11:00~12:15

我看 T4 的求和式，还以为可以改变求和顺序做到 $O(n^2)$ 的复杂度，但是推了好久，最终失败了。

T2 我继续打表，想从不同角度找规律，还是失败了。

12:15~12:45

倒回来查 T1，又加了几个小优化，主要还是害怕过不去，这下在随机数据下的效率又快了两三倍。然后再检查一下，确定自己已经没有思路了。。。

赛后

T1 预料之中拿到 56 分。

T2 得到了暴力的 10 分，说好的打表拿省一呢？

T3 看都不看的。

T4 写挂了，发现忘取模了。

总结： $56+10+0+0=66=18th$ 考得超难，这么低分也能拿到 18 名？

另：khz 明天要唱歌，请大家多多支持！！！

文化课

做了数学。

2024/08/10

完成题目

P5459 [BJOI2016] 回转寿司

可以使用动态开点线段树解决，但是 /2 和 >>1 居然有个小小的区别，导致我调了超级久。。。

P10852 【MX-X2-T1】「Cfz Round 4」Awaken

模拟一下即可。

【模板】可持久化线段树 1（可持久化数组）、【模板】可持久化线段树 2

不知道为什么又讲了，就又过了一遍。

课程

讲了动态开点线段树、可持久化线段树、线段树合并。前两个是会了，后一个听懂了但是例题有一点抽象了。

文化课

做了物理。

演唱会

好多同学和老师都上场表演了，包括 khz。豪庭！

2024/08/11

完成题目

P3403 跳楼机

同余最短路的模板题，我用了一个转两圈的方法写的，这年代谁写同余最短路还真用最短路啊？

P2371 【国家集训队】墨墨的等式

上一题的加强版。

P3379【模板】最近公共祖先 (LCA)

尝试用树剖的方式求了 LCA。

课程

今天讲了同余最短路、LCA、欧拉回路、2-SAT、环计数。前两个听懂了，欧拉回路也大致搞懂了，但后两个就没懂了.

文化课

做了数学。

2024/08/12

完成题目

P3376【模板】网络最大流

学习了网络最大流，学习了 FF 算法、EK 算法、Dinic 算法，实质上后两者是在前者的基础上优化的结果，但是 Dinic 最棒了。

参加比赛

24 暑假 C 班附加赛 day2

13:30~14:00

T1 是区间操作，看起来能用差分，于是先差分了再说，然后发现既可以 $+1$ 也可以 $−1$ ，即任取左右端点并拉近它们的差距，于是直接对正负数分别处理找到最大值即可。

14:00~15:00

看 T2，是数学期望问题，虽然我什么都不懂，但是我可以打表啊！先把 $n=3$ 的情况全部列出来，算出答案，然后反推答案是怎么被算出来的。我明确了：

任意的数对答案的贡献没有区别，这让我只需要考虑一个数；
一个环对答案的贡献为 $1$ ，那么令一个数所在环的大小为 $n$ ，它对答案的贡献就为 $frac {1}{n}；
通过打表，发现环的大小等概率地取到 $1$ 到 $n$ ，即对答案的贡献为 $frac{1}{n} \times \sum_{i=1}^n frac{1}{n}$ ；
那么所有数对答案的贡献即为 $n\times frac{1}{n} \times \sum_{i=1}^n \frac{1}{n}=\sum_{i=1}^n \frac{1}{n}$ 。

然后线性求乘法逆元即可。

以上就是我猜结论的过程，我感觉没有任何问题，便直接自信满满的写上去了。

15:00~16:40

然后去做 T3，发现并没有什么思路，于是对 $n=2$ 的情况打表，拿到 20 分，只是需要考虑 24 种情况，所以打了很久。

6:40~17:00

检查无误后就结束了。。。

赛后

T1 预料之中拿到 100 分。

T2 的结论非常正确拿下 100 分，我爱你打表！

T3 拿到 20 分，神仙结论题，不可做不可做。

总结： $100+100+20=220=2rd$ 。第一的老哥差 10 分 AK 全场，而我这档分数人也算多。为什么是 unrated？为什么是 unrated？为什么是 unrated？

课程

今天讲了网络流和图的匹配。网络流的概念超多，但也还算好理解，而图的匹配可以用到网络流里的算法解决。

文化课

做了数学。

2024/08/13

完成题目

Dining G

这道题告诉了我一个网络流小技巧：拆点以限制流量。

Asteroids G

二分图的最小点覆盖问题，直接跑一遍匈牙利算法即可

Little C Loves 3 II

非常棒的找规律题目

课程

今天讲了网络流进阶和线性规划。听得懵比，感觉不如去做昨天的题目。有同学在写猪国杀！于是我很乐意帮他解决一些题意理解的问题。

文化课

做了数学。

2024.9.8

参加比赛

【MX-X3】梦熊周赛・未来组 3（入门组 4） & RiOI Round 4（同步赛）

A.B.C.

入门～普及难度。

D.GCD 与 LCM 问题

给定一个正整数 $a\le 10^9$ ，请你构造三个正整数 $b,c,d\le 1\,634\,826\,193$ 使得 $a+b+c+d=\gcd(a,b)+\operatorname{lcm}(c,d)$ 。数据范围的限制使得一些很显见的解是不满足条件的。

$b,c,d$ 很多，于是令 $b=1$ ，原式即为 $1+a+c+d=1+\operatorname{lcm}(c,d)$ ，即为 $\frac {c\times d}{\operatorname{gcd}(c,d)}-c-d=a$ 。

发现还是有点困难，于是假使 $c,d$ 互质，则有 $c\times d-c-d=a$ ，对于该不定方程，显然有 $c=2,d=a+c,a\bmod 2\neq 0$ 满足条件，也即特殊性质里的 “ $a$ 为奇数”。

由此，我们可以继续扩展至 $a$ 为偶数的情况。此时， $gcd(c,d)\neq 1$ ，于是不妨令 $gcd(c,d)=2$ ，于是原式可以写成 $\frac {c\times d} 2-c-d=a$ ，我们是想要一个通用的规律来进行构造的，是想要一些固定的形式的，于是不难发现一组不错的解 $c=4,d=a+c,a\bmod 4\neq 0$ 满足条件。

这里 $a$ 又不能是 $4$ 的倍数了。欸？是不是找到规律了？归纳，可以发现若 $a=\prod_{i=1}^kp_i^{q_i}\times 2^r$ （ $p_i$ 为素数且 $p_i\neq2$ ），则 $b=1,c=2^{r+1},d=a+c$ 。可以计算发现不会超过数据范围限制。

总结

最后 $J: 100+100+100+100+0=400=60th,X: 100+100+0+0+0+0=200=115th$ ，还不错吧。

2024.9.9

参加比赛

24csp 7 连测 day1

A. 特工

给定 $n$ 个二元组 $x,y$ ，求出有多少对 $i,j$ 使得 $x_i+y_j=x_j+y_i$ 。移相，得 $x_i-x_j=y_i-y_j$ ，于是对每个二元组做差并开一个桶存储出现次数即可。

B. 提克塔可头

给定 $T$ 个井字棋残局，如果该局面合法，求从当前局面开始二人会赢局面的情况数。发现情况大约是 $9!$ 种，即大约是 $2\times 10^5$ ，于是预处理（爆搜）出所有的局面的答案并存储，做到 $O(1)$ 查询（unordered_map）或 $O(\log n)$ 查询（map），都应该是够用的。

C. 相似的回忆

给定数组 $s,t$ ，求 $s$ 的子串（类似字符串的定义） $subs$ 的数量，满足 $|subs|=|t|$ 且若 $subs_i=subs_j$ 有 $t_i=t_j$ 和若 $subs_i \neq subs_j$ 有 $t_i \neq t_j$ 。第一眼看上去像是某种 $KMP$ 的变形。但是我并不知道如何正确变形 $KMP$ 。于是还得做啊，就先常规离散化，然后想了一个 $O(n^2)$ 的做法，拿了 $60$ 分跑路了。

D. 波波牛一中

并没有看题。。。

总结

最后 $100+100+60=260=40th$ ，lry 也莅临了本场比赛。对于算法还应该更加熟悉才行啊，手速也有点慢了。

2024.9.10

主要就是补题，发现 C 题解的做法是一种奇怪哈希 + 线段树，其实我明明感觉 KMP 也可以的啊。。。 D 题虽然我也知道应该是 DP，但是居然还要推式子就不可能想得到了。。。

然后写了一道题的题解，没想到第一次写题解被打回来的原因竟然是 “【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格”。。。

2024.9.11

今天主要做了初赛的题目，做了 3 套，分别得了 58.5 分，62.5 分，64 分。我只能说很久没有做初赛题是这样的，加上我的补全程序每次都没有足够的时间做，这告诉我还得多加练习并且掌握好时间节奏。

还给学弟们讲了课，虽然确实很抽象。。。

2024.9.12

今天做了 2 套初赛的题目，分别得了 60.5 分，69.5 分。我的完善程序还是不太行，每次都能做到没有什么耐心。

完成了 CRT，EXCRT 的模板

2024.9.18

参加比赛

vp 了【MX-X4】梦熊 X 组・满月赛 & Jason Round 1

T1

发现 $a\times b>0$ 时有 $ans=\min({\operatorname{abs}(a), \operatorname{abs}(b), \operatorname{abs}(a - b)})$ 否则 $ans=0$ 。

T2

明显乘积在变化后是非升的，所以 $a\times b < c \times d$ 是无解的。否则可以转换为 $(1,ab)$ 至 $(cd,1)$ 或反之。然后将 $ab$ 除以二直到 $ab/cd=1$ 即可。

总结

$100+100+0+0+0+0=200=114th$ 后面的题就太蓝啦。。。

2024.9.19

今天做了 2 套初赛题目（其中一套是 23 年的）得了 66.5 分和 94 分（印象很深的 23 年题目），并且总结了一下之前做错的题目，感觉前 15 题应该没有太大问题了。请教了 lry 做题目的方法，总结了一套做题方法。

2024.9.23

完成题目

P3879 [TJOI2010] 阅读理解

对于 trie 的考察，也可以使用 map+vector 解决。

今天主要还在装软件 + 配置 VScode + 配置 WSL，并用新电脑完成了一道题目。准备了明天的 ICPC。

2024.9.24

参加比赛

ICPC 2024 网络赛第一场

开始确定的策略是 lry 先签到（M），然后等了一会儿纸质题面来了，于是分了一下题目，我开始看了 F,G，而 khz 则开了 A。

后来看了一次榜，发现除了 M 以外过了的还有 A 和 C，于是我又看起了 C。lry 签完到后，khz 说 A 就是个大模拟罢了，于是上机开始了长达 1 小时的 “搏斗”。而我看的 C 则没有那么好运，于是我把题意告诉了 lry，自己看起了 G，发现题意非常狗屎。理解了一会儿题意终于大概了解了，但是我还是没有什么思路，而 khz 在一旁说直接 $O(n^2)$ 暴力就行了，我想要是真能暴力就好了，但是暴力复杂度应该是 $O(n^4)$ 的啊（。

lry 则认为 C 不好做，于是看起了 F。正巧我之前看过 F，于是我把题意和他说了，并一起看起了 F。lry 还是太强了，F 想出了单调队列 + 线段树优化的方法，而我当时还在纠结单调队列的问题。。。于是我赶紧验证 lry 的做法，发现正确性应该没问题。

但是 khz 的 A 还在机上面，还有问题。于是 lry 就让 khz 下机并着手写起了 F，而我就开始看 C，因为 C 只要求判断奇偶，我就认为这是一个结论题，于是开始漫长的结论之路。lry 很快过了 F，于是开始看 G，但是 lry 的 G 也是很有思路（%%%），而 khz 又去调试 A 去了。

到了饭点，khz 还是没有调出 A 来，我和 lry 发现 A 很多人过，于是决定由我们俩来重构 A（反正 C 我也找不出结论）。lry 提出了很重要的一点：使用平衡三级制来记录队伍的实力，因为实力的绝对值不影响最后的结果。于是我把模拟的部分写了，而 lry 则写了搜索的部分。而在我写模拟的部分的时候 lry 则在继续思考 G，并且很有思路，于是我在中途被两次赶下了机位。于是在重构 A 的时候，lry 就把 G 过了。后来 lry 又把 A 的搜索部分写完后，我们把 A 以一种奇怪的方式缝合了起来，然后各出了一些锅，不过最后也是一遍过了。

至此 4 题已过，khz 仍然纠结了一会儿 C 和 H，并且方向都是正确的。但是我们都没有写出来了。

2024.9.25

尝试了补题，C 题问题等价于 $(li−1,ri)$ 这个图是不是棵树。虽然要使用线性代数，但是最后的结论还算好实现。H 则是网络流，重点还是在建模，建模完了以后就是纯纯的模板了。但是难点也是在建模，这点还是很折磨的，然后跑最大费用流即可。L 考虑对于每个操作，空格会怎么移动。每个查询等价于用不超过前 $k$ 轮的边， $a$ 能否到达 $b$ 。对于每条边的边权设成加入的时间，那么问题变成了需要求两个点之间的权值最大边最小的路径。可以对于每个起点，用类似 Dijkstra 的做法解决。

2024.9.26

复习了分块，找的题目都是使用线段树可以解决的，当然分块也可以。

P3870 开关

对于区间内的灯，每次可以：改变开 / 关状态；询问开着的灯的数量。还算简单的分块题目。划分块后对于区间来说，分成若干整块和 1~2 个散块进行修改或查询，维护块的 sum 即可。

P2801 教主的魔法

同样是区间修改和询问。难点在于维护东西的不同。

P1972 HH 的项链

可以使用树状数组来做。不过也可以离线下来，然后分块用莫队来做。

2024.9.29

参加比赛

CSP 模拟赛 Day4

T1 看了一下，发现是难题（至少对于我）。想了一下，感觉难度不是按升序排序的，于是开了 T2，发现是一个有规律的数学问题。但是再仔细看了数据范围后，发现并不能找规律来做，而是可以通过二分来寻找答案。然后看 T3，发现似乎是一个计数问题。可以看成一个图，然后发现 $k$ 很小，那么就可以直接爆搜，而剩下的 $n-k$ 就随便怎么连了。

补了昨天参加的梦熊周赛的部分题目，并写了一个题解。

2024.10.10

参加比赛

PCS-S D9

这场比赛 lry 其实有所提示，但是我以为他在骗我，于是我断定 T4 不是签到题（因为它的时限是唯一一个 1s 的，我记得 1s 的是最难的）。于是我看 T1 是数据结构题，T2 是一个一看就很恶心的图论，T3 是个期望，我一开始没有发现要取模，于是想要暴力模拟，并且平均求得期望值。后来发现要取模，认为是个不可做题，就放弃了。于是看 T1，我认为的签到题。最开始把题意理解错了，感觉可以用 st 表水过去，后来发现不行。于是重新思考，发现是离线询问，于是立马想到了莫队，但是实现的时候有地方有小问题，第一次测的时候大样例就有一点小错误。后来的 freopen 写错了，导致 .out 文件一直没有更新，于是其实很快就改对的代码，我却一直在调试，调试了近 $1$ 小时。直到最后我才发现这个问题，这时候离结束只有 $40+$ 分钟了。我才以为终于把到给签了。没想到签到题是题面最长的那个。于是我赶紧开 T4，但是这时候心态就有点崩了，题目读到一半，感觉可以给每种字符分配一个不同的质数，维护区间乘来实现一个另类的 hash。然后赶紧做，做到一半才发现这是一个计数题，不是什么线段树。。。

100+0+0+0=100=2th 没有做出签到题。。。

2024.10.11

今天主要是补了之前模拟赛的题目，然后花了一些时间配置了 FTP。

完成题目

P6273 [eJOI2017] 魔法

乱搞，浅浅推一下式子发现只需要枚举 $\sum_{i=l}^r [S_i=p]$ 即可。可以使用前缀和优化，然后放进桶里判断数值相同的，为一组来进行统计答案。

P7554 [COCI2020-2021#6] Index

20+35+10+0=65=78th T2 想到正解是不太可能的，但是感觉可以写一个更优的暴力多骗骗分。后面感觉都是不可做题了。

2024/05/30

完成题目

P3868 [TJOI2009] 猜数字

P2480 [SDOI2010] 古代猪文

P4774 [NOI2018] 屠龙勇士

其他

2024/05/31

完成题目

P2197 【模板】Nim 游戏

P1288 取数游戏 II

P1290 欧几里德的游戏

P1247 取火柴游戏

P2252 [SHOI2002] 取石子游戏 |【模板】威佐夫博弈

其他

2024/06/02

参加比赛

【LGR-188-Div.3】洛谷基础赛 #12 & Daily OI Round 4

2024 百度之星 初赛 第一场

2024/06/03

完成题目

P5104 红包发红包

P3807 【模板】卢卡斯定理 / Lucas 定理

P5520 [yLOI2019] 青原樱

P3197 [HNOI2008] 越狱

P2290 [HNOI2004] 树的计数

P4981 父子

2024/06/04

完成题目

P1160 队列安排

P1449 后缀表达式

P1739 表达式括号匹配

P1981 表达式求值

其它

2024/06/05

完成题目

P3390 【模板】矩阵快速幂

P1939 【模板】矩阵加速（数列）

P4924 [1007] 魔法少女小 Scarlet

其它

2024/06/06

参加比赛

T1

T2

T3

T4

其它

2024/07/12

完成题目

P3370 【模板】字符串哈希、P3375 【模板】KMP 字符串匹配、P3371 【模板】单源最短路径（弱化版）、P4779 【模板】单源最短路径（标准版）

其它

2024/07/13

完成题目

文化课

2024/07/17

完成题目

文化课

2024/07/18

完成题目

P3372 【模板】线段树 1

P3373 【模板】线段树 2

P4513 小白逛公园

P4145 上帝造题的七分钟 2 / 花神游历各国

CF438D The Child and Sequence

尝试了：P2572 [SCOI2010] 序列操作

课程

文化课

2024/07/19

完成题目

P3379 【模板】最近公共祖先（LCA）

P7482 不条理狂诗曲

P2391 白雪皑皑

课程

文化课

2024/07/20

完成题目

B3609 [图论与代数结构 701] 强连通分量

P3366 【模板】最小生成树

P3387 【模板】缩点

P8436 【模板】边双连通分量

课程

2024 百度之星初赛第一场

P4767 [IOI2000] 邮局加强版

P4767 [IOI2000] 邮局加强版