杂题
DP
Abandoning Roads
看到 \(n \leq 70\) , 想一下朴素状压
设 \(f_{S,u}\) ，\(S\) 表示处理完的连通块状态 ， \(u\) 表示当前的节点
因为只有两种边权，所以可以双队列求最短路，所以我们有了一个天然的 \(O(2^n m)\) 的做法
无法通过捏
\(m\)肯定没办法省略了
那我们考虑减少 \(2^n\) 这个东西
怎么办。状态不好减，就只能转移减了
从小到大的转移肯定不能省略，但小局面可以省略！
发现，如果一个连通块小于 \(4\) 个点，那么一定是用边权小的连，不然就不满足 \(\text{MST}\) 的兴致了
复杂度 \(O(2^{\frac{n}{4}}m)\) , 拿下
T395568 魔法
题意可以转化为一个连通块内是否存在绝对众数，考虑树形DP。
自己做的时候设计了一个 \(f_{u,0/1}\) 的方程，但最后可以发现不好处理子树所选择的连通块大小
数据范围 \(1 \leq c \leq n \leq 3000\)
因此我们可以遍历每一种种族，并且对每一个节点进行赋值，若节点为当前种族，则为\(1\),否则为\(0\)
若 \(\sum_{t \in (D)} > 0\) 那么当前种族在当前连通块就是绝对众数
那么就可以设计一个 \(f_{i,j}\) 表示带有 \(i\) 节点含有\(j\)个节点的连通块，然后我们做树上背包
P2465 [SDOI2008] 山贼集团
看到数据范围 \(1 \le p \le 12 \text{且} 1\le t\le 2^p\) 可以想到状压
那么状压需要将一个集合压缩为一个二进制数
我们可以发现，额外收益或损失，是生来就应该状压的！
设 $\text{dp状态为} f_{u,s} $ 表示以 \(u\) 为根的子树中我们放置的部门形成的状态
然后做一下树上背包就可以做完了
我竟然新学到怎么枚举子集
// 枚举 j 的子集
for(int k = j ; k ; k = (k-1) & j)
// do something
[APIO2014] 序列分割
要记住，DP优化基本都是在原来的DP式子上优化的
这个题，首先要发现切的顺序没有影响，于是可以直接dp
朴素一点的式子
\(f_{i,j}\) 表示在前 \(i\) 个里面切了 \(j\) 刀 。
\[f_{i,j} = \max{f_{j,k-1} + s_j (s_i - s_j)} (0 \leq j < i ) \]时空复杂度 \(O(n^2)\) 空间显然可以直接滚动优化掉。
考虑优化转移
发现存在决策单调性，就是有一种决策一定更优
记 \(f_{i,j}\) 为 \(f_i\), \(f_{j,k-1}\) 为 \(g_j\)
任取 \(j,k\) 满足 \(0\leq k \le j \le i\) , \(j\) 优于 \(k\) , 有下面式子
\[g_j + s_j(s_i-s_j) \geq g_k + s_k(s_i-s_k) \frac{(g_j-s_j^2)-(g_k-s_k^2)}{s_k-s_j} \leq s_i \]发现满足下凸壳
维护一下，做完了
[ICPC2022 Jinan R] DFS Order 2
主要知识点是回滚背包，第一次见
设 \(f_u\) 为 \(f\) 节点为根的子树的总方案数，那么有
\[f_u = son_u ! \times \prod_{v\in son} f_v ; \]设 \(ans_{u,i}\) 表示 \(i\) 在 dfs 序中位置为 \(i\) 的答案，\(g_{j-i}\) 表示 \(v\) 与 \(u\) 差 \(j-i\) 的方案数， 那么有
\[ans_{v,j} = \sum ans_{u,i} \times g_{j-i} (v \in son_u) \]考虑怎么转移 \(g\)
设 \(dp_{i,j}\) 表示在 \(u\) 的儿子里面选 \(i\) 个，大小为 \(j\) 的方案数
发现 \(dp\) 可以用背包维护
那么
\[g_{j+1} = \sum dp_{i,j} \times j! \times (son_u - 1 - j) ! \times \frac{f_u}{f_v \times son_u!} \]其中 \(j!\) 和 \((son_u -1 - j)!\) 表示排列顺序
$ \frac{f_u}{f_v \times son_u!}$表示 \(x\) 的儿子中，除了 \(y\) 的子树内部方案数的积。因为 \(ans\) 定义的时候就要求不能考虑 \(y\) 子树内部的方案数，因此要除去 \(y\) 的子树带来的贡献。
答案是 \(ans_{u,i} \times t_u\)
发现求 \(dp\) 是 \(O(n^4)\) 的，用回滚背包求解，优化到 \(O(n^3)\)
// 回滚背包
for (auto v : G[u]) {
if (v == fa) continue;
mul *= f[v];
++cnt;
for (int i = cnt; i; --i)
for (int j = sz[v]; j <= n; ++j)
ff[i][j] += ff[i - 1][j - sz[v]];
now += sz[v];
}
for (auto v : G[u]) {
if (v == fa) continue;
for (int i = 0; i <= n; ++i)
tmp[i] = 0;
for (int i = 1; i <= cnt; ++i)
for (int j = sz[v]; j <= n; ++j)
ff[i][j] -= ff[i - 1][j - sz[v]];
for (int i = 0; i <= cnt - 1; ++i) {
for (int j = 0; j <= n; ++j) {
tmp[j] += ff[i][j] * fac[i] * fac[cnt - 1 - i] * mul;
}
}
for (int i = cnt; i; --i)
for (int j = sz[v]; j <= n; ++j)
ff[i][j] += ff[i - 1][j - sz[v]];
mint val = 1 / f[u];
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n - 1 - i; ++j)
g[v][i + j + 1] += g[u][i] * tmp[j] * val;
}
Nauuo and Circle
清新的计数题，因为模型抽象错误，导致去看题解才发现哪里错了。
我们可以发现，题目中要求不相交，实际上就是要求子树的区间连续
考虑每一次加边 \((u,v)\) 对答案的贡献
对于点 \(u\) 来说，这条边可以放在他度数所形成的 \(deg_u\) 个区间里
点 \(v\) 同理
DS
[国家集训队] 等差子序列
问题等价于在排列中找三项的等差数列，这使得难度大大降低。
我们通常可以枚举中项，对于每个中项，我们可以考虑左右的项，如果左边的项对应的右边的项还没有出现，那么合法。
问题转化成状态回文 \(hash\) 了，可以用 \(SGT\) 维护一下哈希
做完了
标签：le,笔记,son,leq,子树,times,dp From： https://www.cnblogs.com/osky123456/p/17831204.html