上午：补题
通过题目：（大概是视角转换类dp）
蓝CF321E
蓝P1758
蓝P4492
青P1450
蓝P5664
蓝P2619
下午：学习树上dp 组合dp 容斥dp
组合数小知识：
- \(x^m=\sum_{p=0}^{m}S(m,p)\binom{x}{p}p!\)
其中S(m,p)是斯特林数
树上dp
-
一棵树，树上选k个点，不能选相邻点，最大化点权和
\(n \leq 10^5, k \leq 100\)
做法待补 \(\color{red}{待补}\) -
黑P4827
思路：
\(ans_i=\sum_{j=1}^{n} dist(i,j)^k\)
\(= \sum_{j=1}^{n} \sum_{p=0}^{k} S(k,p) \binom{dist(i,j)}{p}p!\)
\(= \sum_{j=1}^{n} \sum_{p=0}^{k} S(k,p)(\binom{dist(i,j)-1}{p} + \binom{dist(i,j)-1}{p-1})p!\)
\(= \sum_{p=0}^{k} S(k,p) \cdot p! \cdot \sum_{j=1}^{n} \left[ \binom{dist(i,j)-1}{p} + \binom{dist(i,j)-1}{p-1} \right]\)
考虑换根dp，设 \(f_{i,p}\) 表示以 \(i\) 号节点为根时， \(\binom{dist(i,j)}{p}\) 的值，则很容易推出 \(f_{i,p} = \sum(f_{son,p}+f_{son,p-1})\)
这道题就做完了
容斥原理
-
LOJ575
给出一个由大于小于号构成的序列，长度为 \(n-1\)，问有多少个 \(n\) 的全排列满足这个序列的要求
\(n \leq 5000\)
例：\(1<4>2<3\)
思路：[<><>]=[<o<o]-[<<<o]-[<o<<]+[<<<<] -
紫AT_arc101_c
思路：全覆盖=不做限制-没有全覆盖，即连通块 -
蓝P5664
思路：烹饪方法互不相同很好做
没有>k/2 = 不做限制 - 有>k/2，且只能有一个食材>k/2
枚举哪一列>k/2，dp即可
高阶状压dp
-
紫P3343
题意：每条边的边权在 \([0,1]\) 中等概率取，求图的最小生成树中最大边权的期望值
提示：\(n \leq 10\)，对于 \(p\) 个 \([0,1]\) 的随机变量，第k大的期望是 \(\frac{k}{p+1}\)
思路：即求解：在图中选 \(a\) 条边，满足它们是连通的；再在 \(a\) 条边中选一条边 \(E\)，满足删除 \(E\) 后这个图就不连通；
枚举点集 \(S,T\)，无疑是可以状压的，然后枚举它们之中的边 -
紫P2150
思路：对于满足 \(p>\sqrt{n}\) 的质因子 \(p\)，每个数最多只能拥有一个 -
紫P5369
思路：考虑最后选到的下标 \(p\) 的性质，即 \(s[p,i] \leq 0, 0 \leq s[i,p]\)。
思路待补 \(\color{red}{待补}\) -
紫P3959
思路(Naive)：枚举根节点，然后枚举第 \(i\) 层是哪些节点……状态 \(f[S][T][k]\)，复杂度 \(O(爆炸)=O(2^{2n}*n)\)(貌似)
思路(Naive but more nb): 我们直接抛弃一维，因为如果点 \(P\) 要连到点 \(Q\)，不可能连到再上一层，因为连上一层比连更以前的层更优……复杂度 \(O(3^n*n+2^n*n*m)\)
晚上：补题
通过题目：
黑P4827 (黑题首A祭)
紫P2150