分类 题解 下的文章

对于每个联通块,可以看做进出了若干次将其走完,显然可以暴力状压预处理出走 ii \in [1, k])步将该联通块走完的方案数。题意转换为,有 n 个颜色染若干个格子,相邻两个格子不能同色,某种颜色染了的次数唯一对应一个固定权值,一种方案的权值为每种颜色分别染的次数对应的权值的连乘积。这显然可以通过二项式反演来求。

READ MORE

联测的题,刚好前几天做过类似的 idea 结果就 AC 了 QAQ ...

考虑对于每个 k ,处理出 b_{1 ... n - k + 1} ,对于 b 的每个长度超过 k 的极长连续段连边,可以用调和级数证明总次数不会超过 O(n \log n) 。使用后缀数组维护,类似「优秀的拆分」,也可以直接二分。后缀数组的复杂度是 O(n \log n)

考虑连边,可以利用「萌萌哒」一题的 idea ,在倍增数组上递归合并,如果左右两边已经相同就 return 掉否则就计算到答案中。可以证明这个的复杂度是均摊 \log n 级别的。

故如果使用后缀数组 + ST 表 + 倍增并查集,复杂度为 O(n \log n \times \alpha(n)) ,可以通过此题。在 n 较小 T 较大的数据点可能因为常数原因 TLE ,可以考虑对于 n 足够小的部分 O(n^2) 暴力做。

READ MORE

被同学拉去做其他的题了咕掉了考试

假设用 f(a, b) 表示长度为 a ,有 b 个黑色珠子的且满足首位连接后没有超过 k 个连续黑色珠子的方案数,设 g(x) = f(n / x, m / x) ,可以通过 Burnside 引理证明 ans = \sum\limits_{i=1}^n g(n / \gcd(i, n))

考虑 f(a, b) 相当于求方程组

x_0 + x_1 + ... + x_{a - b} = b(0 \leq x_i \leq k, 0 \leq x_0 + x_{a - b} \leq k)

的解的个数,可以转换为生成函数

READ MORE

由于没有调查数据随机,LCP 的长度不会太大,假设为 limit 。我们可以离线出所有的询问,从左往右扫描右端点,在每个右端点用字典树维护出每个长度为 i ( i \in [1, limit] ) 的 LCP 的两个后缀中下标小的下标最大值,然后直接在上面暴力查询即可,复杂度 O((n + m) \times limit) ,取 limit = 50 可过。

READ MORE

一道挺妙的题,代码难度并不是很大。貌似洛谷春令营讲过这道题然而并没有人去写?(除了 LJC00118 和我 QAQ ...)

我们把区间离线,依次加入序列的每个数并更新以这个数作为右段点的查询的答案。

考虑新加入的数,它能够更新的区间一定满足以下性质。

  • 能够更新的区间不可能超过新加入的数的值上一次出现的位置(如果是第一次加入则为 0 )——再往前排序去重后并不会改变

  • 这个数最多会和值在其 \pm 11 的范围内的数产生贡献——长度超过 10 的极长连续段不需要统计答案。

我们可以把值域在其 \pm 11 范围内的数提取出来,并按照从后往前的顺序重新插入。每次考虑新加入的数对答案产生的贡献(注意是新「加入」而不是新「插入」)。可以发现这是个区间修改状物,可以直接线段树维护,也可以差分到树状数组上。

READ MORE

一道还是挺有意思的题,讲下某神仙课件里的 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