CF708E Student's Camp
Codeforces Luogu 分析 显然营地不连通只能是上下分开，即存在相邻两行剩下的砖块区间没有交。 考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行，第 $i$ 行剩下 $[j,k]$，且前 $i$ 行连通的概率。容易得到转移 于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出，第二个可以在 DP 时维护...
分类 题解 下的文章
- 首页
- 题解
洛谷5366 [SNOI2017]遗失的答案
Luogu LOJ 分析 首先特判掉 $G\nmid L$ 的情况。 为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。 我们先不管那个必须选 $X$ 的条件，想一想怎么做。 注意到值域只有 $10^8$，即最多只有 $8...
洛谷5405 [CTS2019]氪金手游
Luogu LOJ 分析 首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。 考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$，整棵树 $w_i$ 的和为 $S$，则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为 这个概率只和子树有关，因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率，转移即为树...
ARC096D Sweet Alchemy
AtCoder Luogu 分析 考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。 令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。 然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。 考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，...
洛谷4694 [PA2013]Raper
Luogu 分析 设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。 考虑 WQS 二分。二分斜率 $m$，求切点相当于最小化 $y$ 轴上的截距，即求出最小的 $f(x)-mx$。 这个最小值的意义就是可以随意造光盘，且每造一张光盘可以赚 $m$ 元时的最小花费（显然它一定非负）。 考虑用堆解决这个问题。 维护一个小根堆，每次将 $a_i$...
CF724E Goods transportation
Codeforces Luogu 分析 容易想到一个网络流做法，即源点向每个点连容量为 $p_i$ 的边，每个点向汇点连容量为 $s_i$ 的边，每个点向编号比它大的点连容量为 $c$ 的边，然后求最大流即可。 发现最大流不好求，而图比较特殊，可以考虑 DP 求最小割。 设 $dp_{i,j}$ 表示前 $i$ 个点有 $j$ 个点和源点相连的最小割。转移这样考虑：如果 $i$ 与源点相连，...
CF568E Longest Increasing Subsequence
Codeforces Luogu 分析 考虑普通 LIS 问题的解法，即设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，转移时二分即可。 考虑沿用到这道题中。设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，$g_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值所在位置；再设 $l_i$ 表示以 $i$ 结尾的 LIS 长度，$p_i$ 表示以 $i$ 结尾...
AGC030D Inversion Sum
AtCoder Luogu 分析 设 $dp_{x,y}$ 表示 $a_x > a_y$ 的概率（假设每个操作发生的概率都为 $\frac{1}{2}$）。 对于每个操作 $(i,j)$，我们会让所有的 $dp_{i,k}$ 和 $dp_{j,k}$ 都变为 $\frac{1}{2}(dp_{i,k}+dp_{j,k})$，会让所有的 $dp_{k,i}$ 和 $dp_{k,j}$ 都...
CF995F Cowmpany Cowmpensation
CodeForces Luogu 分析 设 $dp_{i,j}$ 表示以 $i$ 为根的子树，$i$ 的权值为 $j$ 的方案数。容易得到转移 前缀和优化即可做到 $\mathcal{O}(D)$ 转移，总时间复杂度 $\mathcal{O}(nD)$。 考虑优化。可以发现，$dp_{1,x}$ 为关于 $x$ 的 $n$ 次多项式（可以理解为每个叶子节点都为一次式，往上合并时做乘法从而次...
AGC033D Complexity
AtCoder Luogu 分析 首先能够想到设 $dp_{i,j,k,l}$ 为左上角为 $(i,j)$、右下角为 $(k,l)$ 的矩阵的凌乱度，然而显然是过不去的。 注意到答案在 $\log nm$ 级别，因此可以考虑设 $dp_{i,j,k,l}$ 为凌乱度为 $i$ 时，上界为 $j$ 下界为 $k$ 左界为 $l$ 的矩阵右界最远能到哪。根据横切和竖切的情况不难得到转移 如果暴...