做题记录

yifu_chen · 2025-09-13 20:12:25 · 个人记录

最近一次更新：2026.5.16-9:51

贪心

• CF414D Mashmokh and Water Tanks 一开始放水的点尽量深度差距小，枚举深度最大的地方，二分最小的地方（2025-11-30）

• CF1380E Merging Towers 答案取决于相邻两个不相等的对数，维护即可（2025-12-22）

• CF1905F Field Should Not Be Empty 预处理一个位置左右两侧交换哪两个地方可以使这个位置满足条件，最终答案交换的两个数一定是这样的几对中的一个，又或者是 i 与 a_i 交换（2025-12-29）

• CF1778F Maximizing Root
  题意：给一棵树，进行不多于 k 次操作，每次操作可以把一个子树的所有数都乘上它们的一个公因数，求能使根节点的数最大是多少
  思路：答案是根节点乘上它的一个因子，枚举这个因子，验证是否能在 k 次操作中使得除了根以外的点都变成 a_r 的倍数。从上往下搜索，如果不用再操作就停止，否则先修改儿子再进行子树的操作。（2026-2-23）

• CF30D King's Problem\ 给一排 x 轴上的点，x_1,x_2\cdots x_n，再给一个坐标 (x_{n+1},y_{n+1})，求从第 k 个点开始走，遍历完所有的点所需的最短距离\ 如果从第 n+1 个点开始，则最优的是先到其中一个端点，然后再到另一端。如果不是，特判最终在 n+1 结束，其余的情况必然是先遍历完 [1,i]，然后到那个特殊的点，然后再遍历完 (i,n]（或者先遍历后者），枚举这个分界点，求最小值。（2026-3-9）

• CF1446D1 Frequency Problem\ 给一个序列，求最长的子串使得子串内出现次数最多的数字有两种及以上并列，a_i\le 100\ 子串就是删除前面几个和后面几个。显然元素出现数量只减少不增加，那么最优情况下最终子串内出现次数最多的数一定为原序列出现次数最多的数。枚举最终众数 d 与哪个数 v 的出现次数相等，把 d 出现的位置赋成 1，v 出现的位置赋成 -1，其他赋成 0，求最长的总和为 0 的区间。（2026-3-10）

• CF436E Cardboard Box\ 有 n 个事件，每个事件可以选择花 a 的时间获得 1 的积分，或者花 b 的时间获得 2 的积分，或者什么都不干。求获得 w 的积分至少要多少时间。\ 假如已经有了获得 x 积分的方案，再增加一个可以怎么选。显然不可能反悔两个及以上的积分。如果不反悔，可以将没有选的换成选一个的（a_i），或者将一个的换成两个的（b_i-a_i）；如果反悔一次，可以将选一个的去掉而增加选两个的（-a_i+b_j），或者将选两个的去掉一个而增加选两个的（-(b_i-a_i)+b_j）。需要用五个 priority queue 维护，分别是当前为 0 的最小 a_i，为 1 的最小 b_i-a_i，为 1 的最小 -a_i，为 0 的最小的 b_i，为 2 的最小 -(b_i-a_i)。\ tag: greedy with regret（2026-3-12）

• CF797F Mice and Holes\ 有 m 个洞，n 个老鼠在一个一维坐标轴上，每个洞有个容量，每个老鼠会选择一个洞躲进去，求所有老鼠走的距离和最小是多少，n\le 5000\ 老鼠前后不会互换位置。设 f_{i,j} 表示前 i 个洞放 j 个老鼠最小的路程和。对于每次从 i-1 到 i 的转移，预处理所有老鼠 j 的 |x_j-p_i| 的前缀和。转移使用单调队列优化，每次转移的老鼠编号距离不超过 c_i 即可。\ tag: greedy, dp, prefix sum, monotone queue（2026-3-13）

• CF1793E Velepin and Marketing\ 有 n 个数，q 次询问，每次询问将这 n 个数分成 k 堆之后，如果一个数不大于它所在堆的大小，则说它是合法的，求最大多合法的数数量。\ 答案具有单调性，也就是 k 越大答案越小。而最优解一定是按照元素大小排序之后连续地一段一段划分。设 f_i 为保证前 i 个元素合法时能够划分的最多的堆数。f_{i}=\max(f_{i-1},f_{i-a_i}+1)，算上后面的数则为 \begin{cases}f_i+(n-i)& i\ge a_i\\n-a_i+1&i<a_i \end{cases}，提前预处理然后求后缀最大值。\ tag: greedy, monotonicity, sorting, dp, prefix sum（2026-3-16）

• CF1503D Flip the Cards\ 给 n 张卡片，每个卡片正反面分别写一个数字，这些数字正好是 [1,2n] 内的正整数，求至少把多少张卡片翻面之后可以通过交换顺序使得所有卡片正面的数单调递增，反面的数单调递减。\

  $b_1>b_2>\cdots>b_n$\ 可见 $[1,n]$ 一定是 $a$ 的一个前缀以及 $b$ 的一个后缀，它们不可以相交。如果一张卡片正面反面都是在 $[1,n]$ 内则无解。\ 设 $f_i$ 表示 $i(i\in [1,n])$ 这个数字所在卡片另一面的的数字，问题转化为要给 $f$ 序列拆分成两个下降子序列，其中本来已经给每个数分配了一个归属，如果改变需要给答案加一。\ 如果不考虑计算答案，有一种贪心的构造方式，维护两个序列，每次加入一个数如果可以选择放到两个序列中的一个，肯定放到结尾较小的更优。\ 考虑按照值域分段，也就是如果 $[1,i]$ 与 $(i,n]$ 的值域没有交集就把它们划分开。也可以翻译成 $\min_{j\le i}f_j>\max_{j>i}f_j$。这样可以保证不同的段之间互不影响，并且一个段内方案唯一。假设考虑到一个位置 $i$ 时，两个序列的结尾分别为 $s_1$ 和 $s_2$（$s_1<s_2$），如果 $f_i$ 只能接到 $s_2$ 的后面则方案唯一；如果都能，由于 $s_1$ 为前面数字的最小值，所以 $f_i$ 也是前面数字的最小值，所以在这个段内一定存在一个 $j$ 使得 $f_j>f_i$（一个段内的最后一个一定不是最小值，除非只有一个数。因为如果那样一定可以在最后一个数前面划分一次），这样的话就使得 $j$ 无法分到任意一个序列中了，所以 $f_i$ 只能接到 $s_1$ 后面。\ 每个段内的分法是唯一的，只能决定两个序列代表的正反是怎样的，把不同段的最小值加起来就是整体的最小值。\ tag：贪心，划分（2026-3-16）

• CF1469F Power Sockets\ 题意：初始有一个白点，若干个白色的链。选择其中的一些链，每次把链与初始的树连起来。连接时选择树上剩余的白点并选择链上的一个点连一条边，然后把这两个点都染成黑色，求最终第 k 深的白点深度最小是多少。\ 思路：连接一条链的中点与树上最浅的点最优。树的形态并不重要，只需要记一个数组表示对应深度的白点个数。选链的时候优先选择更长的。于是那线段树维护区间加以及线段树上二分。\ 标签：贪心、线段树上二分（2026-3-19）

• CF1893D Colorful Constructive\ 题意：给 n 个数，恰好分成 m 堆，每堆限定个数恰好为 s_i，要求任意一堆都满足这一堆里距离最近的两个相等的数的距离大于等于 d_i。\ 思路：贪心地放，每次优先选剩余个数多的数放。\ 标签：贪心（2026-3-20）

• CF1572C Paint\ 题意：给一个序列，一次操作可以把一个颜色段改变成另一个颜色，求至少多少次操作可以把整个序列改为一种颜色。n\le 3000，且每种颜色的出现次数不超过 20。\ 思路：结论为一个区间一定有一种最优染色方案把整个区间都改为右端点的颜色。设 f_{i,j} 表示 [i,j] 的最少操作次数，f_{i,k}+f_{k+1,j}\rightarrow f_{i,j}(a_k=a_j)，可以理解为与右端点同色的位置将整个区间分为了若干段，每段分别处理然后合并肯定更优。\ 标签：贪心，区间 dp（2026-3-26）

• CF2201D Binary Not Search and Queries\ 题意：给一个序列，进行 q 次修改，每次修改后求最大的 l，使得存在两个不同的长度为 l 的区间，每个颜色的出现次数是相等的，还要求方案数。\ 思路：结论是答案一定是两个区间 [l,r-1] 和 [l+1,r]，并且 a_l=a_r，因为两个不重叠的区间加上重叠部分一定可以，而两个排列中一定存在一对对应位置距离更大。所以用 set 维护长度为 x 的极长区间的左端点，方案数与左端点组成的连续区间长度有关，是 \frac{1}{2}len\times (len+1)。\ 标签：贪心、set（2026-4-9）

  排序

• CF1601D Difficult Mountain\ 题意：有 n 个物品，一个限制 d，对于一个物品，如果 s_i\ge d 则可以选这个物品并把 d 修改为 \max(d,a_i)，求最多选多少个物品。\ 思路：按照 \max(a_i,s_i) 为第一关键字，s_i 为第二关键字排序，然后能选就选。\ 标签：排序、贪心（2026-4-5）

  括号序列

• CF3D Least Cost Bracket Sequence 先都放右括号，如果成负数了就贪心的选 cost 小的替换成左括号（2025-12-26）

• Q6.1.6.1 括号修复
  题意：给一个括号序列，进行区间覆盖/翻转/反转以及查询区间需要几次操作才能变成合法括号序列
  思路：在括号序列中删除所有配对的括号后跟原来的括号等价，所以最终得到的是一个形为 ))...)((...( 的括号序列，将它修复为一个合法的序列的操作数量为 \lceil\frac{x}{2}\rceil+\lceil\frac{y}{2}\rceil，其中 x 为右括号数量（即一开始的前缀最小值的相反数），y 为左括号数量（即一开始的后缀最大值）。操作通过平衡树维护。（2026-2-2）

• CF1685C Bring Balance\ 给一个括号序列，求最少翻转多少个区间内的括号可以使整个序列是合法的。\ 答案不超过 2 ，因为可以选择前缀和最大的位置 x，把 [1,x] 与 [x+1,n] 反转。如果初始时合法，答案为 0；如果答案为 1 说明反转了一个区间 [l,r]，包含了所有原本前缀和小于 0 的位置，[l,r] 中一个位置 i 与其对应的翻转位置 j，可以得到新的前缀和 s'_i=s_{l-1}+s_r-s_{j-1}，所以找到前缀和最大的位置得到 [l,r] 进行判断；否则答案为 2。\ tag: brackets, constructive algorithm（2026-3-14）

• CF1896F Bracket Xoring\ 题意：给一个 01 串，求操作不超过 10 次的方案使整个串都变成 0。一次操作可以构造一个括号序列，使每两个配对的括号之间的位置的数字都取反。\ 思路：一种形为 (()()()...()) 的括号序列可以使左右端点取反。所以如果 01 串任意两个 1 之间都有偶数个 0，则可以一次操作实现。若能够做到让任意偶数位置都与下一个位置相等则可以满足此条件，则枚举每个偶数位置，若本来就与下一个相等则填 ()，否则填 (( 或 ))。\ 标签：括号、构造（2026-3-25）

• CF2041H Sheet Music\ 求长度为 n 且值域在 [1,k] 内本质不同的乐曲数（任意相邻两个位置之间的大小关系相同则视为本质相同）\ 不合法的情况一定存在连续的 k 个升或降，然后 dp 求解（2025-11-19）

  排列

• CF91D Grocer's Problem\ 给一个排列，一次操作可以选择不超过五个位置（不一定连续），将它们任意排列。求最少几次操作可以把排列复原。\ 可以把排列看做很多个环，如果是整的环就可以都复原，否则如果一个环的大小比五大，则最多还原四个。因此可以先把大的环都处理了，剩下一些大小为二、三、四的环。然后看着办就行。（2026-3-9）

  回文

• CF2004F Make a Palindrome\ 给一个序列，对于每个区间求至少多少次如下操作可以把原序列变成一个回文串：把一个数替换成两个和为它的正整数或者把两个数替换成它们的和，n\le 2000\ 只用考虑合并操作，因为回文串的对称性，在一侧拆分的操作可以通过合并另一侧的对应位置达到同样的效果。然后从最劣的情况优化，如果一个区间有一个前缀和一个后缀相等则可以减少一次合并操作。枚举所有的区间计算答案。\ tag: palindrome, greedy, reverse（2026-3-13）

  中位数

• CF1539F Strange Array\ 题意：对于所有的 i\in[1,n]，求任意 l\le i\le r，将此区间内的数排序后 a_i 最终的位置与区间中点（取靠后的一个）的距离最大是多少。\ 思路：将大于 a_i 的位置赋成 1，小于的赋成 -1，即求区间和绝对值的最大值是多少。\ 标签：中位数，线段树（2026-3-24）

• at_agc020_c Median Sum\ 题意：给 n 个数，求所有非空子集内数的和组成的大小为 2^{n}-1 的集合的中位数。\ 思路：具有对称性，若 a 在集合内，则 sum-a 也在，除非是 0 或 sum，所以进行可行性背包 dp，答案是 \frac{sum}{2} 之后第一个存在的数。\ 标签：中位数、对称性（2026-4-18）

  模拟

• CF1070G Monsters and Potions 有单调性，但整体是暴力。注意如果都朝一个方向走，那么第一个人必须能到集结点

• CF1949J Amanda and Amoeba\ 有一个网格图，里面有一只变形虫和一些不能走的地方，求一种方案让变形虫从起始状态走到终止状态\ 考虑找到一个中间位置，从初始状态和终止状态分别走到中间状态，然后再把两个的操作拼起来。从变形虫初始所在的坐标中选一个开始 dfs，用 dfs 序给坐标编号，这样可以保证走的时候坐标始终减小，否则会有不会绕路的情况。（2026-3-4）

  二分

• **CF24E Berland collider*** 二分答案，判断相邻两个是否相遇

• CF123C Brackets 小结论，同一条对角线上的都相等（可以观察出来）。然后按照优先级枚举每个位置，假定这一位放 (，dp 求出有多少个，然后判断是否大于等于要求的那个排名。

• CF557E Ann and Half-Palindrome 先区间 dp 求出所有备选区间，然后插入到 Trie 树上，二分找排名。

• CF2107E Ain and Apple Tree
  构造一个 n 个点的树，使得 |\sum_{u\le v} dep(lca(u,v))-k|\le 1
  链的时候答案最大，每将链的最低点向上移动 x，（不能超过原来移动的点的终点），答案会减少 \frac{x(x+1)}{2}（2026-1-24）

  位运算

• 6.2.1.3 由乃的OJ\ 有一个数的序列和一个位运算符号的序列，单点修改，求对于一个区间，询问选取一个初始值 v，求从左到右依次将 v 赋值成 v\otimes a（\otimes 三种位运算之一），得到的答案最大是多少（此题被搬到树上）。\ 对于一个区间，维护每一位为 0/1 从左到右/从右到左进行计算得到的是 0/1。但是会 TLE 或 MLE。可以把它装压到一个数，瞪出 c.s0=(((~a.s0)& b.s0)|(a.s0&b.s1))（这是从左到右且输入为零的情况），另外几种情况同理。（2026-2-3）

• CF1493E Enormous XOR\ 题意：给 l，r，求所有 (x,y)（l\le x\le y\le r）中 \mathbf{xor}_{i=x}^y i 的最大值是多少。（l,r\le 2^n，n\le 10^6）\ 思路：找到了一个规律，所有自然数的前缀 xor，按照模 4 的余数是有规律的。如果 l 和 r 最高位不同，则一定可以取形如 2^n 与 2^{n}-1 两个数得到 n+1 个 1；否则一定取奇数个，使最高位为 1，这样的话根据规律可以发现若 y 取偶数，x=y 时答案为 y，x=y-2 时，答案为 y+1，否则答案为 y。\ 标签：位运算、找规律、构造（2026-3-19）

• CF1148F Foo Fighters\ 题意：给 n 个 val 和其对应的一个二进制数 mask，求一个数 s，使得所有 i，满足 mask_i\&s 中有奇数个 1 的 val 变为 -val 之后求和与原本的 val 之和符号不同。\ 思路：按照最高位从低到高考虑，这样可以保证修改了 s 的高位不会对位数较低的数的 val 产生影响。对于最高位为 k 的数，判断它们的 val 之和是否与原本相同，如果是则把 s 这位变为 1 并把对应的 val 都取相反数。\ 标签：贪心、归纳、位运算（2026-4-5）

• CF327E Axis Walking 装压 dp 可以使用 lowbit，每次取出一位来优化转移，卡常（2025-11-18）

• CF662A Gambing Nim\ 给序列 a 和 b，有相等概率选择 a_i 或者 b_i 到这一位，求选择后进行尼姆游戏先手赢的概率。\ 即异或和不为零，构造 c_i=a_i\oplus b_i，则在 a 的基础上可以选择是否选择异或上 c，用线性基求。（2026-5-5）

  01 串

• CF1700F Puzzle\ 题意：给一个 2\times n 的格子，一些是黑的，一些是白的，一次操作可以交换相邻两个格子的颜色，求至少多少次操作可以从初始状态变成想要的状态。\ 思路：考虑一个 1\times n 的格子怎么求。先给初始状态和结束状态都求前缀和 s，答案就是 \sum_{i=1}^n |sa_{i}-sb_i|，利用了把代价拆分的思想。（设 d_{i,j}=sa_{i,j}-sb_{i,j}）如果是两行需要考虑上下交换的情况，若把第 i 列上面的 1 换到下面，则对于所有的 j\ge i，d_{0,j} 会减少 1，d_{1,j} 会增加 1。因为最终是取绝对，所以如果上下的 d 异号就将其中一个的分到另一个使最终一个变为 0，可以在序列上从左到右贪心地修改（虽然说前缀和会改变）\ 标签：前缀和，贪心（2026-3-21）

• at_arc216_a Reversi 3\ 题意：给两个 01 串，一次操作可以把两个相等且距离为 2 的元素之间所夹的那个元素反转，求至少多少次操作可以把一个序列变为另一个序列。\ 思路：把相邻两项作异或，在第一项相等的前提下等价于选择相邻两个相同元素并将它们都反转的。再将这个序列反转所有偶数项，现在等价于选择相邻两项不同的位置反转，转化为 01 串上移动的问题。\ 标签：位运算，构造（2026-3-23）

• CF201E Thoroughly Bureaucratic Organization\ 题意：有 n 个编号不同的人，每次可以去询问最多 m 个不同的人，他们的编号是哪些，求最少申请多少次可以清楚知道这 n 个人每个人的编号。\ 思路：等价于有 n 个长度为 q 的 01 串，满足这 n 个串互不相同（可以区分他们的编号），且每一列都不超过 m 个 1，求 q 最小是多少。可以二分 q。而第二个条件等价于一个更宽松的条件——总的 1 的个数不超过 mq，可以通过调整的方法证明，即每次选择一列多于 m、一列少于 m 的，选择一行交换 01。\ 标签：具象化、01 串、贪心、二分（2026-4-12）

  集合

• CF1208F Bits And Pieces\ 给一个序列，求 a_i|(a_j \& a_k) (i<j<k) 的最大值\ 枚举一个 i，需要找到 j 和 k 使得那个值最大。可以从高位开始贪心地放一，现在需要判断能否凑成一个数，也就是能否找出一个 x 使得 x\sub \overline{a_i}，并且 x\sub a_j,a_k，可以给每个二进制数记录两个下标，表示它的超集的最靠后的两次出现位置，需要稍微递推一下。（2026-3-10）

  bitset

• CF754E Dasha and cyclic table\ 给一个循环的字符矩阵 s，和一个不循环的字符矩阵 t，求 t 在 s 中的所有出现位置（n\le 400）\ 将 s 拆成 26 个字母每一位是否出现。枚举到 t 的每一位时，对于一个坐标 (x,y)，如果 s_{x,y}=t_i，则说明 (x-i,y-j) 可以作为一个对应的位置，而其他位置不可以。可以用 bitset 优化。（2026-3-5）

• CF914F Substring in a String\ 题意：给一个字符串，进行修改一个字符或者查询一个字符串在 [l,r] 内作为子串的出现次数。\ 思路：把字符串拆成 26 个 01 串，进行 ans&=a[t[i]-'a']>>i 的操作，也就是把原串 [l,r] 的部分向前移动，然后判断每位是否相等。使用 bitset。\ 标签：bitset、字符串匹配（2026-4-18）

• GYM 103446J Two Binary Strings Problem\ 题意：给两个二进制串 a 和 b，对于 k\in [1,n]，求出是否满足 b_i=f(\max(i-k+1,1),i)，f(l,r)=[\sum_{i=l}^ra_i>\frac{r-l+1}{2}]\ 思路：把 0 计为 -1，算前缀和，区间的 f 为 1 即 s_{l-1}<s_r，用 bitset 统计对于每个 i，前缀和小于它的位置有哪些，由此统计出那些 k 是可能可以的，取与即可。\ 标签：bitset、中位数（2026-4-21）

  推式子

• CF1139D Steps to One 期望 dp，需要一点解方程的思想，然后带入莫比乌斯函数的式子（难点在于不会莫比乌斯函数的定义）

• NOIP-2025-T2 sale 首先贪心可以发现不满足的情况不多，组合计数的地方是说 a_i>a_x 时可以选择 w=1 或 2，但一定会被算到那 m-2 块钱的地方，a_y<a_i<a_x 的部分可以选择不被算到那里面或者 w=1，所以先把 a_i>a_x 的部分都加上 1 的代价，然后从整体中选择一部分就可以了，也就是说先减去一些东西使得两部分问题相同，然后再整体选（2025-12-2）

• CF1656F Parametric MST\ 题意：有 n 个点，任意两个点 i 和 j ，则它们之间存在一条权值为 (a_i+a_j)t+a_i\cdot a_j 的边，求当 t 取任意值时，求最小生成树的权值和的最大值是多少（可以证明是整数）\ 思路：(a_i+a_j)t+a_i\cdot a_j=(a_i+t)(a_j+t)-t^2，所以按照 a_i 排序后，大于 0 的都连到 1，小于的都连到 n，这样一定是最优的。推一下式子会发现答案里面 t^2 这项被消掉了。所以取到最大值的时候 t 一定是等于某个 -a_i。\ 标签：推式子、贪心（2026-3-17）

• CF286D Tourists\ 题意：有一条直线上的 m 个线段，每个线段有个出现时间 t_i，有 n 个观察点，q_i 时刻从原点开始向正方向以 1 的速度做匀速直线运动，求每个点有多长时间看见的是线段。\ 思路：考虑一个线段与一个观察点，这个点有多长时间被阻挡。答案是 \begin{cases}0&q\in[0,t_i-r_i)\\t+r_i-t_i&q\in[t_i-r_i,t_i-l_i)\\r_i-l_i&q\in[t_i-l_i,+\infin)\end{cases}。由于线段可能重叠，所以需要用 set 维护一下每段线段最早出现的时间，跟颜色段均摊类似。\ 标签：推式子、线段树、颜色段均摊（2026-4-3）

• CF2217G Down the Pivot\ 有 n 个点组成一个二叉树，进行黑白染色，求有多少种染色和建树方法能使得最少进行 k 次下列操作恰好所有点变成白色：选择一条经过根的路径并翻转。\ 如果是一条链，答案是 \binom{n}{k} C(n)（卡特兰数）。所以答案是 \sum_aC(a)C(n-a-1)\sum_{\max(x,y)\in\{k-1,k\}}\binom{a}{x}\binom{n-a-1}{y}，后面可以用 S(i,j)=\sum_{k\le i}\binom{k}{j} 容斥（2026-5-14）

  斐波那契数列

• CF605E Mushroom Gnomes\ 题意：给 n 个数，初始时非降，一秒后每两个相邻的数之间会蹦出一个值为二者之和的数，x 秒后重新排序，然后再等 y 秒，求最终所有数的和。x,y\le 10^{18}\ 思路：sum'=3sum-a_1-a_n，所以需要求 x 秒后的最大值和最小值（a_1）。最大值一定由初始时的 a_n 和 a_{n-1} 组成，且系数为斐波那契数。用矩阵快速幂求解。\ 标签：找规律（2026-4-17）

• CF126D Fibonacci Sums\ 题意：给一个数，求它分解成若干个不同斐波那契数之和的方案数。\ 思路：根据齐肯多夫定理，通过贪心的方法，每个数都可以分解成若干个斐波那契数之和。Fibonacci 数列其实长度很短，发现对于一种合法的答案，可以将一个选了的换成两个没选的，可以抽象成一个 01 串，然后 dp 就行，考虑每一位是否变成 0 并将前两位变成 1。\ 标签：斐波那契数、dp（2025-11-26）

  MEX

• P15652 省选 2026 day2 T1 perm\ 猜一个排列，每次可以询问一个区间的 mex，猜的次数不超过 n 次\ 性质：一个区间的 mex 是区间补集的 min；如果知道了 0 的位置，不包含 0 的区间没有意义。找到 0 的位置之后可以分别求出 0 前面位置的前缀最小值和 0 后面位置的后缀最小值。通过最小值可以确定一些位置，剩下的可以从大到小考虑数字放哪里，哪边限制紧就优先填。\ tag: mex, permutation, special problem（2026-3-13）

  同余/取模

• CF1421E Swedish Heroes\ 题意：给一个序列，一次操作选择下标 i，把 a_i 和 a_{i+1} 替换成 -(a_i+a_{i+1})，求最终剩余的数的最大值。\ 思路：一次操作相当于合并两个连续段，可以区间 dp。也就是给每个位置分配一个符号 + 或 -，乘上 a_i 求和。拼凑必要条件，即不能 +-+-+-（第一次操作的两个位置符号相同），并且 len+c\equiv 1\pmod 3。证明：归纳法，若两个区间 (l_1,c_1) 与 (l_2,c_2) 满足，它们合并起来是 (l_1+l_2,l_1+l_2-c_1-c_2)，和为 2l_1+2l_2-c_1-c_2\equiv-l_1-l_2-c_1-c_2\equiv-(l_1+c_1)-(l_2+c_2)\equiv 1，而观察发现长度为 1 的时候满足。然后正常 dp 就行。\ 标签：观察性质、取模、dp（2026-4-10）

• CF1515G Phoenix and Odometers\ 题意：给一个有向图，询问若干次，每次问是否能从 u 出发走一个长度在模 t 意义下是 -s 的环（可以重复走）。\ 思路：结论为在一个强联通分量里如果有模 t 为 x 的一条路 a\rightarrow b，则一定存在长度 -x 的一条路 b\rightarrow a，构造为从 b 出发到 a 再回来，重复 t-1 次，然后再走到 a，设 b\rightarrow b 长度为 y，则这样走的总长度为 x(t-1)+yt\equiv -x。进而还有结论为如果 a 在长度为 x 的环中，则 b 也在长度为 x 的环中，构造为 b\rightarrow a，a 转一圈回来，然后 a\rightarrow b，总长度为 x。注意到环长可以叠加和增倍，所以所有简单环长度的 \gcd 的倍数长度的环都可以构造出来。于是 tarjan 之后用 dfs 树求出每个强联通分量里的 \gcd，询问的时候只需判断就行。\ 标签：强联通分量、取模与同余、裴蜀定理（2026-4-24）

  数论·gcd

• P14199 Make It Divisible 求给序列每个数加上一个 x 之后求 gcd，可以差分成差的 gcd 与其中一个值加 x 的 gcd，然后套笛卡尔树（2025-12-6）

  数论·因数

• CF1699E Three Days Grace\ 给一个序列，一次操作可以把一个数替换成它的两个非一因子，求经过若干次操作之后序列的极差最小是多少\ 固定最小值求最大值最小是多少。假设当前最小值为 x，一个数 i 被分解且每个数都不小于 x 的情况下，最大的数最小为 f_i。需要知道这个值的最大值。如果把 x+1 变为 x，则只有 x 的倍数才可能改变 f 的值，所以时间复杂度是 O(m\log m)。\ tag: number theory, log, two pointers（2026-3-14）

• CF1285F Classical?\ 题意：给 n 个数，求 \text{lcm}(a_i,a_j) 的最大值。\ 思路：有一个结论，对于任意数 x 和 y，一定存在 a|x,b|y,\gcd(a,b)=1,\text{lcm}(a,b)=\text{lcm}(x,y)，这样可以不用枚举两个数的最大公因数是什么了。将所有数的因子从大到小排序，考虑当前的 x 能找到的最大的与之互质的数 y，显然处理过的且比小的数没有用了，用栈维护可以用的数，判断是否存在互质的数可以用莫比乌斯函数套路地维护。\ 标签：唯一分解定理、因数和倍数、莫比乌斯函数（2026-4-23）

• CF896D Nephren Runs a Cinema\ 题意：求有多少个由 0、1、-1 构成的长度为 n 的序列，满足任意前缀和非负且所有数的总和在 [l,r] 之间。\ 思路：枚举 0 的个数，转化为一个类似卡特兰数的问题，然后发现中间某些项可以一一对应消掉，最终答案为 \sum_{i=0}^n\binom{n}{i}(\binom{n-i}{\lceil\frac{n-i+l}{2}\rceil}-\binom{n-i}{\lfloor\frac{n-i+r}{2}\rfloor+1})，但由于模数不是质数，所以需要把 p 分解质因数，求组合数的时候统计每个的出现次数，减去分母中的，最后再算上。\ 标签：卡特兰数、取模（2026-4-24）

• CF2200H Six Seven\ 给一个序列，求最小的 k 使每一个 a_i+k 里 7 作为因子的次数小于 6 的次数。\ 若 x 不是 42 的倍数，则 x\bmod 42 需要是 6 的倍数；否则 \frac{x}{42} 满足这个条件。递归地求，每次枚举加的数，加上之后把 42 的倍数除以 42 再递归到下一层。（2026-5-16）

  数论·欧拉函数/定理

• CF311D Interval Cubing\ 题意：给一个序列，一次操作将区间内的数都变为它的立方，询问区间和。模数为 95542721。\ 思路：考虑循环节，即求 m 满足 a^{3^m}\equiv a\pmod p，则 3^m\equiv 1\pmod {\varphi(p)}，可以得到 m=48。所以线段树上维护循环节每一位的答案，修改时轮换。\ 标签：数论、欧拉定理、线段树（2026-4-2）

• CF906D Power Tower\ 题意：给一个序列，进行 q 次询问，询问区间 [l,r] 的 a_l^{(a_{l+1}^{(a_{l+2}^{\cdots^{a_r}})})} 的值模 m 的答案。\ 思路：模的数为 m，则 (a_{l+1}^{(a_{l+2}^{\cdots^{a_r}})}) 对 \varphi(m) 取模，以此类推，直到这个值变为 1，取模后就都是 0 了。暴力用扩展欧拉定理算。\ 标签：扩展欧拉定理（2026-4-14）

  数论·离散对数

• CF1106F Lunar New Year and a Recursive Sequence\ 题意：给一个递推式子 f_i=\prod_{j=1}^kf_{i-j}^{b_j}，一切运算在模 998244353 意义下进行，已知 b，并且 f_1 到 f_{k-1} 都是 1，求 f_k 使得 f_n 等于 m。\ 思路：用矩阵快速幂求出 f_n 是 f_k 的几次幂（设为 q），则已知 x^q\equiv m\pmod p，求 x。又知道 3 是 998244353 的原根，设 x\equiv 3^s，则 3^{sq}\equiv m，又已知 q，即先求 sq\pmod {\varphi(p)} 的值，然后求逆元得到 s 的值。\ 标签：BSGS、原根（2026-4-13）

  莫比乌斯函数与莫比乌斯反演

• CF1559E Mocha and Stars\ 题意：给求一个序列 a 的数量满足 l_i\le a_i\le r_i，\gcd_{i=1}^n a_i=1，\sum_{i=1}^n a_i\le m，m\le 10^5,n\le 50。\ 思路：如果不考虑最小公因数的约束，答案可以用前缀和优化背包 dp 解决。\sum_{a}[\gcd(a)=1]g(a)=\sum_{a}g(a)\sum_{d|a_i}\mu(d)=\sum_{d=1}^m \mu(d)\sum_{a_i=\lceil\frac{l_i}{d}\rceil}^{\lfloor\frac{r_i}{d}\rfloor}g(a)，所以枚举 d，然后再套背包 dp 求后半截式子。\ 标签：莫比乌斯函数、背包 dp（2026-4-14）

  组合数学

• at_arc215_d cresc.\ 题意：求有多少个长度为 n 的序列 s，使得存在一个长度为 n+1 的序列 a，满足 a_i\in[0,m]， s_i=a_i+a_{i+1}，s_i\le s_{i+1}。\ 思路：a 由两个非减序列间隔着拼成，设为 b 和 c，若 b_1=0 或 c_e=m 则唯一对应一种合法的 s，可以理解为将 b 序列整体调整为最小的情况。所以答案是 \binom{m+o}{o}\binom{m+e-1}{e-1}+\binom{m+o-1}{o-1}\binom{m+e}{e}-\binom{m+o-1}{o-1}\binom{m+e-1}{e-1}\ 标签：组合计数、贪心（2026-3-31）

• at_arc201_e Total Area of Bounding Boxes\ 题意：给一个排列，表示 n 个点 (i,p_i)，求 \sum_{T\sub S}(\max_{i\in T}i-\min_{i\in T}i)(\max_{i\in T}p_i-\min_{i\in T}p_i)。\ 思路：考虑每个 1\times 1 的格子被包含的次数，设其左上角、右下角、左下角、右上角的点的集合分别为 A,B,C,D，则答案需要满足 A,B 中各选一个或者 C,D 中各选一个，然后容斥，推一下式子，再写个二位偏序的线段树。\ 标签：推式子、线段树（2026-4-1）

• CF961G Partitions\ 题意：给 n 个数，划分成 k 个子集，求每种划分方案中所有子集内元素和乘子集大小的和的和是多少。\ 思路：乘上子集大小就相当于与 i 同一个集和里的每一个数 j 都给它一次贡献。如果 i=j，贡献为 S(n,k)，否则为 S(n-1,k-1)，所以答案就是 \sum_{i=1}^nw_i(S(n,k)+(n-1)S(n-1,k-1))。\ 标签：第二类斯特林数、组合意义（2026-4-5）

• CF932E Team Work\ 题意：给 n 和 k，对于一个大小为 n 的集合，对于它的所有真子集的大小 i，求 i^k 之和。\ 思路：组合意义为选出真子集之后，有 k 个数，每个数选择一个集合放进去的方案数。注意到非空的集合最多 k 个，所以枚举非空集合数，答案为 \sum_{i=1}^kS(k,i)\times\frac{n!}{(n-i)!}\times2^{n-i}。\ 标签：组合意义、第二类斯特林数（2026-4-24）

• CF111D Petya and Coloring\ 题意：给一个 n\times m 的矩阵，有 k 种颜色。染色后满足任意竖直的直线把矩阵分成两部分的出现的颜色种类数想通，求方案数。\ 思路：发现需要满足两个条件，即第一列和最后一列颜色种类数相同，且中间的列的颜色都属于第一列与最后一列的交集，然后容斥，推一推式子。\ 标签：推式子（2025-11-19）

  容斥

• CF1780F Three Chairs\ 求有多少对 (i,j,k) 满足 \gcd(\max(a_i,a_j,a_k),\min(a_i,a_j,a_k))=1\ 使用质因子进行容斥，枚举最大最小两个，记录 cnt 表示小于某个数的数的个数（2025-11-19）

• CF547C Mike and Foam\ 有 n 个数，每次删去一个或把一个放回去，求有多少对互质的数。\ 使用质因子进行容斥，也就是以加入为例，加上 1 的倍数的个数，减去包含一个因子的，加上包含两个的……（2025-11-18）

• at_abc456_g Cound Holidays\ 给一个 01 串，0 的部分可以选择填 0 或者 1，对于所有 k 求有多少种填的方法使得连续 0 的个数最多恰好为 k。\ 发现被 1 划分之后各部分独立。容斥转化为求 f(n,k) 表示连续的 0 都不超过 k 个。相当于连续的 0 超过 k 个的段恰好为 0 个，容斥为 g(n,k,i) 表示长度为 n 的一段种，至少有 i 段 0 的长度 \ge k+1 的方案数。这个分类讨论第一个位置是否放 0，插板求。（2026-5-3）

  概率与期望

• CF1096F Inversation Expectation 分讨处理，使用树状数组和前缀和

• CF2071E Leafall
  题意：一棵树，每个点有一定概率会断开所有与之相连的边，求最终期望的叶子对数量（叶子指度数恰好为 1 的点）
  思路：按照距离分类讨论，因为如果距离小于等于 2 可能会相互影响。推式子：

  \sum_{u=1}^n \sum_{v\in nbr(u)}pe_u pe_v \prod_{i\in nbr(u),i\neq v}pd_i\prod_{i\in nbr(v),i\neq u}pd_i\\+\sum_{u=1}^n [pe_u \sum_{x\in nbr(u)}\sum_{y\in nbr(u),y\neq x}pe_xpe_y(\prod_{i\in nbr(x),i\neq u}pd_i)(\prod_{i\in nbr(y),i\neq u} pd_i)\\+pd_u\sum_{x\in nbr(u)}\sum_{y\in nbr(u),y\neq x}pe_xpe_y(\sum_{i\in nbr(x),i\neq u}pe_i\prod_{j\in nbr(x),j\neq i\neq u}pd_{j})(\sum_{i\in nbr(y),i\neq u}pe_i\prod_{j\in nbr(y),j\neq i\neq u}pd_{j})]\\+\sum_{u=1}^n\sum_{dis(v,u)>2}pe_upe_v(\sum_{i\in nbr(u)}pe_i\prod_{j\in nbr(u),j\neq i}pd_i)(\sum_{i\in nbr(v)}pe_i\prod_{j\in nbr(v),j\neq i}pd_i)

  预处理一些东西，对于中间两种，可以把前面枚举过的 x 的和记录下来，然后计算答案后再将当前枚举的 y 的贡献加上（2026-2-19）

• at_abc450_g Random Subtraction\ 题意：给一个序列，一次操作会随机选择两个元素，将它们删除并把其中一个减去另一个的差插入到序列中，求最终剩余的数的平方的期望值。\ 思路：把平方拆开，一部分可以直接通过序列计算，一部分需要知道每个元素的系数是什么，系数对于所有的下标对称，所以只需要知道 \sum c_ic_j 的期望值 C_n，然后均摊给所有的 c_i\times c_j。假设第一步会操作 a_1 和 a_2，则 c_1c_2=-1，c_1c_i+c_2c_i=0，然后可以从 C_{n-1} 递推。\ 标签：期望（2026-3-21）

• CF1523E Crypto Lights\ 题意：有 n 个灯，每次等概率选取一个未亮起的灯泡点亮，直到有两盏灯距离小于 k 结束，求期望几次结束。\ 思路：枚举结束需要的次数乘上概率求和，式子里有 i，所以把贡献摊给前面的数，也就是说枚举 i，求 i 次操作没有结束的概率之和。答案为 \binom{n-(k-1)(i-1)}{i}\div\binom{n}{i}。\ 标签：期望、概率、前缀和、组合计数（2026-4-11）

  几何

• CF23D Tetragon 一个顶点需要在相邻两个点的垂直平分线上，所以求出解析式暴算（2026-1-7）

• P2076 曼哈顿最小生成树\ 题意：给 n 个点，任意 (x_1,y_1) 和 (x_2,y_2) 之间都有一条权值为 |x_1-x_2|+|y_1-y_2| 的边，求最小生成树。\ 思路：MST 满足任意一个三元环最大的一条边不可能出现在上面。所以对于一个点，它只需要连 8 条边，把它看做原点就是 x、y 轴和 y=x、y=-x 这四条直线切分出来的八个区域中各选一个最近的，因为任意两个点 A 和 B，如果 A 离 O 更近，则 AB\le OB，所以 OB 是三元环 O-A-B 中最大的一条边\ 标签：MST、几何、二位偏序（2026-4-11）

• at_abc221_g Jumping Sequence\ 题意：给 n 个数，一次操作选择一个方向移动这么多距离，求是否能够最终到达 (x,y)。n\le 2\times 10^3,|x|,|y|\le 10^6\ 思路：旋转坐标系 45°，即求能否到达 (x+y,-x+y)，操作的横纵坐标可以分开考虑，选择加一或减一。可行性背包 dp，用 bitset 优化。\ 标签：几何、bitset（2026-4-19）

• CF40C Berland Square 求两组同心圆把平面划分成多少部分，数数（2025-11-20）

• CF274C The Last Hole!\ 初始有一些点，以同样的速度扩展成圆，求圆之间形成而消失的最后一个洞消失的时间。n\le 100\ 这个洞一定是三个圆或四个程菱形的圆挤出来的，因为钝角的三角形没有用。需要计算三角形外接圆圆心和半径。\ 标签：几何（2026-5-2）

  矩阵乘法

• at_abc456_f Plan Holidays\ 有 n 个位置，初始为 0，一次可以花 a_i 的代价使 i 变为 1，或者把两个 1 之间夹着的一个 0 变成 1，求制造一个连续 k 个的 1 的子串所需要的最小代价。\ 容易写出 n^2 的 dp，然后变为 min-plus 矩阵乘法，枚举起始点，用线段树维护然后计算最小值。（2026-5-3）

  高斯消元

• CF113D Museum\ 题意：一个图上有两个人，若一个人在点 i 上，则下一秒有 p_i 的概率在原地，1-p_i 概率随机走向其中一个邻居，求两个人相遇在 u 的概率。\ 思路：设 f_{i,j} 表示第一个人在 i，第二个人在 j 的状态的期望出现次数，列出方程组高斯消元。\ 标签：概率与期望、高斯消元（2026-4-15）

  线性基

• CF724G Xor-Matic Number of the Graph 找 dfs 生成树，再把环都扔到线性基里面，再考虑每一位答案如果取 1 一共多少种方案数（2026-1-2）

• CF845G Shortest Path Problem?\ 题意：给一个图，求从 1 到 n 的最小路径异或和。\ 思路：路径一定是一条从 1 到 n 的简单路异或上若干个环得到的。而环一定是 dfs 树上的一条路径再加上一条非树边得到的。所以把环都存到线性基里，然后查询异或 dis_{1,n} 后的最小值。\ 标签：线性基、dfs 树（2026-4-16）

• CF959F Mahmoud and Ehab and yet another xor task\ 给一个序列，询问若干次，每次询问一个前缀中的数有多少种方式表示 x。\ 用线性基判断是否可以表示，如果可以，任何一个不在线性基内的数都可以选择是否替换，答案是 2^{l-cnt}，其中 l 是前缀长度，cnt 是线性基里的数的数量。（2026-5-5）

  多项式·插值

• CF622F The Sum of the k-th Powers\ 题意：求 f(n)=\sum_{i=1}^n i^k 取模后的值。n\le 10^9,k\le 10^6。\ 思路：这个函数是一个多项式。计算出来 k+2 个点，然后插值求出函数，再代入 n。f(n)=\sum_{i=1}^{k+2} y_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}，注意到 x_i=i，所以预处理或一边枚举一边计算。\ 标签：多项式插值（2026-2-4）

• Q7.5.6.4 Chrip-Z 变换问题\ 给一个等比数列插值\ 模板，写笔记里了（2026-2-9）

  多项式·卷积

• CF914G Sum the Fibonacci 枚举 p，整体是一个 AND 的卷积，中间三个部分，其中一个是子集卷积，还有一个是 OR 的卷积，另一个统计一下就行（2026-1-4）

• Q7.5.2.5 万径人踪灭
  求一个字符串有多少个子序列使得它的字符和位置都关于一条轴对称，并且它不是连续的
  即先对每个轴找出来有多少对字符是对称的，然后 2^k 计算，再减去连续的。也就是找下标和为特定值的字符对是否相等。分别把字符为 a 和 b 的位置标为 1 做一次卷积，然后加起来。连续的可以用 manachar 求。（2026-2-8）

  生成函数

• Q7.5.4.1 斧头
  给若干个互不相等的自然数，求选取 1~3 个不同的数相加能够组成哪些数，并求出方案数
  设 f(x)=\sum_{i=1}^n x^{a_i}，相加就相当于卷积，需要容斥一下。

  B=\frac{f*f-u}{2}\\ C=\frac{f*f*f-3f*u+2v}{6}

  其中 u 表示两个相等的数的和为 i 的方案的生成函数，v 则为三个的。（2026-2-23）

• CF2174F Mosaic Tree\ 题意：给一个序列表示一棵树上每个点的颜色，再给一个 01 序列表示对于颜色 c，所有颜色为 c 的点的度数和为奇数或偶数，求树的构造方案数。\ 思路：一个点的度数等于它在 prufer 序列中的出现次数加一，可以由此推出每个点在 prufer 序列中的出现次数，所以求 prufer 序列的构造方案。考虑构造 m 个生成函数，对于每个颜色 k，x^i 的系数表示这个颜色的总出现次数为 i 的方案数，答案就是 k 个生成函数卷积后 x^{n-2} 的系数。f_k(x)=\sum_{i\equiv a_k}\frac{cnt_k^i x^i}{i!}，由 e^x 的泰勒展开式可以得到 f_k(x)=\frac{1}{2}(e^{cnt_kx}+b_ke^{-cnt_kx})，其中 b_k 为 1 或 -1，取决于 a_k 的奇偶。再推卷积后的式子，可以表示为形如 g(x)=\frac{1}{2^m}\sum_{i=-n}^n h_ie^{ix} 的形式，系数可以用背包 dp 求解，也就是每次可以选择 e^{cnt_kx} 或 b_ke^{-cnt_kx}。然后把式子展开，只取 x^{n-2} 的系数，得到 \frac{1}{2^m}\sum_{i=-n}^nh_i\frac{i^{n-2}}{(n-2)!}，这个 (n-2)! 会消掉，因为一开始没有考虑 prufer 序列中点的顺序。\ 标签：prufer 序列、生成函数、背包 dp（2026-4-9）

  构造

• CF1748D ConstructOR 规定 a|x=x，b|x=x，然后用 d 拼成 x

• CF1227G Not Same 从大到小排序，每列开头比前一列往下一格开始，顺次放就行（2025-12-23）

• CF1340D Nastya and Time Machine 结论是最大度数，构造时一旦一个点的时间到达答案就减去该点的度数（2026-1-3）

• CF2189E Majority Wins\ 给一个 01 串，求把它操作变为一个 1 的代价。可以对于子串 [l,r]，把里面的数合并成它们的众数（不小于一半），代价是 r-l+1。\ 代价等价于删除一个数需要 1 的代价，而一次操作有额外的 1 的代价。如果有 1，答案一定不大于 4，因为可以把 1 左侧合并，右侧合并，再用两次操作合并到一起。然后分类讨论。（2026-5-16）

  转化

• CF2187D Cool Problem\ 对于一个 01 串 r，定义一个序列 c，其中 c_0=0,c_i=\begin{cases}x+c_{i-1}& r_i=0\\y-c_{i-1}&r_i=1\end{cases}，给一个未完成的 01 串求所有可能的 \sum_{i=1}^nc_i 的值之和是多少。\ 转化为 c_{i}-\frac{x+y}{2}=\begin{cases}c_{i-1}-\frac{y-x}{2}&r_i=0\\\frac{y-x}{2}-c_{i-1}& r_i=1\end{cases}。因为 (c_i-\frac{x+y}{2})^2=(c_{i-1}-\frac{y-x}{2})^2\Rightarrow (c_i^2-c_{i-1}^2)-y(c_i-c_{i-1})+xy=x(c_i+c_{i-1})，两侧求和，得到 f(r)=\frac{c_n^2+(x-y)c_n+nxy}{2x}，所以求出 c 就行。设 f_{i,j,k} 表示前 i 个位置，x 系数为 j(-n\le j\le n)，y 系数为 k(0\le k\le 1) 是否可以。

  交互题

• CF2129C3 Interactive RBS 二分求出一对相邻的 ( 与 )，然后设计成 [(a] ( [(b(b] ( [(c(c(c] 这样的东西，每一部分的长度尽量小，但需要满足每一部分给答案的贡献必须比前面贡献的和还要大（2025-12-24）

  博弈论

• CF812E Sagheer and Apple Tree 把阶梯博弈搬到树上，如果到叶子距离为偶数的点的异或和为零则先手必败（2025-12-10）

• CF1942E Farm Game\ 题意：在 [1,l] 的位置中，有 n 个 FJ 的牛，n 个 FN 的牛交错排列，一次移动自己的牛往左或右移动一格，不能撞，不能动的输，求 FJ 赢的方案数。\ 思路：如果相邻的 FJ 和 FN 的 n 个对中，两头牛的距离都是奇数则必败，否则必胜。\ 标签：博弈（2025-11-22）

  区间上问题

• CF369E Valera and Queries 正难则反，求不包含点的区间，这样不会重复算（2025-12-27）

  SA

• P2870 Best Cow Line G\ 题意：给一个字符串，每次从头或尾选一个字符拿出来放入队列中，求形成的字符串字典序最小的情况是怎样。\ 思路：优先选大的一边，但如果有相同的则需往中间跳，找到第一个不同的位置比较，即给正串的后缀和反串的后缀进行比较，所以把反串拼到原串后面，中间夹一个 #，然后后缀排序。\ 标签：SA（2026-3-24）

• P2852 Milk Patterns G\ 题意：给一个字符串，求出现次数大于等于 k 的子串长度最长是多少。\ 思路：子串是后缀的前缀，所以就是求后缀排序之后相邻的 k-1 个 height 的最小值的最大值。\ 标签：SA（2026-3-27）

• P1117 优秀的拆分\ 题意：求一个字符串里面形如 AABB 的子串数量。\ 思路：枚举中间的分界线，即求以 i 结尾且形如 AA 的串的数量，以及以 i+1 开头且形如 AA 的串的数量。枚举长度 l，每隔 l，取一个点，一个这样的串一定经过两个点且这两个点 i 与 j，满足 lcp(i,j)+lcs(i-1,j-1)\ge l，然后记录答案（区间加）即可。\ 标签：SA（2026-3-28）

  dp·结论

• CF1070J Streets and Avenues in Berhattan 小贪心，只有一种字符横竖都出现的时候一定不劣。再贪心，当确定哪个字符重复之后，其他的都尽量选满。然后使用背包 dp

• CF1132E Knapsack 诈骗题，无论用哪种数都可以每 840 组成一组，再把剩下的背包 dp 以下。

• CF1172C1/2 Nauuo and Pictures 跟具体有那些牌喜欢以及初始时的权值没太大关系，只要知道喜欢的牌和不喜欢的牌的权值就可以了，期望 dp，之后把一张权值为 w_i 的牌拆分成 w_i 个价值为 1 的牌

• CF1197E Culture Code 按照里面体积排序，用树状数组优化 dp（也可以建图求最短路）

• CF1798E Multitest Generator 小结论，答案只能是 0 到 2，然后 dp，修改的地方不一定是最前面的位置

  dp·状态的定义

• CF1151F Sonya and Informatics 矩阵乘法加速 dp，难点在于 dp 状态的选择，相较于记录逆序对数量，记录复位数量更为简便

• CF711D Bear and Company\ 题意：给一个字符串，求至少多少次交换相邻项的操作之后能够使整个字符串没有 VK 的子串。\ 思路：设 f_{i,j,k,c} 为最终的字符串的前若干位由前 i 个 V，前 j 个 K，前 k 个其他字符组成且最后一个字符种类为 c 时，所需要的最少操作次数。转移的时候考虑逆序对数量的变化。\ 标签：dp，逆序对

  dp·转移

• CF1015F Bracket Substring 与括号相关的 dp，这里用一位记录 01 的前缀和，需要使用钦定大法，转移的方法与 KMP 相似

• CF1874C Jellyfish and EVA DAG 上 dp，需要预处理辅助转移用的数组，代表后继点有 i 个，选择优先级第 j 大的点的概率是多少，这个东西的转移需要分类讨论第一步选的失败的点是在 j 之前还是之后（2025-12-23）

• CF1131E String Multiplication 有点像小白逛公园的 dp

• CF1430F Realistic Gameplay\ 题意：你有一把枪，这把枪的弹夹量为 k 发，并且刚开始弹夹是满的。每次换弹都需要 1 单位时间，丢弃目前弹夹里的全部子弹并将弹夹装满。你的射击技术十分高超，可以不耗费任何时间射出 1 发子弹并消灭一个敌人。现在有 n 波攻势，第 i 波有 a_i 个敌人，出现时间为 [l_i,r_i](r_i\le l_{i+1})。你需要在保证消灭所有敌人的条件下，让使用的子弹最少（使用的子弹数 = 消灭敌人的子弹数 + 丢弃的子弹数）。注意，在最后一波攻势结束后，不丢弃弹夹中剩余的子弹。\ 思路：如果两波之间有缝隙则可以在缝隙里把弹夹填满；否则可能会出现需要在一波刚开始的一秒内需要填满弹夹的情况。设 f_i 表示解决第 i 至 n 波需要开始时弹夹里有多少个子弹，如果紧挨着下一段则需要在结束时剩余 f_{i+1} 个，倒着求一遍之后，可以贪心地操作了。\ 标签：dp，贪心（2026-3-23）

• CF2053F Earnest Matrix Complement\ 题意：给一个矩阵，一些位置需要你填。设 c_{i,j} 表示第 j 行中 i 的个数，最终需要让 \sum_{i=1}^k\sum_{j=1}^{n-1}c_{i,j} 最大，求这个值。nm\le 6\times 10^5\ 思路：结论为同一行都填一种颜色更优。设 f_{i,j} 为将第 i 行的空位置都填上 j 得到的答案，先不考虑原本填好的位置自己跟自己的贡献，则 f_{i,j}=c_{i,?}(c_{i-1,j}+c_{i+1,j})+\max(\max_{k=1}^m f_{i-1,k},f_{i-1,j}+c_{i-1,?}\times c_{i,?})。形如 a'=max(a+x,y)。可以给全局搞几个标记 x，y 与 max，然后单点加的部分只有当 c_{i-1,j}+c_{i+1,j} 不为零的时候才有用，所以时间复杂度满足条件。\ 标签：贪心、dp、数据结构（2026-3-27）

• at_ndpc2026_i Update Positions\ 给一些元素，求有多少种排列出来的序列使得前缀最大值更新点的个数恰好为 L，后缀最大值更新点的个数恰好为 R，n\le 400\ 设 f_{i,l,r} 表示考虑了 >i 的所有数字，其中已经有 L 个前缀最大值更新点，有 R 个后缀最大值更新点的方案数。f_{i,l,r}\times g(tot+x+y-1,c_i-x-y)\rightarrow f_{i+1,l+x,r+y}，其中 (x,y) 表示放这种数会不会放在左右，g(n,m)=\binom{n+m-1}{n-1}。（2026-5-12）

  dp·优化

• CF1042E Vasya and Magic Matrix 前缀和优化 dp

• CF1156F Card Bag 前缀和优化 dp

• CF2122E Greedy Grid Counting\ 题意：给一个 2\times n 的网格，每个网格有个数，有些需要你填，满足任意子网格都存在一条贪心路径的价值与最大的一条路径价值相等，求方案数。所有路径必须向下或向右走，贪心路径指每次选择大的一侧走。n,k\le 500\ 思路：结论为贪心路径不满足的情况一定是因为先向下拐弯了。可以让下面一行向后错一位更好理解，设 c_i=a_{i+1}-b_i，如果一个子网格里第一个 l 满足 \forall i<l,c_i\ge 0,c_l<0，且存在 r 使 \sum_{i=l}^r c_i>0，则不满足条件。推广到整个网格，则所有满足 c_i<0 的位置都需要满足不存在前缀和大于零。设 f_{i,j} 表示考虑了前 i 位，且前缀和为 j 的方案数，需要满足前缀和始终不大于零，若再遇到一个 c_i<0 则前缀和清零重新算，所以第二位只要到 k 这么大就够了。 \ 标签：背包 dp，状态优化，贪心（2026-3-23）

  slope trick

• P12074 The arithmetic exercise\ 给一个序列 x，有一个初始为 0 的序列 a，依次对于 x 中的元素，选择一个下标 i，使 a_i\leftarrow x-a_i，求最终和的最大值。\ 注意到给每个位置安排一个系数 1/-1，需要从后往前操作否则会影响前面安排过的。设 f_{i,j} 表示考虑前 i 个操作使系数和为 j 时答案的最大值。一次转移后整体向左平移一位可以消除一个方程，然后用 multiset 维护差分（可以证明是单调递减的）（2026-5-14）

  dp·多重背包

• CF755F PolandBall and Gifts\ 给一个排列，构造一个 0 的数量恰好为 k 的 01 串，使得这个串按照排列移动一次再与上原本的串得到的 0 数量最多/最少\ 求最多的情况可以贪心。求最小值，如果有若干个环的大小之和恰好为 k 则答案为 k，否则答案为 k+1。需要背包 dp，然而数太大了。长度不小于 B 的环最多 \frac{N}{B} 个，直接背包 dp，时间复杂度 O(\frac{N^2}{\omega B})；长度小于 B 的用多重背包的方式写，复杂度是 O(BN)。取一个适当的 B 就行。\ tag: permutation, knapsack, sqrt-based divide and conquer（2026-3-12）

  dp·状压

• CF938F Erasing Substrings\ 题意：给一个字符串，进行 k=\lfloor\log_2 n\rfloor 次操作，第 i 次操作删除一个长度为 2^{i-1} 的子串，求最终字典序最小的字符串。n\le 5000\ 思路：设 f_{i,j} 表示考虑到 i 的前缀，操作状态为 j，也就是一个二进制串表示有没有进行删除长度为 2^l 的删除操作，这样的最小字典序。然而无法存储。发现如果保留的前缀长度相同，需要贪心地选下一位最小的，所以 dp 状态改为在当前条件下能否取到同样保留的字符串长度中字典序最小的那种。转移时先枚举保留的长度，直接输出最小的下一位就行。\ 标签：状压 dp、贪心（2026-4-5）

  dp·数位dp

• CF1073E Segment Sum 数位dp,考验代码能力

  记忆化搜索

• CF93E Lostborn\ 题意：给 k 个数（保证两两互质），求 [1,n] 中不能被任意一个数整除的数的个数。n\le 10^{13},k\le 100\ 思路：容斥不行，设 f_{i,j} 表示 [1,i] 中能被 a_1 到 a_j 中的某个数整除的数的个数。f_{i,j}=\lfloor\frac{i}{a_j}\rfloor+f(i,j-1)-f(\lfloor\frac{i}{a_j}\rfloor,j-1)，i 的状态只有 2\sqrt n 个，考虑半记忆化搜索，若 i 小于某个值就记下来。还有一个剪枝是初始给数排序。\ 标签：dp、半记忆化搜索、剪枝（2026-4-17）

  meet in the middle

• CF995E Number Clicker\ 题意：给两个数，一个模数，对第一个数进行不超过 100 次操作后得到第二个数，求方案。操作是在取模意义下加、减、取逆元。3\le p\le 10^9\ 思路：直接建图搜索，用折半搜索优化。时间复杂度不知道。\ 标签：概率、折半搜索（2026-4-12）

  图的形态·建图

• at_abc466_e Multiple_Free Sequences
  题意：给 a 和 b，求有多少对 x 和 y （0\le x,y<m）使得以它们作为初始值，f_{i}=af_{i-1}+bf_{i-2} 作为递推式的序列中没有数是 m 的倍数
  思路：可以让序列对 m 取模，不影响结果。将一个相邻的数对视作点，将递推视作边，可以建图，搜索一遍，把反图中 (0,x) 能到的点都标记。（2026-2-21）

• CF37E Trail for Chief\ 给一个黑白的网格，初始时有一个全白的网格，每次操作可以将一些联通的位置都涂成黑色或白色，求最少操作多少次才能把初始的网格变成给你的网格\ 定义距离为路径上需要切换多少次颜色，如果贪心地染色，一次修改之后会让修改过的地方和修改前的地方的距离加一。枚举最后一次修改的位置，从它为源点的最短路最大值最小，这个值就是答案。（2026-3-9）

• CF1584F Strange LCS\ 题意：给 n 个由大小写字母构成的字符串，其中一个字符串中同一个字符的出现次数不超过 2 次，求这 n 个字符串的最长公共子序列长度。n\le 10\ 思路：共 52 种字符。如果同一个字符的出现次数不超过 1 次，则记录每种字符的出现位置，如果两个字符满足在任何字符串中都是一前一后，则给它们之间连一条边，最后在 DAG 上找最长路。如果变为同一个字符出现次数不超过 2 次，则把每种字符拆成 2^n 个点，表示在每个串里的出现位置是第一次还是第二次的。\ 标签：建图、拆点、装压（2026-3-18）

  图的形态·拆点/合点

• CF1200F Graph Traveler 发现如果关于 2520 同余则实质上相同，把点按照到这里的值拆开，然后找环

• GYM 104787M Tree 得到的图是两个一样的图，边缘有些地方通过一些点相连，这个时候考虑将两个图拍在一起，发现共有的边是最多只能删一条的，边缘的边也是只能删一条的，共有的部分组成的树被删掉的边分成了多个连通块，需要每一个块恰好有一个边缘的边把两层连在一起。树形 dp 即可，推式子其实有点难度（2025-11-28）

  图的形态·拆边

• CF1209F Koala and Notebook 每个边拆成个位，然后 BFS，注意离 1 距离相同的点要同时转移（2026-1-16）

  图的形态·优化建边

• CF2081D MST in Modulo Graph
  题意：n 个点的完全图，每个点有一个权值，u 和 v 之间的边权为 max(p_i,p_j) \mod \ min(p_i,p_j)，求最小生成树的权值和
  思路：首先可以把重复的点去掉，然后建边的时候对于点 u，只在权值在 [p_i\times k,p_i\times(k+1)) 之间的点选择最小的连即可，然后跑最小生成树。（2026-1-22）

  树·建树

• CF856B Similar Words 一对字符最多选一个，所以考虑把可以通过删除第一个字符的操作得到的点与该点连起来建树，树形 dp（2025-12-14）

• CF1617E Christmas Chocolates\ 题意：给一个序列，求一对 (i,j) 使把 a_i 操作变为 a_j 需要的次数最多。对于 x，一次操作选择 2^k\ge x，把 x 替换为 2^k-x，且对于一对数操作时会选择操作数量最少的那种操作方案。\ 思路：结论是减小的操作必然选择最小的 k 进行操作，可以得到一棵树，答案就是求树的直径。不必把树建出来。\ 标签：贪心、建树（2026-4-10）

  树·结论

• CF429C Guess the Tree 多叉树叶子节点一定比非叶子节点多（2025-12-1）

• CF573C Bear and Drawing 树一定是一条链上挂几个链或者挂几个 Y 形，使用度数区分，然后判断链上的点度数都不超过 2（2025-12-5）

• CF2002D2 DFS checker 拼凑条件，如果任意相邻的两个都满足前一个是后一个的父亲或者前一个在后一个的父亲的子树内即可（2025-11-18）

• CF1016F Road Projects 主线上的一个点只能另外多连一个点，否则可以通过连接两个点的方式保证答案不变小（2026-1-9）

• CF1110F Nearest Leaf 向下移动的话，距子树内的点的距离减少 w，子树外增大 w。搜索一遍，用线段树维护距离（2026-1-12）

• CF1696F Tree Recovery
  题意：给定对于 x、y、z，[dis(x,z)=dis(y,z)]，求树的构造
  思路：如果知道了一条边，可以通过它推出整棵树，因此枚举 1 与谁相连（2026-1-22）

  树·贪心

• CF846E Chemistry in Berland 贪心地从叶子开始处理，如果最终根节点不欠，则可以（2025-12-12）

• CF1403B Spring Cleaning 对于一个点（不为根），如果子树内有奇数个叶子，则树内两两配对，多的向外连；如果偶数个，则保留两个（2025-12-24）

• CF758E Broken Tree 贪心从叶子到根尽量往大了选，如果不够了就标记一下子树里需要再减去几次，然后再搜一遍统计答案（2026-1-5）

  树·构造

• CF1391E Pairs of Pairs 同层内两两配对，这样任意两对的四个点之间最多有两条边，由于深度不超过 \lceil \frac{n}{2}\rceil 所以对数不少于 \lceil \frac{n}{2}\rceil（2026-1-15）

  树·遍历顺序与括号序列

• CF893F Subtree Minimum Query 用 dfs序为下标,dep为时间轴建立主席树,查询深度在某个值以内时某个点的子树里的最小值（2025-12-9）

• CF1062E Company 区间 lca 一定是 dfn 最小的点与最大的点的 lca，用 st 表维护最大、最小、次大、次小 dfn 值，考虑删除最大或最小（2025-12-19）

• CF372D Choosing Subtree is Fun 包含一些点的最小子树大小可以通过将它们按照 dfn 序排序后依次计算距离的方式算出来，此题还需二分并使用 set 维护区间的 dfn 序值（2025-12-25）

• CF607D Power Tree 对于一个点的答案，每个它子树里的点都会贡献路径上的所有 d 的乘积再乘上 a 的值，因此用 dfn 序在线段树上维护（2025-12-30）

• CF1045J Moonwalk Challenge 把 dfs 的序列求出来，第一次搜到计为 +，回溯计为 -，这样前缀就是从根到一个点的路径上的信息（2026-1-17）

• P3203 弹飞绵羊
  题意：给一棵树，支持修改一条边和查询一个点的深度
  思路：转化为括号序列，求深度就是求一个位置的前缀和，修改即将一个区间取走并插入到另一个位置，可以用平衡树实现（2026-1-28）

• Q6.2.5.2 这是我自己的发明
  题意：在一个树中，给 m 次操作，换根，或者给 x 和 y 求 \sum_{i\in subtree(x)}\sum_{j\in subtree(y)} [a_i=a_j]
  思路：如果没有换根，两个子树是两个区间。区间可以差分，于是答案可以容斥，然后用莫队维护，只是两个指针代表 [1,x] 与 [1,y] 中相等的数对个数。如果换根，子树可能是两个区间，同样可以差分。（2026-2-15）

• CF1149C Tree Generator\ 题意：给一个括号序列，进行 q 次交换两个位置的操作，每次求树的直径长度。\ 思路：在括号序列上，树的直径就是任意一个区间删除所有配对的括号之后剩下的括号的个数，也就是将 ( 视为 1，) 视为 -1 后，任意一个区间从中间分割之后，后半截减去前半截的差的最大值。用线段树维护，类似最大子段和。\ 标签：树上问题、括号、线段树（2026-4-5）

  树·路径问题

• CF1495D BFS Trees 如果两个点的最短路径不唯一则无解，然后对于不在最短路径上的点，把它们的父亲的可能个数乘起来（2026-1-18）

  树·重心

• CF294E Shaass the Great 枚举断开的边，使用换根 dp 求出两个连通块的重心连在一起（2025-11-29）

• CF708C Centroids 先找出重心，以它为根的时候，一个点的最大子树都是父亲所在的那个，树形 dp 求子树外最大的不超过 \frac{n}{2} 的子树大小最大值，如果能够通过将这一子树拼在该节点上，则这个点可以通过一次修改变为重心（2025-12-8）

• CF748F Santa Clauses and a Soccer Championship 找到所谓的重心，按照它为根搜索的顺序把所有有队伍的点找出来，然后匹配的时候只要跨过 k 就可以保证一定不在一个子树内（2025-12-9）

• CF843C Upgrading Tree 重心不会改变，重心的度数也不会改变，先构造成重心连着若干条链的形式，再构造成重心连着若干菊花图的形式（2026-1-6）

• CF2108E Spruce Dispute\ 给一棵奇数个点的树，求一个点对 (u,v) 表示删掉 v 并把 v 所连的其他点连到 u 上，使得剩下的点能够分配一种两两配对的方式，让配对两点距离的和最大\ 如果没有删边操作，找到重心，然后让剩下点两两跨过重心配对，多出来的一个点与重心配对。删掉一条边之后，如果删掉的点不是原来的重心，则重心不变；否则重心变为 u。可以枚举删哪条边判断，计算答案的时候可以直接计算答案的减少量求个最小。（2026-2-24）

  树·中心

• P11766 遥不可及 所有点到其所有最远点的路径都经过树的中点，找到中点，考虑其每个儿子的子树里的点与其他儿子子树里的高贵点相连的贡献。

  树·lca

• Q6.2.4.3 lca\ 题意：在一棵树上，对于 [l,r] 和 x，查询 \sum_{i=l}^rdep(lca(i,x))。\ 思路：答案可以差分。把 [1,i] 的所有祖先都进行修改，再查询 x 的祖先答案之和就是深度，这是利用了 lca 深度就是二者共同祖先数量的结论。把询问离线按照 i 排序处理。\ 标签：lca、差分、离线（2026-4-13）

  树·路径上的记忆化搜索 dp

• CF1292C Xenon's Attack on the Gangs 将贡献平摊，也就是对于每一个数求有多少个点对的 mex 大于等于它，这样就可以枚举选择哪两个点，构造使得它们之间的路径上可以取到连续的 mex，然后 dp（2025-12-21）

  树·区间 dfs 序 dp

• CF509F Progress Monitoring 拆开第一个儿子的子树便于判断，但是后面的点会形成一个森林，所以把 [i,j] 拆成 [i+1,k] 与 [k,j]，后面的 k 是一个虚点，只用于把森林连起来，注意特判只有一个儿子的情况（2025-12-2）

  树·状压 dp

• CF429C Guess the Tree 把叶子节点和非叶子节点放在两位，只有非叶子节点的部分需要装压（2025-12-1）

• CF599E Sandy and Nuts 钦定加子树的顺序是按照编号最小值从大到小，保证不算重复，lca 以及边的条件可以预处理（2025-12-28）

  树·普通树形 dp

• CF629E Famil Door and Roads 求到一个点的距离和，发现如果形成环，一定是在两个子树内分别选一个点连起来（特判有祖先关系的情况）（2025-12-2）

• CF960E Alternating Tree 树形 dp，注意以 u 为起点的路径个数为 n 个（2025-12-16）

• CF543D Road improvement 注意可能有对零取逆元的情况，需要特殊处理（2025-12-3）

• CF1252B Cleaning Robot 树形 dp，状态为根不能向上连边、可以连可以不连、必须连三种，注意可能有对 0 取逆元的问题，所以可以对于所有的儿子进行一个小递推。（2025-11-7）

• P3177 树上染色 转化为求每条边的贡献，树上背包 dp，但特别的是记录的是对整棵树的贡献而非对于子树的。（2025-11-4）

• CF935E Fafa and Ancient Mathematics 先把括号序列弄成一棵树，然后跑树上背包 dp（2025-12-15）

• CF1385F Removing Leaves 换根 dp，考虑最后删到最后剩下部分的根是谁，需要维护一个点能否删成只剩一个以及儿子当中有多少个能够删到只剩一个（2025-12-23）

• CF629D Preorder Test 二分答案，然后树形 dp，设 f[i] 表示从 i 开始搜索的最大长度，需要换根（2025-12-31）

• CF633F Chocolate Spree 需要很多分类讨论的 dp，分类依据是半条链或者整个链之间的位置关系（2026-1-1）

• CF1402C Star Trek\ 给一棵树，再复制粘贴 D 份，在相邻两层之间选择两个点连边，求方案数量，使得从初始那棵树一号节点开始，进行如下博弈先手必胜：两个人轮流在树上移动，无法移动的人输\ 只有连接两个必输点可能会改变第一棵树的根的答案。事实上可以求出分别以树上每个点为根，有多少个必输点通过连接下一棵树改变成必胜点的方式，可以使得这个根也改变胜负状态（记为 |Cr|）。设必输点所组成集合为 L，必胜点所组成集合为 W，复制粘贴的第 D 棵树上，以 v 作为根，且 v 出发会输的方案数为 (L_D)_v，L_D=\sum_{v}(L_D)_v。则\

  推一推式子，得到 $L_D=|L|N^{2D}+(\sum_{v\in W}|C_v|-\sum_{v\in L}|C_v|)L_{D-1}$。然后用矩阵快速幂优化，难点在于换根 dp。共维护一下值：$a_u$ 以 $1$ 为根 $u$ 是否必胜，$b_u$ 以 $u$ 为根 $u$ 是否必胜，$c_u$ 以 $1$ 为根 $u$ 子树里面能通过改变自己状态改变 $u$ 状态的点的数量，$d_u$ 以 $u$ 为根，有多少个点能够通过改变自己状态改变 $u$ 的状态，$cl_u$ 有多少个必输点儿子，$sa_u$ 所有儿子的 $c$ 之和，$sl_u$ 所有必输点儿子的 $c$ 之和。（2026-3-6）

• P14637 NOIP 2025 T3 tree\ 给一棵树，给每个点定一个值，求所有子树的 mex 值之和的最大值。n\le 8000,m\le 800\ 性质：父亲的值一定比儿子大，且一个子树 u 的 mex 值必然建立在其中一个儿子 v 上，除了 v 子树以外再选择一些作为垫脚石。这样形成了一个类似树剖的结构。一个点的贡献最优情况下为它到根路径上的最长一段重链的长度。\ 于是设 f_{i,j,k} 表示从上往下搜 i 当前所在重链的长度为 k，从 i 到根路径上最长的一条链的长度为 j 的情况下 i 子树内的最大答案。f_{i,j,k}\leftarrow j+f_{v,\max(j,k+1),k+1}+\sum_{v'\neq v} f_{v',j,1}\ 优化状态，只用保留两种情况而去掉最后一维。记 f_{i,j} 为 i 是链顶时，从 i 到根路径上最长重链长为 j 的答案，g_{i,j} 为 i 为链底的答案。\

  $f_{i,j}\leftarrow \sum_{v} f_{v,j}+j$，\ $f_{i,j}\leftarrow \max_{v\in subtree(i),v\neq i,dis(i,v)=j} g_{v,j+1}+\sum_{p\in path(i,v),p\neq i}j+\sum_{x\in son(fa_p)} f_{x,j}$\ 为什么转移到 $j$？\ 用树状数组维护，区间加，单点查询。\ tag: greedy, dp on tree（2026-3-14）

• P15649 省选 2026 day1 T1 recollector\ 给一棵树，随机重链剖分求所有点到根路径上的轻边数量之和的期望值。随机指若对于 u 的儿子 v，它作为重儿子的概率为 \frac{l_v}{\sum_{i\in son(u)}l_i}，其中 l_i 表示以 i 为顶点的重链长度。\ 求出 f_{u,x} 表示以 u 为顶点的重链长度为 x 的概率，由此问题分为两部分，更新答案和计算 f。对于更新答案，设 g_{i,x,0/1} 表示考虑前 i 个儿子，使重链长度总和为 x，是否已经规定重儿子时对答案的贡献，最终答案加上 \frac{g_{|son(u)|,x,1}}{x}，过程就是个背包 dp。对于计算 f，枚举重儿子，前半部分背包 dp，后半部分反推贡献系数，也就是一个倒过来的背包 dp，算出来若当前占用容量为 x 时给答案贡献时的系数是多少。\ 标签：树上背包 dp（2026-5-2）

  树·概率 dp

• CF1823F Random Walk
  题意：从 s 走到 t，每次随机走到其中一个相邻的点，最后求每个点走的次数的期望值
  思路：给边定方向，u 的每个出边的期望值都相等，可以通过 v 的期望值推出来。如果 u\rightarrow v 在 s\rightarrow t 的路上，则期望是 v 出边期望加一，否则就是 v 出边的期望（2026-1-21）

  树·时间复杂度分析

• CF955F Heaps 注意到如果 k 大于某个点的儿子数量，则这个点的最大深度一定为 1，所以总共的状态数量是 O(n) 级别的，求出来之后再 dsu on tree 维护子树内的最大值（2026-1-8）

  树·树上差分

• CF1680F Lenient Vertex Cover
  题意：把每个点染为黑色或白色，保证每一条边都恰好有一个点是黑的，或者只有一条边两端都是黑的
  思路：即最多删一条边，判断是否能够形成一个二分图。dfs 树上的环一定是一条树上的链加上一个返祖边。如果删的边是返祖边，则必须只存在一个奇环；如果删除一条树边，则这条边不能在偶环上，并且所有奇环都经过它。通过树上差分统计每个边通过的奇环、偶环的个数判断（2026-1-24）

  树·倍增/树链剖分

• CF1843F2 Omsk Metro 可以使用树链剖分或者倍增解决，答案一定在一个区间内（2025-11-24）

• CF1403B Spring Cleaning 维护从一个点到根的路径区反，查询整体的和（2025-12-24）

• CF442D Adam and Tree 暴力向父亲更新，如果无法更新就停止，由于按照重链剖分的方式算出来的答案总和是 O(n log n) 的，所以更新次数也不会超过这个值（2025-12-26）

• CF1486F Pairs of Paths\ 给一棵树和若干条简单路径，求有多少对路径恰好只有一个点相交。\ 一定交于这两条路径中深度较大的 lca。按照深度排序，然后容斥求出对于比当前路径的 lca 深度小的路径，有多少条经过 lca 且不经过 u\rightarrow v 路径中 lca 前后的两个点 x 和 y 的路径。树剖维护。\ trick 1: 用树剖求一个点到它的一个祖先路径上，祖先的儿子。\ trick 2: 维护经过 lca 和 x 的路径个数的时候，把每个路径去掉 lca 后加到树状数组里，统计的时候查询 x。（2026-2-28）

• 6.2.1.2 染色\ 路径赋值，求路径颜色段数量\ 套路，注意合并的方向和顺序。（2026-2-3）

• 6.2.1.4 决战\ 路径加/求和/求最大/求最小/翻转\ 每个重链以深度为键值维护一个平衡树。翻转操作需要把所有重链全抠出来，合并，拆分，放回去。（2026-2-4）

• Q6.2.4.2 遥远的国度\ 题意：在一棵树上，进行换根、路径赋值和求子树内最小值的操作。\ 思路：树链剖分，而换根的话，若 x 是 rt 的祖先，则查询整体扣掉 x 的对应儿子的答案；否则正常查 x 的子树。\ 标签：树链剖分（2026-2-13）

  树·重链剖分性质的利用

• 6.2.1.5 能量波动\ 路径加，求一个点的邻居中的第 k 大\ 每个点建一个平衡树维护它的轻儿子们，统计答案的时候再把重儿子和自身考虑进去。这样路径加的时候，只会修改到链顶父亲的平衡树，保证时间复杂度。（2026-2-4）

• 6.2.1.6 路径期望权值/CF1254D Tree Queries\ 选择一个点 r，随机选择一个 u，对于所有的 v 使得 u\rightarrow v 经过 r，把 v 的值加 d；查询一个点的期望值\ 也就是把 r 看成根，它的一个儿子 u 子树内一个点增加 d 的概率为 \frac{n-siz_u}{n}。所以先求出每个点的重儿子，修改的时候只改父亲所在子树和重儿子所在子树。统计答案的时候，对于一个点，它的儿子和旁系都已经给它贡献了答案，唯一需要考虑的是它的直系祖先中不把它当做重儿子子树里的点的祖先，这样的祖先一定是轻边的顶，是 \log n 量级的。（2026-2-4）

• CF2206D Christmas Tree Un-decoration\ 给一棵树， 一次操作可以把 1\rightarrow u 路上的所有不等于零的点权值减去 1，求至少多少次操作可以把所有点都变成零。有单点修改操作。\ 正常 dp 为 f_{u}=\max(a_u,\sum_{v\in son(u)}f_v)。设 b_u 表示 u 的所有轻儿子的 dp 值之和，原方程变为 f_{u}=\max(a_u,b_u+f_{hson(u)})。这样对于一条重链而言（假设 c_1 是链顶，c_t 是链底），f_{c_1}=\max_{i=1}^t(a_{c_i}+\sum_{j=1}^{i-1}b_{c_j})。由于只询问 f_1，所以可以对每个点都维护 a_{c_i}+\sum_{j=1}^{i-1}b_{c_j}。更新操作只会改变链顶父亲的 b 和修改的点 x 的 a_x。（2026-5-15）

  树·LCT

• Q6.2.2.4 三叉神经树\ 给一棵三叉树，末端每个点输入三个值，每个点会把儿子里的众数传给父亲，给几次修改操作和查询根的输出的操作\ 以把零改为一为例，修改到一个点，只有这个点儿子中恰好有一个一的时候才会把修改传递给父亲。所以需要知道一个点的祖先中深度最大的非一的点。修改操作会把从起点到这个点之间（不含这个点）的点都改为二，然后另外修改这个点。可以用 LCT 或者树剖写。（2026-2-6）

  树·dsu on tree

• CF600E Lomsat Gelral 基本就是板子，注意删除操作为枚举子树内每个点（2025-12-6）

• CF1009F Dominant Indices 维护深度为 i 的点的数量，好像也可以用长链剖分做（2025-12-17）

  树·点分治

• CF1575E Eye-Pleasing City Park Tour
  题意：对于所有的 u 和 v，满足 u\le v 且它们之间的路径上的颜色由不超过 k+1 段构成（每一段都是相同颜色），则将它们之间路径的点权之和加到答案里
  思路：点分治，计算通过一个点 u 的路径，先枚举它的儿子 v，每次先计算答案，然后再把 v 子树内的点都扔到树状数组里，保证路径一定经过 u（2026-1-24）

  树·树上莫队

• CF852I Dating 基本就是板子，不带修改（2025-12-13）

  树·Prufer 序列/矩阵树定理

• CF917D Stranger Tree 容斥变为求至少，然后考虑一种连通块划分方式所对应的答案是 n^k\prod a_i，这个可以使用矩阵树定理或者 prufer 序列证明，然后转化为背包求树上划分连通块并在每个连通块中选一个点的方案数量（2026-1-7）

• CF1762E Tree Sum\ 求 n 个点构成的所有形态的树中 1\rightarrow n 路径和之和，这些树需要满足每个边权值为 1 或 -1，且每个点相连的边中都有奇数个是 -1\ 奇数个点的树一定没有一种形态满足要求。每一种树的形态正好有一种给边赋值的方式。去掉一条边权为 1 的边之后，两个连通块大小都为偶数。然后枚举 1\rightarrow n 路径上的一条边，把它断开，1 和 n 在两个连通块中，枚举 1 所在连通块大小，然后利用 n 个点所组成的不同形态的树的个数为 n^{n-2} 得到答案为 \sum_{i=1}^{n-1}(-1)^i\binom{n-2}{i-1} i^{i-2}(n-i)^{n-i-2}\cdot i(n-i)。（2026-2-25）

  树·最小生成树与重构树

• CF1023F Mobile Phone Network 先把我要添加的的选上，然后选择最小的几个已知权值的边补齐生成树，然后对于每个多余的边都是一条路径上的限制，用树剖维护即可（2026-1-10）

• CF1416D Graph and Queries
  题意：删除一条边，或者找到与 u 联通的权值最大的点并将它赋成 0
  思路：给每条边赋一个权值表示它被删除的时间，把它的重构树搞出来。然后倍增求出每个时刻可以选择的子树的根，用线段树维护区间叶子节点的最大权值（2026-1-20）

• CF1981E Turtle and Intersected Segments\ 题意：给一些区间和一个序列 a，如果两个区间 i 和 j 相交，则在 i 和 j 两个点之间连接一条大小为 |a_i-a_j| 的边，求最小生成树的权值和。\ 思路：如果有三个区间 x，y 和 z，使得它们两两相交，则可以把三个点之间边权最大的边删掉，（证明参考求 MST 的过程），也就是说一个区间只用跟与它重叠的且权值距离它最近的两个区间连边。所以用类似扫描线的思路，从左到右扫区间，每加入一个区间找它权值的前驱和后继连边，然后再跑 MST。\ 标签：MST、优化建边、扫描线、区间覆盖（2026-3-17）

• CF1408G Clusterization Counting\ 题意：给一个完全图，每条边有一个互不相同的编号，对于所有的 k\in[1,n] 求有多少种将 n 个点划分为 k 个集合的方案数，使每个集合组成的完全子图内所有边的编号都比这个集合内的点与其他点连边的编号小。n\le 1500\ 思路：处理出所有可能的连通块，然后再选择一部分覆盖所有点，因为连通块互不影响。在求 MST 的过程中，如果一个连通块组成了一个完全图，则这个连通块满足条件。在重构树 dfs，连通块就是若干个区间，然后 dp。\ 标签：MST、重构树、dp（2026-4-10）

  树·dfs 树

• CF2025F Choose Your Queries\ 题意：q 次询问，每次你可以从 x 和 y 中选择一个，将 a_x 或者 a_y 加 1 或减 1，使最终得到的数的总和最小，但需要每一步操作之后所有的数都非负。\ 思路：给 x 和 y 连边，一次操作是给 x 或者 y 取反。如果先给所有 x 都取反一遍，则转化为给一条边连接的两个点同时取反。在 dfs 时的树上，贪心地使儿子都变为 0 这样可以取到最小值，即只有一个连通块内第一个搜到的点可能不能变成 0。\ 标签：建图、转化操作、贪心（2026-3-30）

• CF1519E Off by One\ 题意：给若干个点，求一种两两配对的方法使匹配的对数最多。两个点可以匹配只有当两个点的 (x+1,y) 或 (x,y+1) 在同一条穿过原点的直线上。\ 思路：每个点可以选择向上平移还是向右平移，所以给两种选择建点连边，即求图上边的最多匹配对数，两条边能匹配只有当它们有公共点的时候。每个大小为 k 的连通块答案为 \lfloor\frac{k}{2}\rfloor，方案是在 dfs 树上从下往上填，返祖边归祖先处理。\ 标签：建图、dfs 树（2026-4-10）

  树·虚树

• CF613D Kingdom and its Cities\ 给一棵树，q 次询问，问一些对于一些关键点，至少需要删除树上多少个非关键点可以使这些关键点互不相连。\ 可以贪心，注意到只与这些点和它们的 lca 有关，建出虚树优化。（2026-5-10）

  树·Trie tree

• CF566A Matching Names 放到 Trie 树上，然后从深度大到深度小的点枚举，每次贪心地从子树里选一个名字和一个化名匹配（2025-12-4）

• CF2041I Auto Complete Trie 树上每个点维护一个 set 以及答案（2025-11-21）

  树·AC 自动机

• CF1437G Death DBMS
  题意：给 n 个名字，支持修改一个名字的可疑值和查询一个字符串的所有子串的最大可疑值
  思路：相当于在 fail 树上修改一个点的值，以及查询一个点到根的链上的值的和，可以树剖。注意名字可能会重复，所以给每个点开一个 multiset。（2026-2-21）

• P2292 L 语言\ 题意：给一个字典，一些字符串，求每个字符串最长的能被若干个单词首位相接拼凑成的前缀是多长。\ 思路：设 f_i 表示长度为 i 的前缀能否被拼凑，需要枚举一个字符串 s，从 f_{i-|s|} 转移，考虑放到 AC 自动机上，但是需要用状压优化，即处理出一个点在 fail 树上从根到它的路径上哪些点是在词典中存在的，设这个东西为 g_u，在查询时维护一个 x 表示从 i 往前跳 j 位是否 f_{i-j}=1，则若 x\&g_u，f_i 就是可以的。\ 标签：AC 自动机，dp，位运算（2026-3-24）

  最短路

• CF1163F Indecisive Taxi Fee\ 询问若干次，在原图的基础上修改一条边后求 1 到 n 最短路。\ 若修改的边不在原图上，那么就是原本最短路或者含修改的这条边的最短路，可以从起点、终点分别跑一遍算；否则是不含这条边的最短路或在原本最短路基础上修改这条边。若只修改一条边，则新的最短路中不为原本最短路中的边一定正好是中间一段。因此用线段树更新后单点查询不包含一条边时的最短路。（2026-5-12）

  环

• CF9E Interesting graph and Apples 记录度数，使用并查集判断是否正好是一个环，拼凑必要条件

• CF1325E Ehab's REAL Number Theory Problem\ 题意：给一个序列，保证每个数的因子个数不超过 7，求至少选取多少个数乘起来才能是个平方数。\ 思路：也就是质因子个数不超过两个。考虑把两个质因子连边，如果只有一个就与 1 连边，找最小环。用 bfs 找最小环，而起点只用枚举小于 \sqrt{\max a_i} 的，因为一条边必定有一个端点小于这个数。\ 标签：建图、因子、最小环、bfs（2026-4-12）

  欧拉路径

• CF36E Two Paths\ 题意：给一个图，求完全覆盖它的两条路径。\ 思路：就是求两条欧拉路径，同样需要判联通性和度数的奇偶，另外如果正好有四个点是奇数度数的话，选择其中两个连起来，跑欧拉路，然后再断开即可。\ 标签：欧拉路，以退为进（2026-3-22）

• CF547D Mike and Fish\ 给 n 个点，每个染成红色或蓝色，使得每行、每列的红蓝只差不超过 1。\ 把点变成连接行列的边，即二分图上给边定向使每个点入度和出度之差不超过 1。把奇数度数的点连向 0，跑欧拉路。（2026-5-11）

  哈密顿路

• CF1514E Baby Ehab's Hyper Apartment\ 题意：求一个竞赛图（定向的完全图）中所有的 (a,b) 中 a 是否能到达 b。有两种询问方式，第一种询问 a 与 b 之间的边的方向（不超过 9n 次），第二种询问一个点和一个集合，回答这个点有没有通向这个集合中的点的边（不超过 2n 次）。\ 思路：竞赛图中存在一条哈密顿路，而给竞赛图缩点之后一定是这条路径上的连续的一段缩成一个点。先通过归并求出这条路径，合并的时候比较两条路的起点，假如是 a\rightarrow b，就把 a 放到 b 的前面。然后对于路上的点求出它通过返祖边能到达的最靠前的点是什么，这个是具有单调性的，由此就能知道 a 是否能通往 b 了。\ 标签：图论，哈密顿路，缩点，交互（2026-3-27）

  联通性·dsu

• CF870E Points, Lines and Ready-made Titles 将一个坐标的 x 轴和 y 轴坐标连边，答案取决于连通块大小，但如果是一棵树还要减去都选的情况（2025-12-9）

• P14980 Cow Traversals G
  对于一个基环树森林，一次操作可以将一个点染成三种颜色中的一种，操作后分别对每种颜色求有多少个点第一次走到的颜色就是这个颜色。
  用并查集维护几个连通块。倒着做，因为合并比拆分简单，如果去除一个点的颜色就相当于将它与它的父亲合并（2026-1-20）

  联通性·缩点

• CF22E Scheme 缩点，然后会形成一个森林，并且叶子节点只有一个，把每个图的所有根连在一起，然后用森林中每个图首位相连，标记连通块根的时候只需要搜一遍就行，思路与记忆化搜索相似

• CF652E Pursuit For Artifacts 因为每个边只能走一遍，所以考虑边双，缩点之后求路径上是否有 1 或者路径上的点是否有 1（2025-12-7）

  联通性·圆方树

• CF1045C Hyperspace Highways 建圆方树，每个点双里的点的距离都在 1 以内，发现建完之后两个点原本的距离就是圆方树上的距离的一半（2025-12-18）

• CF487E Tourists\ 给一个图，有点权，询问两个点之间所有路径点权最小值，单点修改。\ 对于点双内的两个点，和点双内的另一个点，前两个点之间一定有一条路径经过后者，因此建圆方树，方点权值为点双内的最小值，用树剖维护。由于有修改，在每个方点用 multiset 维护其儿子的点权最小值即可，类似树链剖分的分治思路。（2026-5-9）

  广义串并联图

• CF2164F1 Chain Prefix Rank (Easy Version)\ 给一棵树以及每个点的祖先中有多少个比它权值小的点，求权值的排列数量\ 可以建出一个 DAG 表示点的大小关系，因为一个排列与一个前缀排名序列是可以相互对应的。然后求 DAG 拓扑排序数量。这个图满足广义串并联图的特点，因为在建 DAG 的时候，在 s 与 v 之间插入点 u 前就一定存在 s\rightarrow t。然后建一个源点一个汇点，把 DAG 上的点一一删除、合并的过程中维护一条边的答案数量和点的数量。（2026-3-3）

  2-SAT

• CF1657F Words on Tree\ 给一棵树和若干个描述，每个描述表示一条路径上的点正着读或者倒着读是这个字符串，求一种分配字符的方式满足所有描述\ 对于一个描述是正着还是反着建两个点，一个点是否是某个字母也建两个点，然后写 2-SAT。建两个点表示整个东西的正确与否。如果正反某一位都相等，那么让正确节点连向它取这个值，它不取这个值连向错误节点，最终需要从正确节点无法通向错误节点。另外还需要处理一个点只能取一种值。（2026-3-5）

  网络流

• CF1473F Strange Set\ 题意：给两个序列 a 和 b，求一个集合 S\in\{1,2,\cdots,n\}，满足对于任意 i，所有满足 j\in[1,i)，且 a_j|a_i 的 j 也必须在集合中，求 \sum_{i\in S}b_i 的最大值。n\le 3000,a_i\le 200\ 思路：从 i 向 j 连边，即求最大价值闭合图。设一个源点 s，一个汇点 t，原图的边的容量设为 +\infin。对于 b_i>0 的 i，连接 s\rightarrow i，边权 b_i；否则连接 i\rightarrow t，边权 -b_i。然后求 \sum_{i\in S,b_i>0}b_i 减去最大流即最小割。\ 标签：网络流，最大价值闭合图（2026-3-30）

• CF1082G Petya and Graph\ 题意：给一个图，求它的子图内边权减点权的值之和的最大值。\ 思路：考虑用最小割求，先在答案里记上所有边的权值和，题意转化为不选一个点有 a_i 的代价，一条边如果有至少一个点不选就有 w 的代价，所以从源点连到边再连到对应的两个点再连到汇点，用答案减去最小割。\ 标签：最小割（2026-4-27）

• CF808F Card Game\ 题意：给 n 个三元组 (p,c,l)，选取一个子集满足 \sum p\ge k，且任意两个的 c 之和不是质数，求 l 的最大值最小可以是多少。\ 思路：二分 l 求 \sum p 的最大值，在互质的两个之间连边，即求最大圈独立集。注意到大部分质数是奇数，所以两个数一定是一奇一偶才能和是质数，所以是个二分图，只要把一半与源点相连，一半与汇点相连，中间边权为正无穷，求总权值减最小割。\ 标签：最小割、二分图（2026-4-27）

• CF1264E Beautiful League\ 题意：给一个完全图，其中一些边已经定向，要给剩下的边定向使三元环数量最多。n\le 50\ 思路：三元环的数量是任选三个点的方案减去不是三元环的个数，不是三元环等价于一个点出度为 2。所以答案是 \frac{n(n-1)(n-2)}{6}-\sum_{i=1}^n \binom{du_i}{2}。建一个源点 s、汇点 t，对任意一条边 u\rightarrow v，建一个点 x 表示这条边，连 s\rightarrow x、x\rightarrow u、x\rightarrow v，这些边都流量为 1，费用为 0，表示一条边可以选择给 u 或 v 的度数加一；对任意点 u，连 u\rightarrow t，共连 n-1 条，第 i 条代价为 i-1，这是对组合数的贡献做了差分，也就是如果多增加一次 u 的度数答案会增加 i。跑最小费用最大流。\ 标签：竞赛图、环、最小费用最大流（2026-4-13）

• CF311E Biologist\ 题意：一个长度为 n 的 01 串，可以花 w_i 的代价修改 i 位置的值。有 m 条要求，如果所有在这个集合内的位置都是 0 或 1，则可以获得 v_i，求能获得的最大值。\ 思路：源点连为 0 的点，为 1 的点连汇点。源点连 0 要求，然后连对应的那些点；1 要求连汇点，对应的点连到 1 要求。用总 v 减去最小割。\ 标签：最小割（2026-4-28）

• CF724E Goods Transportation\ 题意：有 n 个点，可以生产 s_i 的东西，售卖最多 p_i 的东西，若 i\le j 则可以从 i 向 j 运输 c 的东西，求总售卖数最大是多少。n\le 10^4\ 思路：源点连每个点，容量为 p_i，每个点连汇点，容量为 s_i，点之间连容量为 c 的边，求最大流。即求最小割，假设与 s 相通的点的集合为 A，剩下的为 B，则答案为 \sum_{i\in A}s_i+\sum_{i\in B}p_i+\sum_{i\in A,j\in B}c，可以 dp 实现。\ 标签：最大流、最小割、dp（2026-4-29）

• P1251 餐巾计划问题\ 每天需要 r_i 个餐巾，可以选择花 p 买新的，花 f 并用 m 天的时间洗餐巾，也可以先把脏的餐巾囤着。求最小花费。\ 为了区分干净和脏的餐巾，把一天拆成两个部分，早上使用餐巾，晚上处理餐巾，s\rightarrow i_2(r_i,0)，i_1\rightarrow t(r_i,0) 表示餐巾（1 是早上），s\rightarrow i_1(+\infin,p) 表示买餐巾，i_2\rightarrow (i+1)_2(+\infin,0) 表示囤着，i_2\rightarrow (i+j)_1(+\infin,f) 表示洗，跑最小费用最大流。（2026-4-30）

• CF802A3 Heidi and Library(hard)\ 第 i 天需要第 a_i 种图书，可以选择花 c_{a_i} 的钱买或者用图书馆里原有的，而图书馆最多放 k 本书，求最小花费。\ 同样一天拆成两个点，先所有的都买，考虑如何处理保留的部分。在相邻两天之间连 i_0\rightarrow(i+1)_0(k-1,0) 表示留着，i-1\rightarrow pre(i)(1,-c_{a_i}) 表示撤回一次购买，s\rightarrow i(1,c_{a_i}) 表示初始全部购买。跑最小费用最大流。（2026-5-1）

• P2765 魔术球问题\ 给 n 个柱子，求最多按顺序放多少个球，使得每对相邻的球编号之和都是完全平方数。\ 拆点，一个与 s 相连，如果有流就代表另起一个柱子；一个与 t 相连，如果有流就代表是一个柱子中的最后一个；中间对于 i<j,i+j 是完全平方数，则把 i 的第二个点连向 j 第一个点，跑最大流。（2026-5-7）

• P3355骑士共存问题\ 棋盘上有一些障碍，求最多能同时放多少个马。\ 棋盘黑白染色，不能共存的一对一定颜色不同，即为二分图求最大独立集。（2026-5-8）

  二分图

• CF Privatization\ 题意：有个二分图，共 t 种颜色，给每个边染色，求最终每个点的连边中出现最多的颜色的出现次数减去最少的这个值最小是多少。\ 思路：结论是可以取到最小。给每个点的连边按照 t 的大小分成一块一块的，每一块内颜色不重复，然后跑二分图边染色。\ 标签：二分图（2026-4-28）

  前缀和与差分

• CF1906B Button Pressing 前缀异或，相当于冒泡排序。如果一的数量相等，或者可以通过操作第一个整体取反之后数量相等即可（2025-12-29）

• CF1285E Delete a Segment 差分，离散化的时候把下标乘二处理退化成点的情况。

• CF1592F1 Alice and Recoloring 1\ 题意：给一个初始白色的网格，每次操作可以花费 1/2/3/4 的代价，把一个包含左上/左下/右下/右上的矩阵内的格子都反转颜色，求最少花多大的代价可以把网格变成想要的样子。n\le 500\ 思路：代价为 2 和 4 的操作没有意义，因为可以用两次操作 1 来代替。考虑网格的差分网格，(x,y) 为 1 表示把它左上角的所有网格都反转一次，这样发现操作一就是把 (x,y) 反转，操作三就是把 (n,m)、(x-1,m)、(n,y-1) 和 (x-1,y-1) 反转，发现操作三最多进行一次，因为可以用六次操作一代替两次反转。\ 标签：诈骗、差分、黑白格子（2026-3-20）

• Q6.2.5.2 这是我自己的发明\ 题意：给一个树，树有点权，进行换根和查询 \sum_{i\in subtree(x)}\sum_{j\in subtree(y)}[a_i=a_j] 操作。\ 思路：分别把换根后两个子树所对应的若干个区间求出来，两两配对求。而区间也可以通过这种方式转化为若干个形如 [1,i] 与 [1,j] 匹配的问题。通过普通莫队求解。\ 标签：差分、莫队（2026-2-15）

• CF671C Ultimate Weirdness of an Array\ 题意：给一个序列，求 \sum_{i\le j }f(a_1,a_2\cdots ,a_{i-1},a_{j+1},\cdots,a_{n-1},a_n)，其中 f(A)=\max_{i<j}\gcd(A_i,A_j)。\ 思路：枚举最大公因数，用线段树维护每个左端点对应的最大右端点使得抠掉 [l,r] 之后的 f\ge d，发现只要知道这种数的前两次出现位置和后两次出现位置，然后区间取 \max，而由于具有单调性，所以只需要线段树上二分然后赋值。最后再差分就是答案。\ 标签：差分、线段树上二分（2026-4-29）

• CF1101G (Zero XOR Subset)-less\ 给一个序列，求最多划分成多少段能够使得选取这些段中的一些，它们的异或和都不为 0。\ 即一段的异或和就是两个前缀和的异或，原问题等价为最多能选多少个本质不同的前缀和，即线性基的大小。（2026-5-4）

  倍增/st表

• at_ndpc_e Summer Vacation\ 维护区间内最多选多少个互补重叠的线段。\ 每次肯定贪心跳最近的右端点，维护从 \ge i 的位置出发跳 2^j 次最近能跳到哪儿，倍增。（2026-5-6）

  线段树

• CF817F MEX Queries 离散化之后维护区间是否是单一的颜色,支持区间赋值和区间反转（2025-12-11）

• CF1439C Greedy Shopping 线段树二分（2025-12-12）

• CF338E Optimize!\ 题意：给两个序列 a 和 b，其中 a 长度比 b 短，求从 b 中截取长度与 a 相等的一段区间，有多少种取法可以使这两个区间经过排列之后对应位置之和都大于等于 h。\ 思路：把 b 每个位置变成 h-b_i，变为 a_i\ge b_i 的条件。也就是在值域上，前缀和一直不小于零。所以在值域线段树上维护前缀和，求最小值。\ 标签：线段树、转化（2026-4-7）

  可持久化线段树

• CF1957F1 Frequency Mismatch (Easy Version)\ 给一棵树，有点权，查询两条路径是否每种点权的出现次数都相同，如果不同，输出一个出现次数不同的点权\ 以点为时间轴，主席树第 u 层代表 1\rightarrow u 路径上的所有点的权值线段树。考虑找到最小的出现次数不同的点权，需要在主席树上二分，权值线段树中维护的是每种点权出现次数的哈希值。可以给每种点权随机一个权值，哈希值即没增加一个点权的出现次数就把它的权值加上。计算路径的答案可以把路径拆成点到根路径答案的和/差。（2026-3-3）

• CF173E Camping Groups\ 题意：给两个序列 r 和 a，一次询问两个下标 x 和 y，求包含 x 和 y 的最大集合大小使得集合中的一个 i 满足 a_i 是最大值且所有其他的 j 都满足 |a_i-a_j|\le k。\ 思路：对于每个数，可以处理出它作为最大值时的集合最大大小。剩下的只需要满足 |a_x-a_p|\le k，|a_y-a_p|\le k 且 r_p\ge r_x,r_y。所以按照 r 作为时间轴，a 作为值域建主席树，然后维护区间最大值。\ 标签：可持久化线段树（2026-3-31）

  势能线段树

• Q6.1.3.2 区间整除
  支持区间加、区间整除，查询区间最小值和区间和
  设一个区间的势能为其最大值减最小值，即 max-min，一次操作后至少会将每个数减半，变为 \lfloor\frac{max}{2}\rfloor-\lfloor\frac{min}{2}\rfloor。因此若区间内的数都在 [0,1] 内则不操作，若除完后全相等则操作，否则递归。但由于 max-min=1 时可能势能不变，因此还需特判。（2026-1-26）

  李超线段树

• Q6.2.4.1 游戏\ 题意：在一棵树上，修改操作为给一条路径向一个一次函数取最小值，查询一条路径的最小值。\ 思路：树链剖分，再套一个李超线段树。\ 标签：树链剖分、李超线段树（2026-2-14）

• CF631E Product Sum\ 题意：进行一次移动一个元素的操作，使序列 a 的 \sum_{i=1}^n a_i*i 最大。\ 思路：考虑答案的变化量，求一下前缀和并分类讨论一下，发现如果把 i 移动到 j 的前面，答案增加 a_i\times j-s_{j-1}+s_{i-1}-a_{i}\times i，表示为一次函数用李超线段树维护。\ 标签：李超线段树（2026-4-16）

  猫树

• Q6.2.3.1 好吃的题目\ 有 n 个商店，每个商店有个热量值和美味度，查询在一个区间内的商店，热量值不超过 c 时的最大美味度\ 求出每个区间被划分的 mid，按照它的深度将区间排序，一层一层处理，从 mid 处开始向两侧 dp，然后把前后缀拼接求区间的答案。（2026-2-6）

  笛卡尔树

• P11261 Histogram 放到笛卡尔树上，枚举每个点，考虑跨过这个点的区间，使用启发式合并的思想，枚举较小的一边选几个，剩下的部分可以预处理前缀和（但好像可以直接组合数算，不用启发式合并）（2025-12-5）

• P6453 PERIODNI 把直方图放到笛卡尔树上，树上背包 dp 求答案（2025-12-6）

• P1377 tree 使用笛卡尔树优化建二叉搜索树（2025-12-5）

• CF1508B Mathematics Curriculum
  求有多少个长度为 n 的排列，满足有恰好 k 个数满足包含它的子区间的最大值恰好有 m 种取值
  转换为笛卡尔树上深度为 m 的点恰好有 k 个，求树的形态数量，设 f_{i,j,l} 表示长度为 i，深度为 j 的点正好有 l 个的排列数量，枚举最大值位置转移，注意到笛卡尔树一个大小为 x 的子树每一层不超过 \lceil\frac{x}{2}\rceil 个点，可以优化（2026-1-21）

• P2611 小蓝的好友
  在一个网格中，有一些格子里有点，求有多少个矩阵包含至少一个点
  正难则反，求有多少个矩阵不包含任何一个点。枚举矩阵下边界，其实就是求一个直方图里的矩阵数量。由于笛卡尔树是一种 treap，可以维护插入和区间修改的操作（2026-1-30）

• at_arc212_e Drop Min\ 题意：给一个排列，一次操作选择相邻两个数，将较小的拿出来放在新的排列后面，求最终得到的排列一共有多少种。\ 思路：在笛卡尔树上，一个点必须要满足其左儿子的子树或者其右儿子的子树中的点全部删除之后才能被删掉。然而还取决于左右是否有比它大的数，分类讨论然后组合数算。\ 标签：笛卡尔树、组合计数（2026-4-1）

  平衡树

• CF38G Queue 维护一个按照位置排序的 treap，每次分裂之后插进去，除此以外还需要维护区间最大值和个数（2025-11-21）

  扫描线

• UVA1608 non-boring sequences 对于每种数来说，满足条件的是若干个区间，这些区间的左右端点分别有个区间限制，只要有一种数满足条件即可，所以把 l、r 当成 x、y 轴，扫描线求矩阵面积并

• P1856 矩阵周长 扫描线模板，注意同层先加后减

• CF258E Little Elephant and Tree 把修改看成矩阵，矩阵内每个点表示其横坐标和纵坐标是相关联的，然后对于每一个横坐标求纵坐标非零的有多少个就是答案（2025-12-27）

  分治

• CF848C Goodbye Souvenir 求满足 t_{ask}<t_{query}，id_{ask}\le r_{query} 且 pre_{ask}\ge l_{query} 的所有 id-pre 的和，即求三维偏序，离线下来用 cdq 分治求（2025-12-10）

• E6.1.5.2 平面最近点对
  求平面最近点对
  把点按照 x 排序，按照 x 分治。处理到当前区间时，按照 y 排序，如果一个点离分界线的距离已经大于等于当前答案则肯定不行，这样的话对于左边的一个点最多枚举右边六个点，有时间复杂度保障。注意分界线要在递归前记录，否则按照 y 排序之后中点处的 x 坐标会变（2026-2-2）

• CF2203F Binary Search with One Swap\ 求一个 1 到 n 的序列，有多少对 (i,j) 使得交换 i,j 后的序列进行二分仍然能够找到的数恰好有 k 个，对于 k\in [0,n] 都求出来。\ 建出二叉树，若 i,j 不是祖先关系，则有 siz_{rs_x}+siz_{ls_y}+2(i<j) 个，也就是 i 和 j 子树中且在 [i,j] 范围内的数的个数。否则有 |i-j| 个。小结论：二分过程中线段长度的种类数是 \log n 级别的。（2026-5-15）

  整体二分

• Q6.1.5.4 异或运算
  给两个序列 x 和 y，A_{i,j}=x_i~\mathrm{xor}~y_j，求一个矩阵内第 k 大
  在 trie 树上二分，枚举第一维，把询问按照 x 拆分；将第二维的数，即 y 加到 trie 树上（需要可持久化）。然后就是在当前的点，统计 x_i~\mathrm{xor}~y_j 中小于当前的点的数量，然后分别递归。（2026-2-2）

  线段树分治

• Q6.1.6.2 时空旅行
  题意：有一棵树，一个点所包含的星球为在其父亲所包含的星球的基础上增加/删除一个星球。星球具有坐标和权值连个属性。给你一个点的编号和一个坐标，询问在这个点上，距离再加上权值最小是多少。
  思路：用线段树维护树的 dfs 序，一个点肯定存在于一个区间内。(X-x_i)^2+c_i=X^2+x_i^2+c_i-2Xx_i=ans，\therefore x_i^2+c_i+X^2=2Xx_i+ans，可以斜率优化，在线段树的点上维护凸包。（2026-2-3）

• CF1217F Forced Online Queries Problem\ 给一棵树，m 次操作，每次可以改变一条边的存在状态或者求两个点是否在同一连通块内，通过每次加上上次的答案后取模强制在线\ 上一次的答案只可能是 0/1。对于每条边用分界点把时间轴拆成几个区间都挂在线段树上。初始时所有区间都是没有作用的，得到一个时刻的答案之后把它与后面紧挨着的一次询问之间的修改操作修改的边状态取反。到线段树的一个点的时候把上面所有状态为存在的边加上，别的不管。（2026-3-2）

  根号分治

• CF1990E2 Catch the Mole(Hard version)
  树上的一个点有地鼠，每次你可以猜一个点，然后告诉你地鼠是否是以它为根的子树里，如果猜错了，地鼠会向根走一步，否则不动
  在一个叶子节点猜 x 次，这样对于地鼠跑到的点 u，u 的子树的深度一定大于等于 x。然后 dfs 一遍，每次查询都保证可以去除一个深度为 x 以上的子树，最终得到一条链，然后再在链上二分（2026-1-23）

• CF2006D Iris and Adjacent Products\ 题意：给一个序列，每次询问一个区间内的数至少修改多少个可以经过重新排列后得到一个序列 a，使得任意相邻两项的乘积不超过 k。\ 思路：一个序列 a，先排序，按照 a_n,a_1,a_{n-1},a_2\cdots 的顺序排列相邻两项的乘积最小。于是要求等效于 \forall i\le \sqrt{k}，cnt(1,i)\ge cnt(\frac{k}{i},k)（两者都需向 \lfloor\frac{n}{2}\rfloor 取 \min，因为要求 a_i 是在排序后的序列的前半部分）。所以把 \le \sqrt k 的数与 >\sqrt k 的数（可以存到 \lfloor\frac{k}{i}\rfloor 里）分开存储，离线，先枚举 i，这样好处理前缀和，另每个询问的答案同这一种数所需修改次数求最大值。\ 标签：贪心、根号分治、前缀和（2026-3-24）

• CF2173F Isla's Memory Thresholds\ 题意：给一个单调不增的序列，进行若干次询问，从 l 开始每次选择从左边开始的一个区间，恰好和不小于 k，并把这个区间删除，求 [l,r] 操作多少次，剩下的和为多少。\ 思路：暴力的思路是每次二分删除的长度，显然长度单调不降。但是如果长度过短就不行，所以小于 B 的长度进行枚举，二分这个长度的区间有多少个；否则二分一次操作删除的长度为多少。\ 标签：二分、根号分治（2026-4-8）

• P10040 替换\ 题意：给一个 01 串，其中某些位置为 ?，对于所有 k\in [1,n]，求出通过一下方法递推得到的字符串中 1 的个数：若 s_i 不为 ?，则为 s_{i-k}，否则为 s_i。\ 思路：对于每个 k，进行 \frac{n}{k} 次 bitset 的左移取或操作，时间为 \frac{n^2\ln n}{\omega}，但对于 k 较小的情况复杂度过大，所以按照 \sqrt{n} 分治，小于的就暴力算，最多只有 \sqrt n 个。\ 标签：bitset、数论、根号分治（2026-4-20）

  莫队

• CF940F Machine Learning\ 题意：若干次询问区间内 c 的 mex，其中 c_i 表示 i 的出现次数。\ 思路：带修改莫队。没什么特殊的。\ 标签：带修莫队（2026-4-7）

• Q6.2.5.3 最长值域连续段\ 题意：给一个排列，询问区间最长值域连续段长度。\ 思路：普通莫队，修改用值域线段树上求最长连续段维护。\ 标签：莫队、线段树（2026-2-20）

• Q6.2.5.4 作业/P4396 作业\ 题意：给一个序列，询问若干次，每次询问一个区间 [l,r] 内且值在区间 [a,b] 内的数的个数以及值的种类数。\ 思路：普通莫队，再把值域分块，这样一次修改是 O(1)，查询 O(n)。\ 标签：莫队、分块（2026-4-12）

  颜色段均摊

• CF896C Willem, Chtholly and Seniorious
  区间加/赋值，求区间第 x 小或 (\sum_{i=l}^r a_i^x)\bmod y，数据随机生成
  对于同一颜色段，第 x 小和 (\sum_{i=l}^r a_i^x)\bmod y 都好求。用 set区间 维护颜色段，然后暴力枚举区间内的颜色段求。（2026-2-8）

• 6.1.6.5 动态区间颜色数/P4690 镜中的昆虫\ 区间赋值，求区间内不同颜色数量\ 一个长度为 n 的数组，进行 m 次区间赋值，pre 数组的修改次数是 O(n+m) 量级的*。通过颜色段均摊可以保证这点，求出所有改变 pre 的操作。然后再 cdq 分治求不同颜色数。（2026-2-10）

• CF269D Maximum Waterfall\ 题意：给 n 个平行于 x 轴的线段，水初始从 y=t 往下流，一个线段 a 能够向 b 流淌水仅当 \max(a_l,b_l)<\min(a_r,b_r),a_h>b_h，且不存在 c 使得 a 和 c 与 c 和 b 也满足这两条。流淌的水的量为 \min(a_r,b_r)-\max(a_l,b_l)，求一条路使得流量最大。\ 思路：从上到下加线段，维护最下面的一层颜色段，判断是否有中间的只需要判 a 左右两端的两个线段即可。\ 标签：颜色段均摊（2026-4-2）

  随机化

• P8819 星战 首先只要满足每个点出度为 1 则一定满足每个点都能走到一个环上。出度不好修改，考虑入度，给每个点随机化一个权值，如果出度都为 1 则所有点的权值和等于所有点父亲的权值和，因为是随机的，所以可以把必要条件当充分条件使。（2025-10-27）

• P10102 矩阵 随机一个 1\times n 的矩阵 D，如果 D\times A\times B=D\times C，则有 \frac{1}{mod} 的概率 A\times B\neq C，因为 \sum_{i=1}^k (w_{1,i}-w_{2,i})c_i 在模意义下跟一个数相等的概率为 \frac{1}{mod}，注意 c 在 [0,mod-1] 内，此时每次选择的 c 都是对于上一次算出来的值是唯一的。（2025-10-27）

• CF1746F Kazaee 如果能够整除，那么和一定整除，所以给每个数赋一个权值，再把个数求和，如果能够整除就认为每一种数都能整除。（2025-10-27）

• P4581 想法 因为 E(\min_{i=1}^n x_i)=\frac{1}{n+1}，其中 x 是在 [0,1] 中随机取数。证明不会……所以给每个叶子节点随机一个点权，然后求出每个点的多次随机平均值，推出它能到达的叶子结点个数。（2025-10-27）

  卡常

• CF1045J Moonwalk Challenge 数组第一维是先枚举的，这样更快。

2025-10-11

• HDU-7858 洞察* 将式子转化为枚举一个小于 v 的数，使得 r\oplus c\mod k=b，然后数位 dp

• P3204 公交线路* 设 f_{i,s} 表示考虑前 i 个车站，最后进的 p 个中哪些是某条线路当前的最后一站的情况下的方案数

• P13977 数列分块入门 2 每个块内维护一个单调的序列，如果是散块就暴力重新排序，以此来支持区间查小于某个数的数的个数

• P9921 染色 求在表格中防两根一样长的棍儿，最长能多长，有的格子不能放。分类讨论是两个都横着、竖着还是丁字形，注意不同不一定是丁字，丁字不一定相交。

• POJ C24A 游走 显然要尽量把最大值和最小值放在一块，接下来每加入一个点都会更优，然而不能全都并到一起，所以最极端情况下是留着左下角或者右上角，把这两种情况取最优的。——单调性、退一步

• P9361 orz 贪心，显然可以求出每一步能到的排名最大值，然后倍增求解。

• P4824 sencoring 类似 KMP，需要用栈维护剩下的东西，再记录一下每个 i 指针对应匹配的 j 辅助。

• Best Subsequence 使用 set，每次删除最大的那个对中的最大的数字；也可以二分，check 的时候先把 \le \frac{x}{2} 的都选上，然后再判断两两之间能不能再插入一个。

• Mex Subsequence 把序列划分成多个字段，每一段的 mex 跟整体的 mex 相等

• 2025-10-2 mns T1 优先选对着的，其他的贪心地选

• 2025-10-2 mns T2 环一定不优，暴搜莫名其妙能过

• 2025-10-3 mns T3 连续段 dp

• mns T2 差分 2025-10-22

• T4 考虑每次修改正好修改没有修改过的，使用哈希加二分，还需要使用树状数组维护前缀哈希值，单点修改（外加卡常）。

• P2261 余数求和 数论分块，按照 \lfloor\frac{k}{i}\rfloor 相同的分成一块。

  • 注意右端点取值可能会大于 n，需要特判。

• CF11E 01 分数规划，二分答案，然后把式子变形，把 mid 搞到式子左边，然后 dp。

  • 注意浮点数二分不能直接判等于。

• P5633 最小度限制生成树 查看标签 大力观察发现满足凸性，使用 wqs 二分，然后给每个与 s 相连的边加上一个权值，贪心地选最小生成树。

  • 判断 impossible 的情况，把斜率取到最大和最小值分别跑完之后跟 k 比较
  • 斜率相同的时候需要选最小的（根据你二分的时候的情况）

    5 6 1 3
    1 2 2
    1 4 5
    1 5 5
    1 3 2
    3 5 4
    2 4 4

    三点共线的时候直接取到了 (4,14)，所以二分就什么都没有搜到。

• P11899 必胜 博弈，首先优先抢质数，接下来是优先把奇数质因子的数变成偶数，接下来比分数的多少，多的可以把偶数的数推给对方。只有全是质数并且是偶数个的时候才可能平局。

• P11900 不知道 考虑每个猫不死掉的概率，因为它一直往前走，只要每次经过可能被摸的格子都不被摸就行。最后一个猫可以不用考虑它后面的猫都要被摸的限制，这样化简一下式子。至于前面的猫只需要算出概率再乘上后面的猫都不被摸的概率，注意不要算重。

• P11645 Warmth of the Eternity 因为一条边连接的两个联通块一定是和为 n，所以只要确定联通块如何两两匹配就行，组合计数。

• P12137 装修报价 考虑先进行异或操作再进行加减，异或构成了多个区间，而区间前面取加还是减对于和来说正好抵消，所以只要求第一段的就行。

• CF1228E Another Filling the Grid 二维容斥，但是可以优化，只要考虑至少有多少行最小值不是 1，在此基础上保证每一列最小值都是 1。

• P4859 已经没有什么好害怕的了 容斥，因为 dp 的时候不好考虑恰好，把条件转为至少，然后如果这一个数选择满足条件就转移，不满足的话也不用特意使这一位不满足，只要随便就行。

• P9357 Lighthouse 把贡献拆成一个点在另一个点操作的时候给它的贡献，这个东西只跟路径长度有关，然后再枚举当时的权值以及路径上进行了几次操作，组合计数。

• P4587 神秘数 从小到大加数，如果当前加的数在 [1,l]，构成的数的区间为 [1,r]，那么如果新加的数在 [1,r+1] 则满足条件，每次加一个值域里（注意不要重复加），加到不能再加就是答案，用主席树维护区间中值域在某个区间里的数的和。

• P4559 列队 发现相对顺序不变一定不劣。在主席树上随便乱搞。

• CF730I 反悔贪心，先选 b ，选完之后决定每次新选一个 a，还是将一个 b 换成 a 再找个新的 b。

• CF1515E computer 最终电脑会形成若干连续段，中间用自动开的隔开。连续段 dp 的时候不用考虑合并的问题。

• U1168 稻草人 分治，整体按照 x 排序，区间内左右分别按照 y 从大到小排序。条件拆成左右两部分，枚举在左半边的点，右边需要维护一个向右下方倾斜的曲线，并且不能有点在 i 与 mid 之间并且比左边的点低，所以左边需要维护一个右上倾斜的曲线，查询的时候需要用左边的点右边的第一个比它高的点的高度。

• P3197 越狱 整体减不合法，合法的为第一位随便选，其他的位置都有 m-1 种选择。（2025-10-28）

• P4931 情侣 原理跟错排问题差不多，中间需要乘上一些系数。（2025-10-28）

  一篇题解的证明

• CF1870E Another Mex Problem 转移的时候从极短的 mex 区间转移最优，预处理出来这些区间。

• CF433D threegood从从大到小排序，如果选更优就选。（2025-10-28）

• P1462 通往奥格瑞玛的道路 二分答案，check 的时候跑最短路，如果某个点不能走就不跑，如果血量够就可以。（2025-10-28）

• P3396 哈希冲突 根号分治。如果模数较小可以提前预处理，较大则可以暴力枚举。（2025-10-26）

• CF797E Array Query 根号分治。如果 k 较大可以暴力算，较小可以 dp（2025-10-26）

• CF1039D You are given a tree 如果 k 较小可以直接贪心地从叶子结点选，较大可以二分一个答案的左右端点，因为满足单调性，而答案不大。（2025-10-26）

• P1989 无向图三元环计数 根号分治，转换成 DAG，暴力枚举一个点，枚举它的儿子，再枚举它的孙子，如果可以就是三元环。对于一条边，如果两个点度数不同就从小往大连，如果相同就按编号从小到大/从大到小连。因为按照这样的顺序所以不可能成环，三元环就一定变为一个点是另外两个的父亲。时间复杂度是 O(m\sqrt{m})，因为如果 v 的度数小于 \sqrt{m}，则满足；若大于，则其儿子的出度大于它，而图总共的度数是 O(m) 的，所以儿子也最多有 \sqrt{m} 量级的。（2025-10-26）

• CF837D zero 背包 dp，f[i][j][l] 表示前 i 个数选了 j 个，其中含 l 个 5 时最多含多少个 2。(2025-10-28)

• P6880 奥运公交 分类讨论改的边是否在原来的最短路上，如果不在的话可以 O(1) 计算修改后的答案，如果在的话就暴力地把边改过来，然后跑最短路，因为最短路图上的边数是 O(n) 的。

• P5590 赛车游戏 考虑 1 到 n 路径上的点，然后差分约束，dis_u-dis_v\le 9 且 dis_v-dis_u\le -1 然后使用 SPFA（2025-10-27）

  • 特判 1 不能到 n

• P7074 方格取数 横向没有后效性，设计状态为第 i 列到第 i+1 列从第 j 行转移的情况下最大的贡献，使用前缀和优化转移。（2025-11-4）

• U1170 小 Q 的方格纸 花哨的前缀和，需要记一个梯形的前缀和，稍微容斥一下。（2025-11-4）

• at_agc017_d game on tree 树上的 nim 游戏，涉及到一些理论知识（2025-11-6）

• P6475 建设城市 排列组合，枚举指定相等的两个的高度（2025-11-7）

• at_agc026_d Histogram Coloring 相邻两列要么全部取反，要么全部相同，但必须是全部交错的时候，所以状态里设置一位表示从下往上有多少个是连续交错的，需要离散化（2025-11-8）

• P14462 寻宝游戏 感性认为优先选择大的作为最终放泡面的地方，但是有一堆特判和调整，再套上一个线段树（2025-11-10）

• CF1982E Number of k-good Arrays 数位 dp 加上小白逛公园的思想（2025-11-10）

• CF1989E Distance to Different dp，考虑到两个一和一个二的情况有重复，可以强制不选二，因为选择一分的区间数更多更容易满足条件（2025-11-10）

• CF1995D Cases 相邻两个选的字母距离不超过 k，即每 k 个字母中都出现一个是选过的，所以选的字符的集合与每组相邻 k 个字母组成的不可重集都有交集，即求不是任意一组的补集的子集的集合最小的大小（2025-11-10）

• CF42D Strange Town 将边的条件转化为点的条件，发现如果边权是两个点的点权和可以使得任意回路的路径和一定，然后加点的时候尽量使得点权最小即可（2025-11-11）

• CF97B Superset 平面点的分治，在中点加点，涵盖左右所有的纵坐标（2025-11-11）

• CF1858E2 Rollback "假删"，也就是删除操作并不真的删除，只是把结尾的指针往前移动，这样撤销的时候好操作，另外维护 set 记录每个数的出现位置，以及树状数组维护前缀答案（2025-11-11）

• CF2057E1 Another Exercise on Graphs 二分答案，大于这个值的边赋成一，否则为零，需要满足最段路长度大于等于 k，优化在于每改变一条边更新当且仅当这两个点的距离不是零（2025-11-11）

• CF1621E New School 贪心不好使用数据结构优化，所以考虑它们的值，对于任意值，大于等于它的学生组数一定小于等于老师个数则满足条件，使用权值线段树维护（2025-11-12）

• CF1738E Balance Addicts 左右相等的区间会把原来的数组分成一段一段的，可以选择划分开或者不划分，但是还需要处理零的情况（2025-11-12）

• CF1425D Danger of Mad Snakes 整体减空白，可以求出包含某个蛇的方案数，将平方拆开，两个蛇的那一项枚举两条蛇，两条蛇容斥一下求答案（2025-11-12）

• CF141E Clearing Up 反悔贪心，先选一种，再填另一种，然后再新加一些第二种边把第一种边替换掉（2025-11-13）

• CF44I Toys 类似格雷码的思路，首先转换为考虑每个东西所属的堆的编号组成的数组，最终的答案需要满足相邻的两个只有一位不同，所以每一段要求首尾为 0 或 1，镜像后拼接。（2025-11-13）

• CF1914G2 Light Bulbs 可以分为若干段使得每一段都可以自己解决自己的问题，所以每一段只需要选一个就可以，把每个颜色向区间内的颜色连边，缩点后没有入度的点都可以作为选择的颜色，使用线段树优化（2025-11-14）

• QOJ4632 Card Shark 一个字符串可以看成一条边，代表它的第一个零的位置连向下一个字符串第一个零开头的位置，然后跑欧拉回路（2025-11-15）

• CF1917D Yet Another Inversion Problem 每 k 个分一段，算完块内的逆序对个数之后就可以不考虑块内的顺序了，模拟归并排序的过程，发现将两个块合并的时候一定是交错排列，枚举交错开的位数，在 log_n 量级。（2025-11-16）

• CF36D New Game With a Chess Piece 博弈，平衡点是两个循环，一个循环正好区反，注意特判 k=1（2025-11-17）

• CF167C Wizards and Numbers 两种操作可以分别转化为 b-\lfloor \frac{a}{b}\rfloor a 和 b-a^{k-1}\cdot a，首先如果第一种操作后必败则一定必胜，否则可以转化问题为选 \lfloor \frac{a}{b}\rfloor 个石子，可以一次选 a^k 个，而在模 x+1 的意义下，x^k 为 1 或 x，这样找到了平衡点（2025-11-17）

• CF1929F Sasha and the Wedding Binary Search Tree 根据二叉搜索树将节点按照点权排序，然后排列组合（2025-11-17）

• CF660E Different Subsets For All Tuples 钦定子序列选最靠前的，枚举子序列的长度考虑它的贡献，发现还需要枚举最后一个元素的出现位置，推式子利用二项式定理（2025-11-18）