分类 题解 下的文章

一道还是挺有意思的题,讲下某神仙课件里的 Matrix Tree 定理做法。

首先最小生成树有个很显然的性质,就是对于任意两颗同一个图的最小生成树,他们的边权序列排序后应当相同。可以考虑克鲁斯卡尔算法的过程用归纳法证明。

也就是说如果两棵最小生成树不同,一定是克鲁斯卡尔算法加边时,对 同一边权相同数量 条边的选择不同。

容易发现,每次以任意顺序加完所有相同边权的边后,图的连通性相同,而新加的边,一定是将原图的一些不连通的联通块连接起来。考虑暴力做法 2^{10} 枚举,即可有一种朴素的 AC 算法。

然而此题可以跑到 O(n + m k^2) ,可以发现选边的过程类似于生成树计数,我们可以直接用 Matrix Tree 定理求出对于每个连边后联通的联通块的方案树,根据乘法原理相乘即可。

需要注意:

  1. 题目给出的数不是质数(我就因为这个调了很久
  2. 需要把加边前已经联通的联通块缩点

READ MORE

容易发现答案与旗杆的顺序无关,我们可以把旗杆按照从矮到高的顺序排序,这样的话我们只需要维护两个操作:

  1. 插入一些 0
  2. 给一个前缀整体 +1

考虑每次 +1 操作,除了这个前缀中的最大值,每个数的相对位置不会改变。考虑放到线段树上,对于最大值二分出其区间,对其特殊处理后移即可。

READ MORE

本题中我们可以对机器人进行四种操作:

  • U ,即向量 (0, 1)
  • D ,即向量 (0, -1)
  • L ,即向量 (1, 0)
  • R ,即向量 (0, -1)

考虑正解,容易发现我们需要分开考虑 xy 轴的变化,然而上述四种操作对 xy 轴而言有 1 / 0 / -1 三种情况,较难考虑,且一边为 1-1 时,另一边只能为 0 ,较难判断。

于是有一个经典的 trick 就是旋转坐标轴。

考虑以 (\frac {\sqrt 2} 2 , \frac {\sqrt 2} 2)(-\frac {\sqrt 2} 2, \frac {\sqrt 2} 2) 为基底,考虑原来的四种操作:

  • U 变为向量 (1, 1)
  • D 变为向量 (-1, -1)
  • L 变为向量 (-1, 1)
  • R 变为向量 (1, -1)

那么就可以分开考虑 xy 轴的 \pm 1 变化。

假设最后所有向量的和为 \vec{S} ,则题目给出的坐标在时间模 L 后即可转换为一个关于 \vec S 的一次函数。列出不等式并判断下奇偶性即可。

READ MORE

与上一题相同的思路,考虑分块 + 凸包来维护。

  • 对于 1 操作,两端的块暴力查询,中间的取整块计算的结果

  • 对于 2 操作,暴力重构两个块

  • 对于 3 操作,两端的暴力重构,中间的同样用单调栈来维护。

READ MORE

非常好的分块 + 凸包题。

讲每个人按照 b 排序并依次插入,题目可以转换为维护

  • 插入一个数;
  • 查询从大到小排序后每个数的排名乘以自身的最大值。

考虑分块维护插入操作

  • 暴力重构当前块
  • 单调栈维护下凸壳维护整体排名 + 1 操作,对于当前块之后的块,执行这个操作。

查询时直接查询即可。

READ MORE