BZOJ4347 [POI2016]Nim z utrudnieniem
BZOJ 分析 后手必胜当且仅当每堆石子个数异或和为 $0$。 设 $dp_{i,j,k}$ 表示前 $i$ 堆石子，扔掉的堆数模 $d$ 等于 $j$，扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的，显然过不了。 考虑一个优化：把所有堆按石子个数从小到大排序，这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorna...
博主已经退役，评论可能会审核很久才能通过。
BZOJ 分析 后手必胜当且仅当每堆石子个数异或和为 $0$。 设 $dp_{i,j,k}$ 表示前 $i$ 堆石子，扔掉的堆数模 $d$ 等于 $j$，扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的，显然过不了。 考虑一个优化：把所有堆按石子个数从小到大排序，这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorna...
Luogu 分析 设 $dp_{i,j}$ 表示建了 $i$ 个基站，最后一个建在 $j$ 时只考虑 $1\sim j$ 的最小代价。 这样子最后会有一段没有算，所以我们在最后再加一个村庄 $n+1$，然后答案就是所有 $dp_{i,n+1}$ 的最小值。 考虑转移。枚举上一个建站的位置可以得到 这里的 $cost(p,j)$ 表示 $[p,j]$ 中只有 $p$ 和 $j$ 建了基站时会...
Luogu 分析 首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。 设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬，$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬，容易得到状态转移方程 因为要求的是最大值，所以维护上凸壳；因为 $x_i$ 单...
AtCoder Luogu 分析 为了方便，令 $A>B$。 那么显然，如果存在 $3$ 个数满足两两之差小于 $B$，无解。所以把这个先判掉。 设 $dp_i$ 表示第一个集合最后选的数是 $i$ 的方案数，转移枚举上一个数是谁即可。 考虑如果 $j$ 能转移到 $i$，那么 $j$ 会具有哪些性质。可以发现： $j<i$ $S_i-S_j\geq A$ 对于 $[j+1,i...
Luogu UOJ 分析 首先考虑连线的过程。可以发现，以最先加的点为根，所有的蓝线都会是儿子-自己-父亲的形式。 于是我们枚举根，然后 f。设 $f_{u,0/1}$ 表示以 $u$ 为根的子树，$u$ 是或不是蓝线中点的最大得分。 首先考虑 $f_{u,0}$ 的转移。此时每个子节点要么不是中点，要么是中点。于是有 这样子是 $O(n^2)$ 的，结合随机算法可能可以拿 57 分。 因...
Luogu 分析 我们考虑构造一个矩形 $a$ 满足 这样子问题就变为在这个矩形中选若干个数，相邻的不能选，求方案数。 我们需要保证 $a_{i,j}\leq n$，因此行数不会超过 $17$，列数不会超过 $11$，因此可以状压 DP。设 $dp_{i,S}$ 表示前 $i$ 行，第 $i$ 行选了 $S$ 的方案数，枚举上一行状态转移即可。 但是这样会有一个问题，就是有一些数（例如 $...
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}$ ...
Luogu 分析 首先应该可以一眼看出来这就是个 treap，然后改权值就相当于旋转。 考虑到 treap 旋转后中序遍历是不变的，因此我们可以先给所有节点按数据值排个序，这样就能得到中序遍历了。 进一步发现，中序遍历中一段区间在 treap 上是连通的一部分。因此可以考虑区间 DP。 设 $dp_{i,j,k}$ 表示 $[i,j]$ 内的节点，根节点权值 $\geq k$ 的最小代价。因...
Luogu LOJ 分析 通过手玩一些数据可以发现，我们一定会从一个有宝藏的点出发，而且按照 DFS 序遍历所有有宝藏的点会最优。 不妨设现有的有宝藏的点按 DFS 序排序后为 $a_1,a_2,a_3,\cdots,a_k$，那么我们要求的就是 $\operatorname{dis}(a_1,a_2)+\operatorname{dis}(a_2,a_3)+\cdots\operatorn...