洛谷3687 [ZJOI2017]仙人掌
Luogu LOJ 分析 首先特判原图不是仙人掌的情况，直接输出 $0$ 即可。 显然连边不会跨过一个环，因此可以直接断掉所有环边，则原图变为一个森林，方案数即为每棵树的方案数之积。 考虑如何计算一棵树的方案数。 我们假装一个边也是一条链，那么就相当于求用若干条不相交的链覆盖树上所有边的方案数。 考虑 DP。设 $dp_u$ 为 $u$ 子树中所有边加上父边被覆盖的方案数，$g_n$ 为一个...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
51nod1597 有限背包计数问题
51nod 分析 考虑根号分治。令 $B=\left\lceil\sqrt{n}\right\rceil$，则 $[1,B]$ 内的物品能取完，$[B+1,n]$ 内的物品无法取完。 先考虑 $[1,B]$ 内物品。设 $f_{i,j}$ 表示前 $i$ 种物品和为 $j$ 的方案数，容易写出转移 注意到 $(i,j)$ 的转移点 $(i,k)$ 满足 $k\leq j\land j\eq...
JOI 2018 Final 简要题解
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫，维护 ...
CF1097D Makoto and a Blackboard
Codeforces Luogu 分析 容易想到设 $dp_{i,j}$ 表示 $j$ 次操作后 $i$ 的期望大小，转移直接枚举约数即可。然而这样子显然是会 T 的... 注意到当 $\gcd(i,j)=1$ 时有 $dp_{i\times j,k}=dp_{i,k}\times dp_{j,k}$，因此我们可以将 $n$ 分解为 $p_1\!^{c_1}p_2\!^{c_2}\cdots...
BZOJ4722 由乃
BZOJ 分析 $[l,r]$ 的非空子集数为 $2^{r-l+1}-1$，而子集贡献数至多为 $1000(r-l+1)$。 当 $2^{r-l+1}-1>1000(r-l+1)$ 即 $r-l+1>13$ 时，根据抽屉原理显然有解，因此直接输出 Yuno 即可。 先考虑操作 $1$ 怎么做。用树状数组维护每个点被修改的次数，然后倍增即可求出答案。 再考虑操作 $2$。设 $dp...
JOI 2019 Final 简要题解
传送门 勇者比太郎 看懂题后可以发现，我们要求每个 J 右边的 O 的数量乘下面的 I 的数量之和。 预处理前缀和后枚举每个 J 计算即可。 代码 画展 先以 $V_i$ 为第一关键字、$S_i$ 为第二关键字对所有画排个序，以 $C_i$ 为关键字对所有画框排序。 然后从后往前扫，如果当前的画能装进没有装画的 $C$ 最大的画框里，就把它装进去。 正确性比较显然？反正我不会证 代码 有趣的...
CF79D Password
Codeforces 分析 题目给的操作就是区间异或。考虑将原数组差分，那么我们相当于每次可以将两个距离为 $a_i$ 的位置异或 $1$，然后求从全 $0$ 数组生成原数组的最小步数。 我们将这个东西反过来，变为求原数组的差分数组生成全 $0$ 数组的最小步数。 注意到原数组的差分数组至多有 $20$ 个 $1$，因此可以考虑状压 DP。 设 $dp_{S}$ 表示 $S$ 中的 $1$...