-
CF1413C
转化题意，对于每一个 \(i\)，找到一个 \(j\)，求 \(b_i-a_j\) 的极差。
考虑把 \(6n\) 个 \(b_i-a_j\) 算出来，排序，枚举起点，找到能把 \(n\) 个旋律凑齐的最靠前的终点，用终点的权值减去起点的权值，取最小值就可以了。
这个东西的正确性很显然，因为你可以不选择重复的旋律，实现可以用双指针，至于怎么想到的……，拜谢 HR。
-
CF1554C
找到 \(k\ge m+1\)，求 \(k \oplus n\) 的最小值。
然后做经典的 \(2^n>2^{n-1}+2^{n-2}+\dots+2+1\)，即若 \(m+1\) 当前这位为 \(1\)，那么 \(k\) 只能取 \(1\)，否则就应该和 \(n\) 的当前这位相同，若 \(n\) 的当前这位为 \(1\)，那么 \(k\) 取 \(1\)，于是 \(k\) 无论后边取什么都会有 \(k\ge m+1\)，就可以不用看 \(m\)，随着 \(n\) 取即可。
-
CF1525E
虽然很经典，但是我没有做过，学到了不少东西。
考虑到 “期望的和等于和的期望”，把每个点拆开，分别计算其能被征服的期望，最后加和。
设当前枚举的点为 \(j\)，\(t\) 时刻在 \(i\) 城市建造建筑物，那么该建筑物的影响力为 \(n-t+1\)，它能影响到点 \(j\) 当且仅当 \(n-t+1\ge d_{i,j}\)，即 \(t\le n+1-d_{i,j}\)，记 \(n+1-d_{i,j}\) 为 \(L_i\)。
那么能被征服条件变为了存在一个城市 \(i\) 的 \(t\le L_i\)，这样很难做，正难则反，计算不能被征服的期望，即对于所有 \(i\)，\(t>L_i\)。
对 \(L_i\) 从大到小排序，第一个城市的取值有 \(n-L_1\) 种可能，第二个城市的取值有 \(n-L_2-1\) 种可能，因为城市一占用了城市二的一个地方（\(L_1>L_2\)），由此可得，第 \(i\) 个城市的取值有 \(n-L_i-(i-1)\) 种可能。乘法原理可得，乘起来就是全部方案。
最后用 \(n!\) 减去不合法方案数再除以 \(n!\) 就是点可以被征服的期望了。
-
CF1630D
根据裴蜀定理，最短的可操作区间长度为 \(\gcd(b_1,b_2,\dots,b_m)=g\)。
然后具有一个很奇妙的状态设计：\(f_{x,0/1}\) 表示当前对 \(i \bmod g=x\) 的所有 \(i\)，操作偶数/奇数次。
状态转移显然，由于一次操作必然会使对 \(g\) 取模结果为 \(0,1,\dots,g-1\) 的数各操作一次，所以答案为 \(\max(\sum\limits _{i=0}^{g-1} f_{i,0},\sum\limits _{i=0}^{g-1} f_{i,1})\)。
-
P7987
性质一：存在答案使得每组配对的区间互不相交。
证明：若 \(a<b<c<d\)，且答案为 \((a,d),(b,c)\)，则可以将答案调整为 \((a,b),(c,d)\)，且该调整一定能够满足配对限制。
性质二：满足性质一的答案中，\(i\) 只能与 \(i-1,i-2,i+1,i+2\) 配对。
证明：假设 \(i\) 与 \(i-3\) 配对，则 \(i-1\) 和 \(i-2\) 必然也可以配对，与极大匹配矛盾，原命题得证。
设 \(f_{i,0/1}\) 表示前 \(i\) 头牛，叉掉了 偶数/奇数头牛的最小重量和。
这样的方案合法当且仅当叉掉的牛之间的距离 \(>k\)，且剩下的牛之间的距离 \(\le k\)，那么最好就是相邻的牛配对才更有可能满足条件。
设 \(last\) 表示最后一头牛与 \(i\) 牛的距离 \(>k\) 的编号。
-
如果前 \(i\) 头牛选了偶数头牛，则必然可以两两配对。
-
若这头牛不选，那么就可以转移 \(f_{i,i \bmod2}=f_{last,1-i\bmod2}+y_i\);
-
若这头牛选，转移为 \(f_{i,i\bmod2}=f_{i-1,i\bmod2}\)。
-
-
如果前 \(i\) 头牛选了奇数头牛，则必然可以剩下一头牛没有配对。
-
若这头牛不选，则下一头牛必须与上一头牛距离小于 \(k\)，那么就可以转移 \(f_{i,1-i \bmod2}=f_{last,i\bmod2}+y_i\);
-
若这头牛选，则必须与下一头牛距离小于 \(k\)，转移为 \(f_{i,1-i\bmod2}=f_{i-1,1-i\bmod2}\)。
-
Q：这个 \(f_{i,i\bmod2}=f_{i-1,i\bmod2}\)，你怎么知道 \(f_{i-1,i\bmod 2}\) 时，哪头牛被选了呢？
A：注意到 \(f_{i-1,i\bmod2}\) 相当于 \(f_{i-1,1-(i-1)\bmod 2}\)，发现其取值只能来源于 \(i-1\) 与 \(i\) 配对，\(i-2\) 与 \(i\) 配对两种情况，那么当且仅当的其配对距离不超过限制时才会转移，所以体现在 \(f_{i-1,i\bmod2}\) 都是能与 \(i\) 配对的代价。
-
-
ARC219E
连通矩阵构造技巧：把矩阵转化为蛇形或环形，化二维为一维，降低构造难度。
回到本题，转化为环后，发现必然在环上有一段区间满足题目要求，直接枚举起点，使用前缀和优化即可。
-
CF1307D
把最短路径表示成 \(dist_{1,x}+dist_{x,n}\) 的形式。
若连接 \(x,y\)，则经过 \(x,y\) 的最短路径长度为 \(dist_{1,x}+1+dist_{y,n}\)。
显然连接一条边后最短路径变短，所以做差 \(dist_{1,x}+dist_{x,n}-dist_{1,x}-1-dist_{y,n}=dist_{x,n}-dist_{y,n}-1\)，目标即为使差值更小。
那么直接对 \(dist_{x,n}\) 排序，取相邻两个点连边求最短路即可。
-
ARC170C
刻画 \(\operatorname{mex}\) 形式的好题。
若 \(m\ge n\)，则 \(s_i=1\) 有一种方式，否则有 \(m\) 种方式，因为 \(\operatorname{mex}\) 无论如何都不会超过 \(m\)，乘法原理可得每个位置的方案相乘即为答案。
考虑将 \(\operatorname{mex}\) 转化为填方格问题。
注意有 \(m+1\) 个方格。
设 \(f_{i,j}\) 表示前 \(i\) 个数，填了 \(j\) 个格子的方案数。
- 当 \(s_i=1\) 时，\(f_{i,j}=f_{i-1,j-1}\)，相当于强制填了一个格子。
- 否则，\(f_{i,j}=f_{i,j}\times j+f_{i-1,j-1}\times (m-j+1)\)。
答案为：\(\sum\limits_{i=1}^{m+1} f_{n,i}\)。
-
CF1253E
注意到，\(k\) 最优取值为 \(\sum a_i\) 的质因子，因为 \(k\) 的数量很少，所以直接枚举 \(k\)。
发扬人类的智慧，把 \(a_i \bmod k =0\) 转化为 \(s_i \bmod k=0\)，\(s\) 为 \(a\) 的前缀和。
根据均分纸牌的原理，每个位置只向右侧借糖果，那么假设 \(a_i\) 向 \(a_i+1\) 借了 \(x\) 个糖果，\(x\) 可以为负，\(s_i\) 变成 \(s_i+x\)，\(s_{i+1}\) 不变。
那么因为前面 \(i-1\) 个盒子都符合标准，所以 \(s_i \equiv a_i \pmod k\)，把 \(a_i\) 变成 \(k\) 的倍数最小步骤为 \(\min(a_i\bmod k,k-a_i\bmod k)\)。综上所述，答案为 \(\sum\limits_{i=1}^n \min(s_i\bmod k,k-s_i\bmod k)\)。
-
CF1286B
构造好题。
首先 \(size_i\le c_i\) 时显然无解，其他情况有解，因为无论子树长什么样子，其根节点总能有一个值使其满足题意。
如何构造呢？注意到答案一定可以写成一个长度为 \(n\) 的排列。那么这个位置应该填当前没填过数的排名第 \(c_x+1\) 的数。
-
CF1288D
想到二分，想到从 \(m\) 入手，但是没有想到位运算啊啊啊。
在 check 函数中，若 \(a_{i,j}\ge x\)，则 \(val_i\) 的第 \(j\) 位为一，否则为零。
注意到若 \(val_i \operatorname{or} val_j=2^m-1\)，则 \(x\) 合法，暴力枚举 \(val_i,val_j\) 的取值即可。
时间复杂度：\(O(2^{2m}\log V+n)\)。
做题笔记 Ⅰ
