CF718E Matvey's Birthday
Codeforces Luogu 分析 首先可以证明图的直径长度不超过 $15$。 先预处理 $f_{i,j}$ 表示 $i$ 走到一个颜色为 $j$ 的点的最短路、$g_{i,j}$ 表示某个颜色为 $i$ 的点走到某个颜色为 $j$ 的点的最短路。这可以通过以每种颜色为起点 BFS 一遍求出。 接着我们枚举 $i$，并试着找到 $j\in[1,i)$ 使得 $dis(i,j)$ 最小。实...
标签 状压 下的文章
- 首页
- 状压
Codeforces Round #614 简要题解
Div1 Div2 从一月份一直咕到现在的一场比赛 /kel ConneR and the A.R.C. Markland-N 暴力往两边找即可。 代码 JOE is on TV! 显然每次淘汰掉刚好一个人是最好的。 答案即为 $\sum_{i=1}^n\frac{1}{i}$。 代码 NEKO's Maze Game 维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即...
洛谷6622 [省选联考 2020 A/B 卷]信号传递
Luogu LOJ 分析 考虑从 $x$ 传递到 $y$ 的代价，显然有 这样子就可以 $\mathcal{O}(m2^m)$ 预处理 $g(x,S)$ 和求 $f_S$，总时间复杂度 $\mathcal{O}(m2^m)$。 然而存 $g$ 需要 736MB 空间，并开不下。 但是可以发现，我们只需要求 $x\in S$ 的 $g(x,S)$，所以我们只需要对每个 $x$ 求 $2^{m...
CF1316E Team Building
Codeforces Luogu 分析 有一个显然的状压 DP：设 $dp_{i,S}$ 表示前 $i$ 个人，$S$ 中的位置被选中时的最大力量值，转移枚举当前这个人当观众还是进某个位置即可。 然而 $p+k\leq n$，所以这个做法不太行。 注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序，当 $i-|S|>k$ 时 $i$ 显然不会被选...
洛谷5366 [SNOI2017]遗失的答案
Luogu LOJ 分析 首先特判掉 $G\nmid L$ 的情况。 为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。 我们先不管那个必须选 $X$ 的条件，想一想怎么做。 注意到值域只有 $10^8$，即最多只有 $8...
洛谷5772 [JSOI2016]位运算
Luogu 分析 先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。 考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直...
CF79D Password
Codeforces 分析 题目给的操作就是区间异或。考虑将原数组差分，那么我们相当于每次可以将两个距离为 $a_i$ 的位置异或 $1$，然后求从全 $0$ 数组生成原数组的最小步数。 我们将这个东西反过来，变为求原数组的差分数组生成全 $0$ 数组的最小步数。 注意到原数组的差分数组至多有 $20$ 个 $1$，因此可以考虑状压 DP。 设 $dp_{S}$ 表示 $S$ 中的 $1$...
洛谷3226 [HNOI2012]集合选数
Luogu 分析 我们考虑构造一个矩形 $a$ 满足 这样子问题就变为在这个矩形中选若干个数，相邻的不能选，求方案数。 我们需要保证 $a_{i,j}\leq n$，因此行数不会超过 $17$，列数不会超过 $11$，因此可以状压 DP。设 $dp_{i,S}$ 表示前 $i$ 行，第 $i$ 行选了 $S$ 的方案数，枚举上一行状态转移即可。 但是这样会有一个问题，就是有一些数（例如 $...