【HNOI 2016】序列 / 题解

题目描述 [https://loj.ac/problem/2051] 给定一个长度为 $n$ 的序列 $a$,每次询问 $[l,r]$ 内所有连续子区间的区间最小值。 思路 我们分别讲解如何使用离线 / 在线算法解决本题。 离线 / 莫队 使用莫队将问题离线后,我们需要思考如何从 $[l,r-1]$ 的答案推至 $[l,r]$ 的答案。 首先,我们知道一共新增了 $r-l+1$ 个,以 $r$ 为右端点的区间。如果将 $[l,r]$ 中区间最小值的位置记为 $p$,这些区间可以根据是否包含 $p$ 划分为两部分:对于包含 $p$ 的那 $p-l+1$ 个区间,显然它们对答案的贡献都等于…

【笔记】Borůvka's Algorithm

Borůvka 算法是一种计算图最小生成树的贪心算法,于 1926 年被 Otakar Borůvka [https://en.wikipedia.org/wiki/Otakar_Bor%C5%AFvka] 首次发表。 基本原理 首先,我们会找到图上每个节点到其他节点的最短边,然后把这些边加入森林中。我们不断重复这个过程,即每次给森林中每棵树找到连接其他树的最短边,然后将这样的边加入森林。 每次操作会减少森林中树的数量至少一半,于是我们可以在对数次操作内完成这个算法。 均摊复杂度为 $\Theta((n+m)\log n)$。 典型例题 对于大多数的图,Kruskal 和 Prim 已经非常优秀了。这里我们给出一个特殊情况,在这种情况下 Borůvka 的效率比前两者高得多。 > 给定 $n$ 个二维平面内的点,两点之间边权为两点的曼哈顿距离,求这些点的最大生成树大小。 在这里,图中边的数量达到了 $n^…

【笔记】线图 / Line graph

在图论中,一张无向图的线图是能体现其连边状态的一种生成图。有关线图的中文资料很少,但有关它的外文资料非常丰富。在这篇文章中,我将简单介绍线图的定义,以及提出计算线图最小生成树大小的一种方法。 Formal definition 给定一张无向图 $G$,它的线图 $L(G)$ 满足以下条件 * $L(G)$ 中的每个节点表示 $G$ 中的一条边; * $L(G)$ 中两个节点之间连边,当且仅当它们代表的边在 $G$ 中有公共点。 Example 下面展示了一张图(蓝色节点)和它的线图(绿色节点),线图上每个节点标出了原图上边两个端点的编号。 Minimum spanning tree 现在我们有一张无向图 $G$ 和它的线图 $L(G)$。如果我们我们把图 $G$ 的点和边都赋上权值,在 $L(G)$ 中,我们可以认为点权为原图中对应边的边权,边权为原图中对应公共点的点权。 我们解决这个问题的思路都基于…

【IOI 2018】Werewolf / Solution

Description 官方 PDF 题面 [https://ioi2018.jp/wp-content/tasks/contest1/CHN-werewolf.pdf] Idea 相当于询问是否存在一个中间点 $X$,满足 $S_i$ 能仅经过编号 $≥ L_i$ 的点走到 $X$,且 $E_i$ 能仅经过编号 $≤ R_i$ 的点走到 $X$。 考虑第一部分,第二部分类似。把边权设置成 $min(A_i, B_i)$,然后求一个 Kruskal 重构树。即模拟 Kruskal 求最小生成树的过程,每次加入一条边时,就新建一个表示这条边的节点,作为那两个点的父亲。 于是 $S_…

【IOI 2018】Combo / Solution

Description 官方 PDF 题面 [https://ioi2018.jp/wp-content/tasks/contest1/CHN-combo.pdf] Idea 我们需要一种能一次确定一位的高效询问算法。 考虑到 $p$ 的最大长度为 $4n$,$S$ 的首字母只出现一次,那么我们每次可以基于已知的前缀 $s$,询问 $4$ 种可能的情况。 不妨设 $S$ 的首字母为 $A$,对于已知的前缀 $s$,我们询问 $$sXBsXXsXYsB$$ 如果返回值比当前长度大 $2$,说明下一位是 $X$;大 $1$,说明下一位是 $B$,否则下一位为 $Y$。 对开头和结尾的两个字符做二分查找,总询问次数为 $n+2$。 Code #include "combo.…

【杂谈】Boy Erased: Some Thoughts

Boy Erased 是一部能让我平静地看完最后一个镜头,然后在片尾曲响起的一瞬间开始泣不成声的电影。 它不像 Love, Simon 或者 Brokeback Mountain ,主人公 Jared 的出柜并没有得到前者一般广泛的包容和鼓励,故事的结局也不及后者孤独绝望 – 它只是现实罢了。 这种现实发生在向父母出柜之后的 Jared 身上。 Jared 的父母都是虔诚的基督徒,包容同性恋意味着背弃教会,为了宗教信仰,他们毅然决然把 Jared 送进了性取向矫正机构。 在这样的机构里,同性恋 / 同性接触被描绘成 “暴力、滥交和艾滋” 的代表,是背离上帝而犯下的罪行。 每个人都要上台承认自己的罪行 – 在来到这里之前,自己过着 “同性恋式的生活”,叛逆和滥交是罪行的标准答案。 而拒绝承认自己的罪行,是成为了 “撒旦的牺牲品”,是被恶魔附身。机构的工作人员带领着在场的所有人,充满正义感地用《圣经》抽打倔强的 Cameron,知道他承认自己与同性做过的每一件事情。 他们不是在迫害同性恋着,他们是在拯救迷途的孩子,他们的口号是…

【笔记】快速沃尔什变换入门

概念 快速沃尔什变换是一种类似 FFT,用来加速逻辑位运算卷积的算法。具体地,它被设计为用来解决以下问题: $$C_k=\sum_{i\oplus j=k}a_i\times b_j$$ 其中,$\oplus$ 表示位运算 $\lor, \wedge, \veebar$。直接枚举 $i,j$ 的复杂度是 $\Theta(n^2)$,FWT 能加速这个过程到 $\Theta(n\log n)$。 原理 前面说到它类似 FFT,因为它们都是通过先做一个变换,相乘,然后逆变换得到结果的,而变换的过程都是折半、分治。 我们定义变换为 $tf$,有 $$tf(C)…

【笔记】从傅里叶变换到数论变换

概述 我们可以使用傅里叶变换来快速计算卷积。然而快速傅立叶变换具有一些实现上的缺点,我们必须做复数而且是浮点数的运算,因此计算量会比较大,而且浮点数运算产生的误差会比较大。 这个问题可以用数论变换解决。在模意义下,一些整数可以发挥单位复根的作用,使我们更精确地计算只有整数参加的卷积运算结果。 原根 概念 在 $FFT$ 中,我们利用了单位复根的以下性质: 1. $\omega_n^k$ 互不相同; 2. $\omega_{2n}^{2k}=\omega_n^k$; 3. $\omega_n^{k+\frac{n}{2}}=-\omega_n^k$ 4. 当 $k \neq 0$ 时,$1+\omega_n^k+(\omega_…