1. 基础贪心：邻项交换与证明 贪心算法的精髓在于“局部最优”导向“全局最优”。然而，其正确性并非总是显而易见的，需要严谨的数学证明。邻项交换（Exchange Argument）是证明一类排序相关贪心策略最经典、最强大的…

[CTS2024] 众生之门 小清新构造题。 观察大样例可以发现答案不大于 \(3\)，感性猜测可以在路径长度不超过 \(3\) 的情况下遍历整棵树，事实也确实如此。 进一步考虑答案一般为 \(0\) 和 \(1\)，只有 \(n\) 比较小或者图…

CF1909I Short Permutation Problem并非独立切，大量参考题解。 对于排列计数问题，考虑三个方向：容斥、连续段DP、按顺序加数。 发现容斥和连续段DP没前途，考虑按顺序加数。从 \(1\) ~ \(n\) 加数显然是不行的，因为…

pre { white-space: pre !important; word-wrap: normal !important; overflow-x: auto !important; display: block !important; font-family: "Consolas", "Monaco", "Courier New", …

考试 开考看题，秒了 T1，感觉 T2 是简单 dp，T3 有点神秘不知道，T4 一眼有一个 \(\mathcal O(n^2)\)。于是顺序开题。T1 很快写了，T2 看了一个小时还是不会有点难崩，当时是很快想到一个 dp，设 \(f_{i,j,0/1}\) 表…

今天是10月28号，上了铁道技术认知。

P8269 [USACO22OPEN] Visits S 题解题目传送门 博客传送门 首先，每头牛牛都只有一个拜访对象，所以如果考虑图论建模的话，相当于每个点出度都是 1。这相当于图是个基环树森林（注意不只有一棵基环树），而且每个基环…

联合猫国 去年模拟赛做过一道几乎一模一样的题，于是一眼秒了。 本题的一个结论：最终可合并的区间数为 \(\bm{O(n\log n)}\) 级别。 证明可以考虑构造出可合并区间数最多的序列，显然是所有数都相同时的区间数，可以取…