CF527E Data Center Drama
Codeforces Luogu 分析 这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来，然后把欧拉回路上的边依次正向、反向定向即可。 这个很容易造，我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数，再连一个自环即可。显然这样子边数是最小的。 代码 // =================================...
M_sea 发布的文章
- 首页
- M_sea
洛谷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$ ...
CF838D Airplane Arrangements
Codeforces Luogu 分析 我们考虑计算总方案数乘上合法的概率。然而这样子并不好计算，考虑一些转化。 我们加一个位置 $n+1$，然后把飞机看成一个环，问题变为每个人随机一个初始位置和方向，走到第一个空位停下，如果停在 $n+1$ 就不合法。 这样子最后的每种座位情况都是等概率的，那么 $n+1$ 上有人的概率为 $\frac{m}{n+1}$，即合法概率为 $\frac{n+1...
洛谷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...