T4 传信游戏
建反向边，从入度为 \(0\) 的结点开始搜
T5 喵喵卫士，全靠你了\(\star\)
考虑暴力枚举每个点的深度，发现只要知道相邻两层的深度就能用组合数算方案数，自然想到按层 DP，把上一层的点数记到状态里
赛时做法
按深度从小到大 DP 的话想要记录每个点是否被用过，以保证深度达到上界时它已经被加入，这是无法接受的
在一个前缀上可用，考虑倒序做。设 \(f[i,j,k]\) 表示构造好了深度 \(\ge i\) 的部分，深度为 \(i\) 的有 \(j\) 个点，还剩下 \(k\) 个点可用，容易枚举当前深度的点数转移
时间复杂度 \(O(n^{4})\)
std
其实是可以正着做的。先将 \(A\) 排序，预处理 \(g[i]\) 表示要求深度 \(\le i\) 的点数
设 \(f[i,j,k]\) 表示构造好了深度 \(\le i\) 的部分，深度为 \(i\) 的有 \(j\) 个点，一共用了 \(k\) 个点。这里先令用过的点编号为 \(1\sim k\)，之后再重新分配
枚举第 \(i+1\) 的点数 \(l\)。注意到已经有确定的 \(g[i]\) 个点深度 \(\le i\)，所以只能把 \(k+l-g[i]\) 个编号分配到前 \(i\) 层和第 \(i+1\) 层
T7 这一击贯穿星辰
std
预处理 \(i\) 点体力能够达到的 \(A\times B\) 的最大值 \(f[i]\)，\(100+C\) 的最大值 \(g[i]\)
可以证明 \(D\) 增大时分配给 \(100+C\) 的体力值是单增。决策单调性
凸包
分配 \(i\) 点体力给 \(A\times B\) 的答案为 \(f[i](g[m-i]-D)=-Df[i]+f[i]g[m-i]\)。凸包
T8 小度的双色球
从颜色和盒子两个角度考虑。精细实现可以做到时间 \(O(n\sqrt{n})\)，空间 \(O(n)\)，并避免使用哈希表
T9 寻宝
二分答案。考虑计算被偷走的价值 \(\le mid\) 最少需要多少名警员
如果 \(c[i]+d[i]>mid\)，那么先放 \(a[i]\) 个，之后每个点只有两种可能：不放 或 放 \(a[i]\) 个/放 \(b[i]-a[i]\) 个。考虑最小割，用割与 \(S\) 或 \(T\) 的连边代表两种情况
- 如果 \(d[i]>mid\)：\((S,i,b[i]-a[i])\)
- 如果 \(c[i]+d[i]\le mid\)：\((i,T,a[i])\)
- 如果原图中 \(i,j\) 相邻：\((i,j,+\infty)\)