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 维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
AGC028E High Elements
AtCoder 分析 因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。 为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。 首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。 证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我...
CF107D Crime Management
Codeforces Luogu 分析 不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。 因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。 实现时需要把后面的状态压成一个数。我的做法是压...
洛谷3643 [APIO2016]划艇
Luogu LOJ 分析 一个显然的想法是设 $dp_{i,j}$ 表示前 $i$ 个学校，第 $i$ 个学校派了 $j(j\neq 0)$ 艘划艇的方案数，然而第二维高达 $10^9$。 可以想到把所有端点离散化一下（这里改成左闭右开区间会方便一些），$dp_{i,j}$ 的定义改为前 $i$ 个学校，第 $i$ 个学校派的划艇数在第 $j$ 个区间中的方案数。 考虑转移。我们枚举一个 $...
洛谷4769 [NOI2018]冒泡排序
Luogu LOJ 分析 先考虑什么样的排列是满足条件的。冷静分析一下，达到下界当且仅当排列中没有长度 $\geq 3$ 的下降子序列，因为如果有的话一定有一个元素需要移过目标位置再移回来，从而不能达到下界。 先考虑忽略字典序的限制怎么做。设 $dp_{i,j}$ 表示长度为 $i$、首项为 $j$ 的合法排列数，转移有三种情况 第二个元素 $k$ 比 $j$ 大：那么如果 $k$ 不能与...
CF1174E Ehab and the Expected GCD Problem
Codeforces Luogu 分析 根据一些小学奥数知识可以知道第一个数应该是 $2^x3^y$ 的形式，而且 $y\in\{0,1\}$ ，因为 $>3$ 的质因子我们换成 $2^k$ 更优，$3^2$ 换成 $2^3$ 更优。为了方便设 $m=\lfloor\log_2 n\rfloor$。 考虑 DP。设 $dp_{i,x,y}$ 表示前 $i$ 个数，当前的 $\gcd$ ...
洛谷6775 [NOI2020]制作菜品
Luogu LOJ 分析 感觉同步赛上的我就是个 SB /kk 下面没有证明。 为了方便我们把所有 $d_i$ 从小到大排序。 先考虑 $m=n-1$ 的情况。此时显然会有 $d_1< k,d_1+d_n\geq k$，于是我们可以把 $d_1$ 和 $d_n$ 放在一起做一道菜，这样子变成了 $n'=n-1,m'=m-1$ 的情况。所以我们只要每次把最少的和最多的拿出来即可。 再考虑...
洛谷6773 [NOI2020]命运
Luogu LOJ 分析 规定根节点的深度为 $1$。 考虑 DP。设 $dp_{u,i}$ 表示以 $u$ 为根的子树，下端在子树中的未被覆盖的链的上端的最深深度为 $i$ 时的方案数（$i=0$ 表示全部被覆盖）。这个“最深”的好处在于我们覆盖了深的就一定会覆盖浅的，便于计数。 考虑转移，每次把一棵子树合并进来，考虑子树的父边填 $1$ 还是 $0$ 可以得到 可以想到整体 DP，用线...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷4459 [BJOI2018]双人猜数游戏
Luogu LOJ 分析 下面的 $n,m$ 和题面上是反的（因为我写完才发现这个问题所以就懒得改了）。 先复原一下样例一（$s=5,nm=60,n+m=16$）的游戏过程中双方的心理活动。 Bob：$(n,m)$ 的可能情况有 $(5,11),(6,10),(7,9),(8,8)$，所以回答不知道。 Alice：$(n,m)$ 的可能情况有 $(5,12),(6,10)$，两种情况 Bo...