Algorithms Summary

算法 trick 的记录。 系列前作:https://www.luogu.com.cn/article/yc9w22em 拆贡献!拆贡献!交换维度!交换维度!时间逆流!时间逆流!操作顺序反演!操作顺序反演!递推!递推!分离常量!分离常量!不同的项分开算! 优化一些代数式计算的复杂度时,最简单常用的技巧就是试着拆开,然后分离常量和变量,将不同类项分开处理。而当你推不出一些式子时,可以放弃推式子而使用递推。交换求和顺序/交换 DP 转移顺序/维度是破解循环依赖,找到好的计算顺序的方法,这和拆贡献是相关的:拆贡献其实就是变换了统计的第一维度。从按照整体的统计变成按照单个元素统计。 双指针就是“在不合法和不优之间的境界线上游走”,同时也是“一种扫描线”,并且是“在复杂度允许的情况下,枚举一定量信息以确定更多条件”的体现。 而“枚举一定量信息”在 DP 中也很常用。DP 的经典套路就是随便乱设状态,加入信息直到能够转移为止,然后利用种种洞察和优化去掉一部分维度,优化转移直到时空复杂度达标。 在做任何题的时候,第一步考虑性质刻画。无论是操作的性质还是维护信息的性质。性质就是限制,能够帮你找出正解。 一个好的性质刻画也很重要。一个愚蠢的性质刻画会极大地妨碍你做题。所以如果你觉得性质刻画太笨,就试着简化。 “信息学”的本质就是对于信息的处理。算法对于复杂度的优化本质上是减少不必要的对信息的处理(计算)。所以当你试图确定复杂度或者优化复杂度时,不妨思考一下“这个题,至少需要处理哪些信息?如何避免处理不必要的信息?” 信息即向量,操作即矩阵。 写了线性代数大学习,你应当能知道这点。有许多操作都是线性/仿射的,可以写成矩阵。从而拥有结合性,可以用快速幂或者线段树等方法处理。 孤链压缩权值线段树/01 trie。线性空间复杂度,从此整数可重集再也不用平衡树。 线性筛线性预处理积性数论函数。要点在于筛 n = i * p 时用到的 p 和 i 满足 p 不大于 i 的最小质因子。比埃筛更好写。 以后再也不要 naive 地 $O(n \log n)$ 算 d(i) 了。 利用单调性等等贪心性质简化问题。 有交不优 => 钦定末尾。 有时二维问题按第一维排序,而后第二维更小就一定更优所以无脑排除一些。剩下的就满足二维偏序(相当于利用贪心性质额外制造了一个维度上的单调性。这里的贪心性质是“a 被 b 包含 => b 的所有解都不劣于 a 的对应解/a 能干的所有 b 都能干”) 两种证明贪心的策略: 局部上,交换论证/调整法:调整一定能导出不劣的解。 整体上,必要性 => 充分性:我们至少需要多少操作,然后让这些操作发挥最大的效益。 增量更新并不要求旧的答案一定是新的答案。在旧答案总数很小时,可以暴力枚举它们判断它们是否是新的答案。或者,如果容易确定哪些不是新的答案,排除它们即可。 对于一些非常复杂的操作,可以考虑寻找不变量。常见的不变量常常和奇偶性或者两类元素的差有关。因为总和是容易变的,但是有时对于两类东西的作用是相同的,就可以被作差消去。 当操作是对两个相邻元素(或者类似的,一个元素附近的几个元素)时,这样的关于奇偶性或者奇偶下标的元素的差的不变量比较容易出现。 不变量和另一种思想紧密相关,即状态而非过程。在很多贪心或者博弈论的题中,常常有复杂的流程模拟,直接陷进去就做不出来了。 这时可以考虑最终状态或者解的性质,有时能够得到非常简洁优雅的结果。就像解方程一样。 ...

October 12, 2025

怎么办?

CSP-S 2026 进场之前压力巨大,非常害怕获得低下的成绩。 同一个教室里有若干位认识的同学。但偏偏坐在我右边的是一个初一小朋友,非常恼人。这家伙一直不停的试图向我搭话,全然不顾这很烦人的事实。 打开了 vmware,看上去体验不错。建立目录(反复核对准考证号),打缺省源。 搞笑的是很快要求重启电脑(验证 D:/ 的系统还原是否关闭)。于是又不得不第二次打开 vmware,重新敲缺省源。 监考老师不知为何要求在第一行注释写考场、准考证号和学校、姓名。 下发压缩包。第一次还没拿到,于是又发了一遍。看 T1,发现是唐题,20min 通过大样例。发现没有 1e18 的数据,于是检查了 long long,并手造一组样例测试无误。 T2 第一眼感觉题面非常复杂,再看一眼竟然不会。吓出冷汗。仔细想想,很快发现暴力写法。然后很快看出需要建虚点。很快发现可以跑 n 次 dijkstra 求出每个地铁到所有点的距离。发现还是过不了,很快想到跑 n 个地铁彼此间的全源最短路。很快想到对每个站厅枚举地铁线路对来求出邻接矩阵 把复杂度估计成了 $O(n^3 + m d^2 + q d^2)$。感觉有点悬,但是不管不顾就写了。反正 ultra 9 285k 很强,哪怕 3.7GHz 也一样。 (赛后发现其实是 $O(n^3 + m d + q d^2)$) 大约 15:21 过了大样例,我是码力低手 :( 回想起去年 T2 的教训,刻意观察了大样例强度。发现最后一个样例数据范围 d 很小,但倒数第二个几乎是满范围。跑了不到 400ms,显然复杂度应该能过。不过注意到大范围样例都是特殊性质,对正确性的考验不够强。 样例 3 是 n=50,m=500,没有特殊性质。应该足以检验正确性了。只是边权不需要开 long long。稍微检查一下。 同时去年 T2 告诉我们建立虚点需要让某些数组开到 m+n+eps 而不是 m+eps。进行检查。 ...

November 3, 2026

Reading Comprehension

【中考英语拔高模拟卷 · 任务型阅读第 45 题】 Read the sentence below and answer the question: “…when a player’s combo count reaches 100, they increase the Gauge of each of the other three players by 30 and reset their own combo count.” Question: What does the underlined word “their” refer to? A. The other three players B. The player who reaches 100 combo C. All four players D. The problem setter’s broken conscience

October 18, 2026

当然我在扯淡

“认为二次元的缺陷是由于缺少不肯媚俗的严肃作品,或不肯媚俗的严肃创作者引起的,这纯粹是同义反复。二次元产业除了能够迎合受众的作品以外,再也不知道有别的作品。 但是,如果有人想使这个同义反复具有更深刻的辩护论根据的假象,说什么二次元表达思想的野心太小了,只要思想的野心提高,弊端就可以消除,那么,只要指出下面这点就够了: 二次元的扑街每一次都恰好是在这样一个时期准备好的——在这个时期,文案的形而上学野心一般是在膨胀,世界观设定实际上也是空前晦涩的,而每一部自诩深刻的作品,最终也还是都毫无例外地退化为一个美少女。”

October 2, 2026

聪明与智慧

“聪明”是“硬件”,智慧是软件与算法。

July 24, 2026

艺术

关于“艺术”。那个经典的问题 艺术的本质是什么? 我现在知道了答案。 艺术的本质是美。美的传达。 美的本质是感动。 感动将“爱”缔造而出。而爱正是艺术的源头。作者对作品的爱。读者对作品的爱。读者与作者的爱。作品对世界的爱。 爱创造艺术。艺术传递美。美造就感动。感动缔造“爱”。

July 15, 2026

绝地与西斯

后现代主义教条: 真理是谎言,唯有权力。 通过权力,我获得力量。 通过力量,我获得身份。 通过身份,我获得尊严。 通过尊严,我击碎束缚。 自由将我解放。 古典主义/现代主义教条: 怀疑,然相信。 混乱,然和谐。 激情,然宁静。 愚昧,然求知。 死亡,然真理。

July 9, 2026

等待

等待吧。等待是最大的美德。 热衷于预测未来的人们,为什么不去请教现实这位最好的推演家呢?

July 6, 2026

如何研究一个问题?

有一个所谓对象-本质-关系模型:研究一个问题,先找它涉及的要素。再看要素的本质。最后发掘要素间的关系。 立论和驳论同时适用这一套。 三个步骤,每一步都可以注入独特的洞见。也都是驳论的突破口。

July 5, 2026

一个邪恶的阴谋

用户应当保留拒绝购买任何特定硬件的权利。 用户应当保留拒绝使用任何特定软件的权利。 用户应当保留随时随地登录任何设备的权利。 很可惜,除了密码,没有任何所谓“现代”的安全方案能做到以上三点。 密码学家兜兜转转五十年,发明出一堆原始人都会嘲笑的东西。 邪恶的巨头推广 passkey,推广 2FA,短信验证码,邮箱验证码,要求不能用密码登录……这是一个巨大的阴谋。

June 29, 2026