如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。

M_sea 的博客

Delightful

洛谷3643 [APIO2016]划艇

LuoguLOJ分析一个显然的想法是设 $dp_{i,j}$ 表示前 $i$ 个学校，第 $i$ 个学校派了 $j(j\neq 0)$ 艘划艇的方案数，然而第二维高达 $10^9$。可以想到把所有端点离散化一下（这里改成左闭右开区间会方便一些），$dp_{i,j}$ 的定义改为前 $i$ 个学校，第 $i$ 个学校派的划艇数在第 $j$ 个区间中的方案数。考虑转移。我们枚举一个 $k$，然后...

  • M_sea
  • 2020 年 08 月 27 日
  • 暂无评论

    • 洛谷4769 [NOI2018]冒泡排序

    LuoguLOJ分析先考虑什么样的排列是满足条件的。冷静分析一下，达到下界当且仅当排列中没有长度 $\geq 3$ 的下降子序列，因为如果有的话一定有一个元素需要移过目标位置再移回来，从而不能达到下界。先考虑忽略字典序的限制怎么做。设 $dp_{i,j}$ 表示长度为 $i$、首项为 $j$ 的合法排列数，转移有三种情况第二个元素 $k$ 比 $j$ 大：那么如果 $k$ 不能与后面的元素构...

  • M_sea
  • 2020 年 08 月 26 日
  • 暂无评论

    • CF1174E Ehab and the Expected GCD Problem

    CodeforcesLuogu分析根据一些小学奥数知识可以知道第一个数应该是 $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$ 是 $2...

  • M_sea
  • 2020 年 08 月 26 日
  • 暂无评论

    • CF838D Airplane Arrangements

    CodeforcesLuogu分析我们考虑计算总方案数乘上合法的概率。然而这样子并不好计算，考虑一些转化。我们加一个位置 $n+1$，然后把飞机看成一个环，问题变为每个人随机一个初始位置和方向，走到第一个空位停下，如果停在 $n+1$ 就不合法。这样子最后的每种座位情况都是等概率的，那么 $n+1$ 上有人的概率为 $\frac{m}{n+1}$，即合法概率为 $\frac{n+1-m}{n...

  • M_sea
  • 2020 年 08 月 25 日
  • 暂无评论

    • 洛谷3641 [APIO2016]最大差分

    LuoguLOJUOJ分析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]) 来求出 $a_1...

  • M_sea
  • 2020 年 08 月 24 日
  • 暂无评论

    • 洛谷6776 [NOI2020]超现实树

    LuoguLOJ分析我们把每个节点都满足有一棵大小 $\leq 1$ 的子树的树称作「树枝」。那么，$\mathrm{grow}(\mathscr{T})$ 是几乎完备的当且仅当所有高度为 $h$ 的树枝都在 $\mathrm{grow}(\mathscr{T})$ 中，这里的 $h$ 为 $\mathscr{T}$ 中树高的最大值。证明比较简单，因为任意一棵高度 $>h$ 的树都能由...

  • M_sea
  • 2020 年 08 月 24 日
  • 暂无评论

    • 洛谷6775 [NOI2020]制作菜品

    LuoguLOJ分析感觉同步赛上的我就是个 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$ 的情况。所以我们只要每次把最少的和最多的拿出来即可。再考虑 $m\geq...

  • M_sea
  • 2020 年 08 月 22 日
  • 暂无评论

    • 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$ 时只有三个数，需要特判掉。代码Rabbit Exercis...

  • M_sea
  • 2020 年 08 月 21 日
  • 暂无评论

    • 洛谷6773 [NOI2020]命运

    LuoguLOJ分析规定根节点的深度为 $1$。考虑 DP。设 $dp_{u,i}$ 表示以 $u$ 为根的子树，下端在子树中的未被覆盖的链的上端的最深深度为 $i$ 时的方案数（$i=0$ 表示全部被覆盖）。这个“最深”的好处在于我们覆盖了深的就一定会覆盖浅的，便于计数。考虑转移，每次把一棵子树合并进来，考虑子树的父边填 $1$ 还是 $0$ 可以得到可以想到整体 DP，用线段树维护每个节...

  • M_sea
  • 2020 年 08 月 20 日
  • 暂无评论

    • 洛谷6271 [湖北省队互测2014]一个人的数论

    Luogu分析先莫比乌斯反演一下后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$，显然是积性函数，所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$，所以只要算两项即可。至于 $f_i$，可以求拉格朗日插值公式中每项系数求出，也可以直接高斯消元。代码// ========...

  • M_sea
  • 2020 年 08 月 20 日
  • 暂无评论