博主已经退役，评论可能会审核很久才能通过。

M_sea 的博客

“Poet Nai Dist, Phier”

CF749E Inversions After Shuffle

Codeforces Luogu 分析 考虑一个点对 $(i,j)\;(i<j)$ 的贡献。 分两种情况考虑：$i,j$ 都在连续段内、$i,j$ 不都在连续段内。 先考虑第一种情况。显然连续段的左端点 $\in[1,i]$，右端点 $\in[j,n]$，于是随机出的连续段包含 $i,j$ 的概率为 那么对于每个 $i$，我们只要知道满足 $j>i,a_j<a_i$ 的...

  • M_sea
  • 2020 年 01 月 15 日
  • 暂无评论

    • CF903G Yet Another Maxflow Problem

    Codeforces Luogu 分析 容易发现，至多只会割掉一条 A 边和一条 B 边。我们加边 $(A_0,A_1,0)$ 和 $(B_n,B_{n+1},0)$，然后求 $A_0$ 到 $B_{n+1}$ 的最大流，就可以转化成恰好割掉一条 A 边和一条 B 边的情况了。 设割掉了 $A_i\to A_{i+1}$ 和 $B_j\to B_{j+1}$，则此时的最大流为 显然对于每个...

  • M_sea
  • 2020 年 01 月 14 日
  • 暂无评论

    • CF901C Bipartite Segments

    Codeforces Luogu 分析 「图中没有偶环」等价于「图是仙人掌」。因此本题中「一个诱导子图是二分图」等价于「一个诱导子图没有环」。 考虑求出一个 $nxt_i$ 表示以 $i$ 为左端点的最大右端点。我们找到所有的环，假设某个环上点编号的最小值为 $mn$，最大值为 $mx$，那么 $[1,mn]$ 中的所有点的 $nxt$ 都不会 $\geq mx$，即用 $mx-1$ 对 $...

  • M_sea
  • 2020 年 01 月 14 日
  • 暂无评论

    • AGC005F Many Easy Problems

    AtCoder Luogu 分析 设要求的东西是 $f_i$，考虑怎么求这个东西。 可以想到计算每个点在多少种方案中，进而想到计算每个点不在多少种方案中。于是容易得到包含 $u$ 的方案数为 可以发现后面已经是卷积的形式了，于是直接 NTT 即可。虽然这个模数很奇怪，但是它确实是 NTT 模数。 代码 // =================================== // ...

  • M_sea
  • 2020 年 01 月 11 日
  • 暂无评论

    • 三角恒等式整理

    背不下来，我没了 QAQ

  • M_sea
  • 2019 年 12 月 20 日
  • 5 条评论

    • 洛谷4062 [Code+#1]Yazid 的新生舞会

    Luogu LOJ 分析 显然每个数作为众数的情况是相互独立的，因此我们考虑枚举众数 $k$，然后计算有多少个区间中 $k$ 的出现次数超过一半。 不妨把等于 $k$ 的数看做 $1$，不等于 $k$ 的数看做 $-1$，那么我们相当于要求有多少个区间的和大于 $0$。这个东西等价于前缀和的逆序对数。 但是直接做的话当 $A_i$ 的数量比较多时显然会 TLE，所以我们需要一些优化。 考虑到...

  • M_sea
  • 2019 年 12 月 17 日
  • 暂无评论

    • CF1276C Beautiful Rectangle

    Codeforces Luogu 分析 考虑枚举短边的长度 $r$。设数 $i$ 有 $cnt_i$ 个，那么我们至多能填 个数到矩形中。因此当短边长度为 $r$ 时长边至多为 $\left\lfloor\frac{s_r}{r}\right\rfloor$。 因为短边长度不超过 $\sqrt{n}$，因此我们可以在 $\mathcal{O}(n\sqrt{n})$ 的时间内求出答案。 现...

  • M_sea
  • 2019 年 12 月 15 日
  • 暂无评论

    • 洛谷4199 万径人踪灭

    Luogu BZOJ 分析 下文中默认字符串的下标从 $0$ 开始。 可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。 后面的就是 manacher 板子，考虑怎么求前面的。 设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有 后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1...

  • M_sea
  • 2019 年 12 月 14 日
  • 暂无评论

    • PKUSC2018 简要题解

    不想写计算几何，告辞。

  • M_sea
  • 2019 年 12 月 10 日
  • 6 条评论

    • PKUWC2018 简要题解

    998244353？998244353！

  • M_sea
  • 2019 年 12 月 07 日
  • 暂无评论