CF521D Shop
Codeforces Luogu 分析 首先可以知道，我们执行操作的顺序一定是赋值 $\to$ 加 $\to$ 乘。 先考虑只有乘的情况。因为我们要最大化所有数的积，因此直接选最大的 $m$ 个即可。 再考虑有加的情况，我们想办法把加转化为乘。对于每一个位置，我们把对它的加操作按权值从大到小排序，显然我们选的会是一段前缀，因此我们可以转化为一些乘 $\displaystyle\frac{\s...
分类 题解 下的文章
- 首页
- 题解
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$...
BZOJ4347 [POI2016]Nim z utrudnieniem
BZOJ 分析 后手必胜当且仅当每堆石子个数异或和为 $0$。 设 $dp_{i,j,k}$ 表示前 $i$ 堆石子，扔掉的堆数模 $d$ 等于 $j$，扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的，显然过不了。 考虑一个优化：把所有堆按石子个数从小到大排序，这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorna...
洛谷2605 [ZJOI2010]基站选址
Luogu 分析 设 $dp_{i,j}$ 表示建了 $i$ 个基站，最后一个建在 $j$ 时只考虑 $1\sim j$ 的最小代价。 这样子最后会有一段没有算，所以我们在最后再加一个村庄 $n+1$，然后答案就是所有 $dp_{i,n+1}$ 的最小值。 考虑转移。枚举上一个建站的位置可以得到 这里的 $cost(p,j)$ 表示 $[p,j]$ 中只有 $p$ 和 $j$ 建了基站时会...
洛谷5504 [JSOI2011]柠檬
Luogu 分析 首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。 设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬，$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬，容易得到状态转移方程 因为要求的是最大值，所以维护上凸壳；因为 $x_i$ 单...
AGC009C Division into Two
AtCoder Luogu 分析 为了方便，令 $A>B$。 那么显然，如果存在 $3$ 个数满足两两之差小于 $B$，无解。所以把这个先判掉。 设 $dp_i$ 表示第一个集合最后选的数是 $i$ 的方案数，转移枚举上一个数是谁即可。 考虑如果 $j$ 能转移到 $i$，那么 $j$ 会具有哪些性质。可以发现： $j<i$ $S_i-S_j\geq A$ 对于 $[j+1,i...
洛谷3647 [APIO2014]连珠线
Luogu UOJ 分析 首先考虑连线的过程。可以发现，以最先加的点为根，所有的蓝线都会是儿子-自己-父亲的形式。 于是我们枚举根，然后 f。设 $f_{u,0/1}$ 表示以 $u$ 为根的子树，$u$ 是或不是蓝线中点的最大得分。 首先考虑 $f_{u,0}$ 的转移。此时每个子节点要么不是中点，要么是中点。于是有 这样子是 $O(n^2)$ 的，结合随机算法可能可以拿 57 分。 因...
洛谷3226 [HNOI2012]集合选数
Luogu 分析 我们考虑构造一个矩形 $a$ 满足 这样子问题就变为在这个矩形中选若干个数，相邻的不能选，求方案数。 我们需要保证 $a_{i,j}\leq n$，因此行数不会超过 $17$，列数不会超过 $11$，因此可以状压 DP。设 $dp_{i,S}$ 表示前 $i$ 行，第 $i$ 行选了 $S$ 的方案数，枚举上一行状态转移即可。 但是这样会有一个问题，就是有一些数（例如 $...
CF55D Beautiful numbers
Codeforces Luogu 分析 显然是数位 DP，但是要想清楚这个条件怎么处理。 注意到如果 $a_1|d,a_2|d,\cdots,a_k|d$，那么 $\operatorname{lcm}(a_1,a_2,\cdots,a_l)|d$。因此我们只需要知道这个数对每一位上的数的 $\operatorname{lcm}$ 取模的结果。 但是 $\operatorname{lcm}$ ...