D1.md

D1.T1 AtCoder - agc018_d

题意：

$N$ 个点的树，第 $i$ 条边连接 $A_i$ 和 $B_i$，边权为 $C_i$。由这棵树建一张图 $G$，图 $G$ 中任意两个点都有边相连，且边权为树上这两点间简单路径长度。求图 $G$ 的最长哈密尔顿路径。$N\le 1e5$。

题解：

事实上这类的树的问题，通常可以往树的直径 / 重心的角度去考虑。

当我们要求的是哈密顿回路的时候，我们可以从重心出发，在两颗子树中横跳，使得每条边的经过次数达到上限 $sze_x\cdot(n-sze_x)$。但是这回我们要求的是哈密顿路径，那么从重心相连的一条边中最短的删掉；如果有两个重心，那么一定要删掉它们之间的那条边。

有一个改版：如果是最短路径，那么就是 $2\times\sum C_i - l$，$l$ 是直径长度。

时空：$O(n)$。评测记录：AC Submission。

D1.T2 AtCoder - agc041_d

题意：

构造一个值域为 $[1,N]$，长度为 $N$ 的单调不降序列 $A$。并且使得 $\forall 1\leq k\leq N-1$，都有任意 $k$ 个数之和小于任意 $k+1$ 个数之和。求构造方案数，对 $M$ 取模。$N\le 5000$。

题解：

上面这个条件等价于前一半的数小于等于后一半的数，因为 $k>\frac{n}{2}$ 时可以消掉一些，成为 $k<\frac{n}{2}$ 的情况；对于 $k<\frac{n}{2}$ 的时候，显然只要最大的那一组成立，根据单调性，其他的也都成立了。

对于单调的数列，我们考虑差分。设 $d$ 为 $A$ 的差分数组，于是有 $\sum\limits_{i=1}^nd_i\le n$；还有的限制——不妨设 $n=5$，那么得： $$ d_1\times 3 + d_2\times 2 + d_3 > d_1\times 2+d_2\times 2 + d_3\times 2 + d_4\times 2 + d_5 $$ 移项： $$ n-d_2-d_3-d_4-d_5 \le d_1 + 1 \le d_3+2\cdot d_4+d_5 $$ 所以对于 fixed $d$，$d_1$ 有右减左种取值，这个就可以 背包 统计了。复杂度：$O(n^2)$。

D1.T3 AtCoder - agc024_f

题意：

给定一堆 ( $\le 1e6$）长度小于等于 $20$ 的 01数组，再询问一堆 ( $\le 1e6$）长度小于等于 $20$ 的 01数组 在模式串中是多少个串的子序列（不需要连续）。

题解：

假设只有一个模式串和一个询问，那么我们可以结合子序列自动机设一个傻傻的 DP：设 $f_{i,j}=1$ 表示前 $i$ 能匹配到第 $j$ 位......

假设只有一个询问，但是有多个模式串，那么我们考虑把 DP 中的 $j$ 改成一个状压 $S$ 的位表示模式串还剩下什么，就能一起转移了——转移中要使用子序列自动机，这要能保证唯一和最优。

假设有多个询问和多个模式，也就是原题：那么我们把 $i$ 和 $j$ 都改成状压就行了。

复杂度：$O(n\cdot 2^n)$，评测链接：TLE Submission (被卡常)。