题意 题目链接。 给定一个序列 $y$​, 初始有一个全零序列 $x$​。每次可以选择一个长度为 $k$​ 的前缀或者一个长度为 $k$​ 的后缀将其加一，代价是 $k$​。问最少需要多少代价能使得对于所有 $i$​ 都满足 $b_i\geq a_i$​。 序列的长度范围为 $1 \le n \le 10^6$。 解答 Key 1: 考虑什么情况下…

这个笔记想写得稍微详细一点，部分内容来自我自己之前的博客: OI 里的数学内容整理（提高组）。 其中一些公式是 AI 从 PPT 上识别的，格式混乱，还请谅解。 整数分解与筛法 欧几里得算法 用于求解两个数的最大公因数。 $\gcd(a,b)=\gcd(b,a\bmod b)$。 int gcd(int a,int b){ return b==0?…

图匹配 二分图匹配 判定 静态：黑白染色。 动态：分层并查集。并查集可以维护的可以是点的连接关系，也可以是关系的连接方式。连接两个点，我们可以改为连接这两个点的逻辑关系，黑-白，白-黑。如果有一天同一个点的黑白被连在了一起，则这就不是一个二分图。 分层并查集经典例题：P2024 [NOI2001] 食物链。 最大匹配：匈牙利算法 模版：P3386 …

题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包，每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个，我们需要这个答案序列先单调非降再单调非升，即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …

题意 题目链接。 给你一棵树，你可以在树上连两条边，这两条边会分别形成两个环，要求这两个环没有任何相同的边或结点，求连边的方案数。 解析 蛮有趣的一个树形 dp。 考虑对于所有的连边方案，在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ，有多少方案是以其为 LCA 的，发现共有以下几种情况： $2-2$ 结构：在 $u$ 的两棵不…

这是第一场所有赛题都由我命制的公开比赛，也是第二场我参与命题的公开比赛。 比赛时由于内测下来大家都觉得 D 比 E 难，就更换了 DE 的顺序，本篇题解中没有发生更换，望读者注意。 比赛链接：Link. A. 伊甸之花 题目链接：Link. 若乐曲中同时存在 $1$ 和 $m$ 则无解，否则一定可以通过整体上移/下移一个音调来满足条件，时间复杂度 …

基础数据结构（前缀和/差分/树状数组/线段树） 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式，将复杂度控制在可控范围。 例如二维前缀和求法： 1. $sum_{i,j}=a_{i,j}$ 2. $sum_{i,j}+=sum_{i-1,j}$ 3. $sum_{i,j}+=sum_{i,j-1}$ 例题：NC225630 智乃酱的…

分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系，相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块，就可以给其中一块的所有点标记为 $1$，另一块所有点标记为 $0$，这样对于每个点只需要进行一些异或运算 $\Sigma …

不知道过了多久，似乎是时候开始回归之路了。 CodeForces Pinely Round 3 (Div. 1 + Div. 2) 链接：Link 时间：23.12.23 分数：4109(solved:4/10) 排名：963/10976 Rating 变化：2006->2006 简评： 我好菜。 BC 观察+猜想 D 从假设目标已有的情况反推，可…

几年前，我常常想到这个问题，晚上入睡，我失去了意识，第二天早上醒来，我却未曾怀疑早上醒来的我和昨晚睡下的我不是同一个人。这或许是一种潜意识吧，但这种潜意识又从何而来。后来我想，兴许是记忆赋予的。 早上醒来的我，和昨晚睡下的我有着及其相近的记忆，这让我从未怀疑我这个个体是否过了一宿仍是同一个个体，因为我所见所闻的一切都与我的记忆所吻合。假如记忆可以转…