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

M_sea的博客

——どうか悔いることなく 明日へ続く道 歩いて——

CF917D Stranger Trees

CodeforcesLuogu算法一分析设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可。时间复杂...

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

    • CF156D Clues

    CodeforcesLuogu分析我们把每个连通块看成一个点，然后用 Prufer 序列计数。那么方案数为用并查集求出连通块个数及每个连通块的大小即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ===================...

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

    • 洛谷4606 [SDOI2018]战略游戏

    LuoguLOJ分析考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所以可以考虑把...

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

    • 洛谷4630 [APIO2018]Duathlon 铁人两项

    LuoguLOJ分析可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$，这样子 ...

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

    • 洛谷6558 [APIO2017]考拉的游戏

    LuoguLOJ分析Subtask1在某个物品旁边放上一个蓝色石子，这样子 Koala 就只能得到至多 $99$ 个物品，而没选的那个物品一定是权值最小的。这样子只需要调用一次 playRound，可以得到 $4$ 分。Subtask2先在每个物品旁边放 $1$ 个蓝色石子，这样子 Koala 会选出至多 $50$ 个物品，所以我们可以确定权值前 $50$ 大的物品。那么可以再在这 $50$...

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

    • 洛谷6630 [ZJOI2020]传统艺能

    LuoguLOJ分析因为期望具有线性性，所以可以对每个节点计算它在 $k$ 次操作后有标记的概率，全部加起来即为答案。考虑 DP。设 $f_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后有标记的概率，$g_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后某个祖先有标记的概率，$h_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后自己和祖先都没有标记的概率。转移需要再求出 $5$...

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

    • CF908H New Year and Boolean Bridges

    CodeforcesLuogu分析显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内，所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。显然每个强连通分量内成环最优，那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。因为点数 $\geq ...

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

    • ARC098F Donation

    AtCoderLuogu分析设 $c_i=\max\left\{0,a_i-b_i\right\}$，则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。然后可以发现两个结论：每个点只会在最后一次访问时被捐赠。$c_i$ 大的会优先捐赠。那么我们大概是这样捐赠的：首先选一个点 $u$，假设删掉 $u$ 后形成了 $tot$ 个连通块，则先捐赠掉 $tot-1$ 个，然后捐赠 $...

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

    • CF1067D Computer Game

    CodeforcesLuogu分析显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移于是只要快速找到决策点改变的位置即可。一个想法是...

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

    • CF1139D Steps to One

    CodeforcesLuogu分析直接算即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #def...

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