洛谷3641 [APIO2016]最大差分
Luogu LOJ UOJ 分析 Subtask1 首先调用 MinMax(0,1e18,&a[1],&a[n]) 来求出 $a_1$ 和 $a_n$。 然后不断调用 MinMax(a[i-1]+1,a[j+1]-1,&a[i],&a[j]) 即可求出整个序列。 Subtask2 首先调用 MinMax(0,1e18,&a[1],&a[n]) ...
分类 题解 下的文章
- 首页
- 题解
洛谷6776 [NOI2020]超现实树
Luogu LOJ 分析 我们把每个节点都满足有一棵大小 $\leq 1$ 的子树的树称作「树枝」。 那么，$\mathrm{grow}(\mathscr{T})$ 是几乎完备的当且仅当所有高度为 $h$ 的树枝都在 $\mathrm{grow}(\mathscr{T})$ 中，这里的 $h$ 为 $\mathscr{T}$ 中树高的最大值。证明比较简单，因为任意一棵高度 $>h$ 的...
洛谷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$ 的情况。所以我们只要每次把最少的和最多的拿出来即可。 再考虑...
AtCoder Grand Contest 006 简要题解
比赛地址 只会做 A，自闭了 Prefix and Suffix 枚举重叠部分的长度即可。 代码 Median Pyramid Easy 显然 $x=1$ 和 $x=2n-1$ 的情况无解。 我们在中间放上 $x$，在它左边放 $x-1$，右边放 $x+1$ 和 $x-2$，可以发现这样子中间就会出现两列 $x$ 一直通到最顶上。 然而 $n=2$ 时只有三个数，需要特判掉。 代码 Rabb...
洛谷6773 [NOI2020]命运
Luogu LOJ 分析 规定根节点的深度为 $1$。 考虑 DP。设 $dp_{u,i}$ 表示以 $u$ 为根的子树，下端在子树中的未被覆盖的链的上端的最深深度为 $i$ 时的方案数（$i=0$ 表示全部被覆盖）。这个“最深”的好处在于我们覆盖了深的就一定会覆盖浅的，便于计数。 考虑转移，每次把一棵子树合并进来，考虑子树的父边填 $1$ 还是 $0$ 可以得到 可以想到整体 DP，用线...
洛谷6271 [湖北省队互测2014]一个人的数论
Luogu 分析 先莫比乌斯反演一下 后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$，显然是积性函数，所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$，所以只要算两项即可。 至于 $f_i$，可以求拉格朗日插值公式中每项系数求出，也可以直接高斯消元。 代码 // =...
洛谷6730 [WC2020]猜数游戏
Luogu LOJ 分析 先简单介绍一下阶。设 $\gcd(a,p)=1$，则满足 $a^x\equiv 1\pmod p$ 的最小正整数 $x$ 被称为 $a$ 在模 $p$ 意义下的阶，记做 $\operatorname{ord}_pa=x$ 阶有这样一些性质（这里没有证明，可以自行查找相关资料）： $\operatorname{ord}_p a|\varphi(p)$。于是我们可以枚...
洛谷6772 [NOI2020]美食家
Luogu LOJ 分析 如果见得多的话，从 “恰好第 $T$ 天回到城市 $1$”、$n\leq 50$、$w_i\leq 5$ 和 $T\leq 10^9$ 中不难知道本题要用矩阵快速幂。 这类问题是这样的：边有边权，求从 $i$ 出发经过恰好 $k$ 条边走到 $j$ 的最长路。 对这种题可以想到 DP。设 $dp_{k,i,j}$ 表示从 $i$ 出发经过恰好 $k$ 条边走到 $...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3516 [POI2011]PRZ-Shift
Luogu LOJ 分析 假设已经排好了 $1\sim i$，考虑如何把 $i+1$ 放到 $i$ 后面。可以构造出这样的方案： 首先用 ka 把 $i+1$ 移到最前面。 重复使用 2a 1b 把 $i$ 后面的元素两个两个地移到 $i+1$ 和 $1$ 之间。 如果最后 $i+1$ 后面还有一个元素，使用 1a 2b 把它移到 $i+1$ 和 $1$ 之间。 这样子有一个问题，即当 ...