Darth Vader and Tree *2200

首先考虑暴力。

设 $f_i$ 表示距离根距离恰好为 $i$ 的数量。转移为

$$f_i=\sum_{j=1}^n f_{i-d_j}$$

但观察数据范围，发现 $d_i\le 100$，说明不同的 $d_i$ 很少。

那么只需要对这些不同的 $d_i$ 转移就行了。

设 $num_i=\sum_{j=1}^n [d_j=i]$，那么转移为

$$f_i=\sum_{j=1}^V num_j\times f_{i-j}$$

这是一个常系数齐次线性递推方程，BM算法矩阵快速幂即可。

最终答案为 $\sum_{i=1}^x f_i$，可以在矩阵里顺便维护一下。

复杂度 $O(V^3\log x)$

Vladik and cards *2200

容易想到状压。

但第一个条件感觉很难搞，没法记录每个元素出现次数，怎么办？

我们可以二分出所有的数字的最小出现次数 $mid$，那么每个元素出现次数只能为 $mid$ 和 $mid+1$（经常在错解里想到这种思路，终于在这道题成为正解了）。

设 $f_{i,S}$ 表示到第 $i$ 个位置，数字出现状态为 $S$ 时，出现次数为 $mid+1$ 的数的最大个数。

这么设状态是因为，一个数的出现次数只能为 $mid$ 和 $mid+1$，那肯定让 $mid+1$ 的个数越多越好。

转移比较简单，看每个数字出现 $mid$ 次还是 $mid+1$ 次即可。

我们可以把每个数字出现的位置记录下来，方便转移。

注意每种数字必须连续，也就是出现过后就不能再转移了。

复杂度 $O(2^Vn\log n)$

Treeland Tour *2200

树上路径问题直接考虑点分治。

设当前分治重心为 $rt$，我们求出从叶子往 $rt$ 走且以 $i$ 结尾的 LIS 和 LDS。

这个东西怎么求呢？

每个点都只能从子树转移来，所以问题就是单点加子树查，弄个 dfn 序后线段树维护即可。

统计答案时，考虑包不包含 $rt$。

设 $up_i$ 表示以 $i$ 结尾的 LIS 长度， $down_i$ 表示以 $i$ 结尾的 LDS 长度。

对 $up_i$ 和 $down_i$ 分别做前缀 $max$ 和后缀 $max$。

包含 $rt$：$ans=\max up_{a_{rt}-1}+down_{a_{rt}+1}+1$

不包含 $rt$：$ans=\max up_i+down_{i+1}$

然后完了？

显然没有，因为如果两条路径来自同一颗子树内就寄了。

那么线段树在维护时，记录最大值和次大值，以及来自哪棵子树即可。

统计答案时特判一下。

复杂度 $O(n\log^2 n)$

Felicity’s Big Secret Revealed *2200

简单性质题。

不难发现答案 $x$ 不会很大。因为 $n\le 75$，所以 $x\le 20$。

那就考虑状压，设 $f_{i,S}$ 表示这一刀切在 $i$ 前，状态为 $S$ 时的方案数。

转移就枚举上一刀切在哪。

转移为

$$f_{i,S}=\sum f_{j,S/T}$$

把 $[j,i-1]$ 组成的数去掉即可。

答案为 $\sum f_{i,2^j-1}$

复杂度 $O(n2^V)$

Abbreviation *2200

唐唐唐，下次读题能不能读仔细点。

做了半个小时+看了半天题解才发现翻译里最后一句写着“至多进行一次操作”

绷不住了。

那就好做了。枚举缩哪一段区间即可。

具体的，我们可以先处理出 $f_{i,j}$ 表示 $i$ 和 $j$ 向后匹配的最长长度。

然后枚举缩哪段区间，然后向后暴力缩就行了。

复杂度 $O(n^3+n|\sum s_i|)$

代码可参考官方题解。

Three Pieces *2200

很厉害的一道题，完全没想出来。

考虑 dp。

设 $f_{i,j,k,0/1/2}$ 表示当前在 $(i,j)$，已经填了 $1\sim k$，且当前是 0/1/2 棋子的最小花费。

但这个 dp 有一个问题：不知道转移顺序。

所以考虑用最短路转移。

转移分三种：

1. 换棋子，代价为 inf+1
2. 移动棋子，代价为 inf
3. 填数（即 $(i,j)$ 所在的数是下一个数），代价为 0

这里有一个 trick：因为还要求换的次数最小，所以可以设一个极大值，将移动棋子设为 inf，换棋子设为 inf+1，这样就可以做到双关键字了。

输出答案时，时间就是 $ans/inf$，换的次数就是 $ans\%inf$。

一共 $O(n^4)$ 个点，$O(n^5)$ 条边。