绝顶之战
首先这是一道判定题而不是计数。我们首先枚举一个放进去的子集 \(S\) 和没放进去的子集 \(T\)，做 \(dp\) 判定它是否能合法。
判定合法问题我们往往要猜的是合法取值是连续的，然后转为求最值问题处理区间，此题也是如此，如果合法区间存在，那么区间下界应该是 \(\sum_{i \in S} a_i\)，上界设为 \(f_S\)，合法区间为 \([\sum_{i \in S}a_i,f_S]\)。
我们考虑 \(S\) 中第一个被放进的元素设为 \(p\)，由于不可越过，它把整个区间分为两半，那么我们枚举一个放到左边的子集和右边的子集，就可以进行转移了，还要考虑 \(T\) 中在 \(p\) 前的元素，那么最终答案还要对这个取 \(\min\)，即 \(\min_{i \in T}a_i-\epsilon\)。
实现细节：注意到所有东西都会带一个 \(\epsilon\)，所以我们直接使用 int 类型存储，实现中相等实际上是小于。
Negative Cost
看起来就不太能贪心，那么我们考虑的就是背包。
维度太多很麻烦，我们考虑 压缩决策，每次加入一个魔力合法的操作序列，为什么不用考虑这些东西之间的魔力影响？我们画出折线图，从下往上考虑，如果能够取出一个子段它最小前缀和为 \(0\) 并且和为 \(0\)，我们就可以拆分，并且可以证明通过调整法重排可以把魔力值时刻控制在 \([0,2C)\) 中，那么序列长度也不会超过 \(2C\)。
这样我们就消去了魔力值的影响，剩下的是简单的，处理体积为 \(C^2\) 的背包，剩下的选性价比最高的。
水题走四方
瞬间移动，并且两个人没有区别，那么一定是一个人一直走路，一个人移动，我们称为 \(1\) 和 \(2\)。
\(1\) 走的一定是一条从根到叶子的链，我们考虑 \(2\) 的走路结构，发现可以在链上选出一些进行瞬移过的点，假设两个是 \(x,y\)，那么 \(1\) 一定在 \(x\) 等待，\(2\) 遍历除了 \(y\) 子树内 \(x\) 子树的所有叶子，最终 \(2\) 走向一个很深的叶子同时 \(1\) 走向 \(y\)。
结构必然是这样，于是我们可以转移枚举上一个关键点了。
\(f_u=\min([mxdep_{anc/u}\ge dep_u]f_{anc}+dis_{anc/u})\)，当不存在这样的点是 \(f_u=f_{fa}+1\)，对应两个点同时向下走一步。
注意到关键的性质是我们一定只会从深度最大的这样的点转移，容易证明，又涉及到深度相关，于是我们长剖，单调栈转移就可以了。
注意 dfs 空间占用极大，不要写。
Jumping sequence
45 度旋转，然后把所有东西全选上，变成 01 背包能否表示问题。
重点在于 物品值域较小，当我们遇到值域较小的问题时，要考虑的是重排，调整，证明循环，控制正负交替保证值域全程在小范围内。
此题需要调整，我们选一个最长的前缀使得 \(p_v\le sum\)，此时 \(sum-p_v\le V\)，并且最终方案一定是左边删一些，右边加一些。
那么此时就有正负交替性了，我们设 \(f_{l,r,a}\) 表示左边考虑到 \(l\)，右边考虑到 \(r\)，能否表示出 \(a\)。
注意到 f 是 01 数组，那么我们遇到这种东西需要考虑的是状态的偏序，设 \(g_{l,a}\) 表示左边考虑到 \(l\)，为 \(a\) 时右边最小是 \(g_{l,a}\)。然而转移复杂度没有变化因为每次需要枚举一个 \(x \ge g_{l,a}\) 转移。
考虑减少无用转移，发现对于 \(x \ge g_{l-1,a}\) 的转移都已经被考虑过了，所以我们只需考虑 \(g_{l,a} \le x \le g_{l-1,a}\) 的 \(x\)，这样就是 \(O(n^2)\) 的了。
Bear and Cavalry
排序完之后最优的是较大的 \(w\) 向较大的 \(h\) 连边，一开始再往类似错排的角度考虑，但是问题在于每个点都不是等价的，所以你不能错排。
限制是很松的，我们不妨考虑最优解离对应匹配实际上是比较近的？
我们注意到两条线相交的话交换一定更优，又有更有趣的是 如果一个匹配为 \((i,j)\)，那么一定至少存在 \(|i-j|\)条跨过它的边。
存在两条以上一定能够交换，所以我们的结论是 \(i\) 的匹配范围一定是 \([i-2,i+2]\)。设 \(f_i\) 为考虑前 \(i\) 匹马和人最大值，分类讨论匹配情况从 \(f_{i-1},f_{i-2},f_{i-3}\) 转移。
ddp，不过因为数据范围松其实可以 \(O(nq)\)。
为什么没想到呢？主要没从限制较松联想到匹配较近，而且思路一直往错排那边跑。
CF1188D
一个自然的思路是枚举最终的值，代价是 \(\sum popcount(s-a_i)\)，但是我们发现这样是减法，一般来说是加法更好做，于是我们排序，设 \(s=a_n+z\)，\(\sum popcount(a_n-a_i+z)\) 最小化这个东西。
考虑每一位填 \(0/1\)，发现还需要考虑上一位是否进位，我们好像只能状态压缩了。
此时我们不应直接放弃思路，应该考虑的是 大部分状态是不是都是无用的？能否削减状态？,发现是可以的，因为在 \(\mod 2^i\) 意义下进位具有单调性，于是我们按这个值排序，进位的是一个前缀，这样我们把状态数从 \(O(2^n)\) 直接降到了 \(O(n)\)。
图
考虑 \(k=\frac{m}{n-1}\) 的意义：\(n-1\) 是生成树边数，并且生成树上两点有路径。
这启发我们把原图的边分成几张生成树图，具体而言是这样：我们依次考虑每条边 \((u,v)\)，对于 \(1\) 到 \(k\) 的图 ，找到第一张 \((u,v)\) 不连通的，把这条边加入，如果这张图是第 \(k\) 张就输出答案。
如果无解，那么说明第 \(k\) 张图没有任何边，容易利用抽屉原理说明这是不可能的。
找到第一张不连通的图这个过程可以二分，于是复杂度 \(O(m \log m)\)。
poor turkeys
第一眼是考虑建边二分图什么的，但是顺序做都是很难做的，我们考虑倒序。
倒序考虑人的决策实际上就很简单了：我们假设现在想要保留 \(i\),那么一个人的决策是 \((i,x)\)，他就要吃掉 \(x\)，换言之 \(x\) 在前面都没有被吃，保留了下来，于是我们维护一个需要保留的集合 \(S\)，如果扫到一个人两个元素都在 \(S\) 中就无解，两个都不在就不管，一个不在就加入。
计算答案很容易说明只有两个集合无交时有解，复杂度 \(O(n^3+nm)\)
balance
好玩图论建模题。
\(S=2^k\) 往分治方向考虑，那么我们先考虑 \(S=2\)。
对于出现次数为奇数的我们可以补一个 \((0,i)\) 把它变为偶数，此时限制强化为两行出现次数相等。
发挥注意力：每种颜色出现次数为偶数，要求相等，答案是欧拉回路。
我们把交换描述为无向边定向（好像在哪见过但是我忘了）跑一条欧拉回路，发现每个点出度入度相等，那么就解决了。
容易扩展分治。
复杂度 \(O(NS \log S)\)。
Black, White and Grey Tree
显然，一个颜色相同的连通块应该在一次被删除，我们合并它们。
这样树上的点就都是异色的了，如果没有灰色的话手玩一下能够发现答案是直径的一半左右，上下界都比较好证明。
但是有灰色！！那么很有趣的一步是注意到灰色点一定是某次与黑色或白色删除的，相当于它是一个黑色或白色点，答案相当于是我们要对灰色染成黑或白色，合并后最小化直径。
看起来可以 dp，实际上很神奇的是如果一个灰色点周围都是同色点就染成同色，否则拆成黑白二色，然后合并求直径，这样就是对的。
容易证明正确性。
Shrinking Tree
场上考虑到了对着与根相关的边形态 dp，但是性质推错了。
枚举每个点作为根，一条边被删除时与根相连当且仅当它到路径上所有边删除时间都比它早（有点废话）。
那么我们设 \(f_{u,k}\) 表示根到 \(u\) 路径上最大值大于子树内前 \(k\) 小的边，子树合并是卷积，然后考虑 \(u\) 向父亲的连边时间。
tree depth p
不知道怎么想到的。
笛卡尔树深度是这样的 \(\sum_{v}[\min([v,u])==a_v]\)。
对于每个 \(u\)，我们枚举每个 \(v\) 考虑它是祖先的贡献，那么经典的我们每次加一个数考虑它的相对排名，先从 \(u\) 向 \(v\) 加入，加入 \(v\) 时相对排名一定是 \(1\)。
复杂度爆飞了，但是我们发现实际上对于 \(u-v\) 相等的 \((u,v)\) 算法流程是一模一样的，于是我们先跑出来总的逆序对方案数，枚举 \(u-v\)，相当于撤销一个物品，撤销完再枚举 \(u\) 贡献。
Mr. Kitayuta's Gift
当然是钦定匹配顺序，因为是回文串，此题我们定义是从两端往中间维护两个指针匹配，原串从两端向中间匹配，通过匹配过程可以说明匹配是唯一的。
那么就可以 \(dp\) 了，定义 \(f_{i,l,r}\) 为长度为 \(i\) ，还有 \([l,r]\) 区间内字符未匹配方案数。
暴力直接矩阵快速幂是 \(O(s^6 \log n)\) 的，考虑画出这个自动机看看，发现除了自环之外它应该是一个 dag，并且路径长度应该比较短，是 \(O(n)\) 的，这启发我们统计路径形态相同的路径数量。
首先定义 \(a\) 点为自环数为 \(24\) 的点，\(b\) 点为自环数为 \(25\) 的点，那么形态相同指的就是经过这些点数量相同的路径。
注意到对于一条从起点到终点的路径，\(b=\frac{n-a}{2}\)，于是我们记录 \(g_{l,r,x}\) 表示当前在 \([l,r]\) 经过了 \(x\) 个 \(a\) 点的路径数，于是我们完成了对路径的统计。
但是还有对插入自环方案的统计！这个就比较完蛋了，我们每次做个矩阵乘法的话大概是个 \(s^5\)。
但是注意到矩阵乘法实际上一次求出的是图内所有起点终点的路径数，因此我们大概做一个这样的图：所有 \(a\) 点连一条链，所有 \(b\) 点连一条链，每个 \(b\) 点下面再挂一个对应的终点，\(a\) 链尾向 \(b\) 链头连边，这样就可以对应求出系数。
Reunion
有两个比较有意思的做法。
1：
首先看到计数最大值我们应该想到的是差分，求小于等于的。
我们定义忙的人是白点，不忙的是黑点。
求 \(\le k\) 的方案数，我们对每个点设 \(d_i\) 为距离它最近的白点，那么要求就是所有 \(d_i \le k\)。
我们实际上可以对着 \(d_i\) 计数！容易证明是双射的，并且 \(d_i\) 有相当良好的性质：
\(0 \le d_i \le n\)，对于每个 \(u\)，若它不为零，则存在一个 \(v\) 满足 \(d_v=d_u-1\)。
于是我们对着 \(d_i\) 计数，优美地解决了问题。
2：
这个做法感觉不太优美，但是比较新。
这题可以对于大于等于计数！！是的 \(\max\) 也可以大于等于。
条件就是存在一个黑点，它领域内全是黑点。
树上领域问题有上面的处理方法，也可以考虑深度。
我们设 \(f_{i,j}\) 为 \(i\) 子树内最浅的点深度为 \(j\) 方案数， \(g_{i,j}\) 为存在一个备选点，这个点子树内合法，子树外暂时合法，最深的备选点深度为 \(j\) 的方案数。
一个重点是 \(f,g\) 是互斥的，它们计数的集合交集为空，这样可以不重不漏，并且此题可以这样做的原因是如果存在一个备选点，那么这个子树内的白点就不会造成影响。
转移是简单的，可以 \(O(n^3)\)，似乎长链剖分可以优化。
Eternal Average
过程相当复杂，我们考虑直接对着可以合法生成的结果计数。
首先一个结果当然是形如 \(\frac{1}{k^i}\) 和 \(\frac{0}{k^i}\)。
结论是一个结果能被生成的充要条件是 \(\sum \frac{1}{k^i}=1\)。
必要性：我们观察操作过程，初始设所有数次数都是 \(0\) 即为全 \(1\)，然后每次是选 \(k\) 个加起来再除，发现除完新增的数还是 \(1\)，如此我们证明了必要性。
充分性：发现必要性了应该尝试证明它是充分的，其实也很简单，我们取最大的 \(i\)，设为 \(B\)，那么 \(\sum k^{B-i}=k^B\)，除了指数为 \(B\) 的数外其他都是 \(k\) 的倍数，因此指数为 \(B\) 的数一定有 \(k\) 的倍数个，所以可以进行一次操作，由此归纳证明。
由此我们可以在 \(k\) 进制小数位下 dp 保证唯一生成每个串，注意到一个 \(\frac{1}{k^i}\) 可以变成 \(k\) 个 \(\frac{1}{k^{i+1}}\)，所以只要在 \(\mod k-1\) 下同余就能变换出个数相等的。
这样就做完了。
to make 1
怎么都在说 \(O(3^n\sum)\) 简单啊，不会。
和上面类似的，我们发现对着过程做大概就只能做到 \(O(3^n)\)，直接考虑什么结果能被合法生成。
首先必要的是存在一个序列 \(b_i\) 使得 \(\sum \frac{a_i}{k^{b_i}}=1\)。
找到必要性一定要尝试证明它是否充分，我们发现它是充分的，证明和上面那个类似。
于是问题变成对着这个东西 dp，可以看这个题：Number of Multisets
Density of subarrays
容易发现密度等价于求一个最短的不是它子序列的串。
我们发现每次往最远的那个 \(nxt\) 走就是对的，于是容易写出 \(O(\frac{n^3}{c})\) 的 dp ，每次枚举下一个 nxt，保证中间的区间内除了 \(nxt_i\) 的颜色都出现了一次。
只要复杂度存在除法我们就应该设计另一种算法尝试平衡，容易发现存在 \(O(\frac{n^22^c}{c})\) 的算法，复杂度被平衡到 \(O(\frac{n^3}{\log n})\)。
CF1474F
如果你按序列顺序考虑 lis，那么就全都完了，但是如果按照值域大小顺序考虑那么就全都对了。
很神奇，启发我们 dp 顺序是很重要的，有时候不需要那么多性质，重点在于状态和顺序。
Logical Operations on Tree
很有趣的题。
推性质推错了，启示我们推出性质之后不能做要考虑性质是不是推错了。
做法有两个：
1：注意到把所有 \(and\) 操作先操作必定不劣，那么如果操作完存在一个 \(1\) 就必胜了，于是条件相当于断开所有 \(or\) 边后存在一个全 \(1\) 的连通块。
2：从叶子开始考虑：
如果叶子是 \(or 1\) 那么已经赢了，如果叶子是 \(or 0\) 或者 \(and 1\) 那么没有影响，如果叶子是 \(and 0\) 那么推迟操作它一定不优，所以直接操作，这样剥叶子计数。
线段树
\(\max \min\) 问题要枚举转 \(01\)，然后对于每个 \(0\) 连续段我们拿出来做 dp，设 \(f_{l,r,t}\) 表示在时刻 \(t\) 区间 \([l,r]\) 是一个极长的 \(0\) 连续段的方案数，复杂度是 \(O(n^3q)\)，但是是随机数据，分析一下发现是期望 \(O(n^2q)\) 的。
实际上也有确定性做法，我们发现每次 dp 只有初始值不一样，过程是线性变换并且是一样的，这种东西可以推贡献系数或者把所有初值加到一起，整体做一次 dp，对于此题，我们原来每次做 dp 初始值是 \(f_{l,r}=1\) ，最后是 \([l,r]\) 区间加 \(a_{i+1}-a_{i}\)，那么我们把初值改成 \(a_{i+1}-a_{i}\) ，所有初始值加在一起做一次 dp 就可以了。
类似题目有 10879
9月8日：