又名《MK 的第一次坐飞机体验》。 Day -1 上午 9:00 出发去机场。 尝试用手机里的 vim 写了个 A+B（ btw，现在也是用手机里的 vim 在写游记（ 总之很快就到机场了。 （为保护当事人隐私，把头挡住了） 不出意外的，飞机延误了（ 大概 12:44 的时候上的飞机，机舱内比想象中的要小。 12:59 起飞。人生中第一次坐飞机，感觉飞机太酷了。起飞的时候突然有很大的声音，然后很快速地往前开，上升的时候有很明显的超重感，特别是最开始的一段。 飞过云层的时候中间可以看到一条蓝色的分界线。 （拍得有点糊） 飞的过程中一直都能看到地面，如果没有云的话。 （btw 这张拍得真好看） （飞机上偷学，右边题目是付费内容所以打码了） 由于一直在颠簸所以一直没饭吃，现在已经 13:50 了还没吃午饭，饿死我了。 然后刚写完这句话就来饭了（ upd：吃完了，锐评一下。 首先我拿到的盒子是这样的： 结果打开来是这样的： 但是，虽然量很少，吃完竟然饱了。 味道还是挺不错的。 后面又做了会题，然后觉得困了就稍微眯了一会，然后飞机就开始降落了。 （重庆...

Link Cut Tree 可以用来维护动态树（树的形态会变化，支持加边删边）的信息。 实链剖分 对于树上每个节点连向儿子的所有边，任意选择至多一条进行剖分。我们称选择的边为实边，连接的儿子为实儿子，其余边为虚边，连接的儿子为虚儿子。 实际上就是任意剖分，因为是任意的所以可以由我们随意改变以满足动态树的要求。 辅助树 对于每一条实链都建一棵 Splay，其中序遍历是该链上点按深度从小到大排序。然后对于每棵 Splay，其根向该实链顶的父亲连一条虚边，这条虚边与 Splay 上的边的区别在于虚边认父不认子，即无法从父亲通过虚边访问儿子。 容易发现可以通过辅助树还原出原树，因此我们只需要维护辅助树而不需要维护原树。 例子： 原树为： 辅助树为： （图源 OI Wiki） 节点信息 对于辅助树上每个节点，因为是 Splay，所以需要维护父亲 fafafa，左右儿子 son0/1son _ {0 / 1}son0/1​，子树大小 sizsizsiz。下面会讲到需要支持 reverse 操作，因此需要维护翻转标记 swpswpswp，以及题目要求的信息。 以上信息在代码中分别记为...

KM 算法用来求二分图最大权完美匹配。当二分图两侧点数不同时，需要将较少部分的点补足，然后将不存在的边视为边权为 −∞-\infty−∞。 下设总点数为 2n2n2n，其中左部点编号为 1∼n1 \sim n1∼n，右部点编号为 n+1∼2nn + 1 \sim 2nn+1∼2n。下面认为图是完全二分图，不存在的边边权为 −∞-\infty−∞。 我们给每个点一个点权 lil _ ili​，称之为顶标。称一组顶标是可行顶标当且仅当对于所有边 (u,v)(u, v)(u,v) 都满足 wu,v≤lu+lvw _ {u, v} \le l _ u + l _ vwu,v​≤lu​+lv​。 我们定义相等子图是原图的一个子图 G′=(V,E′)G' = (V, E')G′=(V,E′)，使得 ∀(u,v)∈E′,wu,v=lu+lv\forall (u, v) \in E', w _ {u, v} = l _ u + l _ v∀(u,v)∈E′,wu,v​=lu​+lv​。 定理：若一张图的相等子图存在完美匹配，则该匹配即为原图的最大权完美匹配。 证...

约定：本文中用 u→vu \to vu→v 表示从 uuu 通过一条边直接走到 vvv，u⇝vu \rightsquigarrow vu⇝v 表示 uuu 通过某条路径走到 vvv。 支配关系与支配点 对于一张有向图和一个起始点 sss，我们定义 uuu 支配 vvv 当且仅当所有 sss 到 vvv 的路径都经过 uuu，记做 udomvu \mathbin{\mathrm{dom}} vudomv。 方便起见，我们认为 sss 可以到达图上每一个点。 若 udomvu \mathbin{\mathrm{dom}} vudomv，则我们认为 uuu 是 vvv 的一个支配点。每个点都是自己的支配点，sss 是所有点的支配点。 引理 1：支配关系是偏序关系。 根据定义有自反性，反对称性和传递性也是好证的。 引理 2：若 udomw,vdomwu \mathbin{\mathrm{dom}} w, v \mathbin{\mathrm{dom}} wudomw,vdomw，则 udomvu \mathbin{\mathrm{dom}} vudomv 或 vdomuv \ma...

符号与约定 下文默认图是连通的。 子图：点集与边集都是原图点集与边集的子集的图。 导出子图：一个点集的导出子图是该点集与所有两个端点均在该点集内的边构成的边集构成的子图。 团：完全子图。 极大团：不是其他团的子图的团。 最大团：点数最大的团。 团数：最大团的点数。 最小染色：使用最少的颜色给点染色使得任意一条边的两个端点颜色不同。 色数：最小染色的颜色数。 最大独立集：最大的点集使得其中任意两个点之间没有边。 最小团覆盖：用最少的团覆盖所有点。 弦：连接环上两个不相邻的点的边。 弦图：任意一个大小大于 333 的环都有一个弦的图。 弦图的性质 性质 1：团数小于等于色数。 考虑对最大团染色至少需要团数种颜色。 性质 2：最大独立集小于等于最小团覆盖。 每个团中至多选择一个点。 以上两个性质在普通图上也存在。 性质 3：弦图的导出子图一定是弦图。 考虑到若导出子图上存在无弦环，其在原图上也存在。 点割集 我们称弦图上任意两点 u,vu, vu,v 的点割集是满足删去其中的点后 u,vu, vu,v 不连通的集合。 引理 1：弦图上任意两点 u,vu, vu,...

前置知识 笛卡尔积 对于两个集合 X,YX, YX,Y，定义它们的笛卡尔积为 X×Y={(x,y)∣x∈X,y∈Y}X \times Y = \{(x, y) \mid x \in X, y \in Y\}X×Y={(x,y)∣x∈X,y∈Y}。 对于任意集合 AAA，定义 A1=AA ^ 1 = AA1=A，An=An−1×A(n∈N,n>1)A ^ n = A ^ {n - 1} \times A(n \in \N, n > 1)An=An−1×A(n∈N,n>1)。 二元关系 对于两个集合 X,YX, YX,Y，定义 XXX 到 YYY 的二元关系 RRR 为 X×YX \times YX×Y 的子集。对于 x∈X,y∈Yx \in X, y \in Yx∈X,y∈Y，记 xRyx\mathrel{R}yxRy 当且仅当 (x,y)∈R(x, y) \in R(x,y)∈R。 如果 Y=XY = XY=X，则可以称 RRR 是 XXX 上的二元关系。 等价关系 对于集合 XXX 上的二元关系 RRR，定义其为等价关系，当且仅当其满足： 自反性（r...

问题概述 给你一个正整数 nnn（1≤n≤2×1051 \le n \le 2 \times 10 ^ 51≤n≤2×105），求一个长度为 nnn 的 01 串，使得其本质不同的子串数量在所有 2n2 ^ n2n 个长度为 nnn 的 01 串中最多。 答案上界 我们考虑字符串的长度 iii，显然在长度为 nnn 的字符串中，本质不同的长度为 iii 的字符串个数上界为 min⁡{2i,n−i+1}\min\left\{2 ^ i, n - i + 1\right\}min{2i,n−i+1}，所以答案上界为 ∑i=1nmin⁡{2i,n−i+1}\sum _ {i = 1} ^ n \min\left\{2 ^ i, n - i + 1\right\}∑i=1n​min{2i,n−i+1}。 对于 n = 2 ^ k + k - 1 这里我们引入一个名为 De Bruijn Graph 的特殊的有向图。 定义 De Bruijn Graph 为一个有 knk ^ nkn 个点的有向图，每个点为一个由 kkk 种元素组成的有序 nnn 元组。当且仅当两个点 u,vu, ...

iframe { margin: auto; }

希望不会咕咕咕…… 有些题 LOJ 上没有就不写了。 JOISC 2014 Day1T1 バス通学 答案显然只能是以 111 为起点的边的起始时间。 考虑将每个点的出边按起始时间从大到小排序，则对于每个到达时间，可以走的边都是一个前缀。 我们考虑对于每个答案跑最短路，发现复杂度爆炸。 但是排序后前面的答案能走的边后面的答案一定能走，于是我们考虑在之前的基础上跑最短路。具体地，我们对于每个点记录一个指针表示当前枚举到了第几条出边，显然指针之前的边没必要重新走一遍。这样每条边至多被使用一次，时间复杂度为 O(mlog⁡m)O(m \log m)O(mlogm)。 最后对于每组询问二分即可得到答案。 提交记录 Day1T2 たのしい家庭菜園 显然最终序列一定是先一段单调不降再一段单调不升。 对于没有相同元素的情况，有一个显然的贪心：每次将最小的元素移到最左或最右（选择距离较短的），然后变成一个子问题。 考虑维护每个元素的实际位置，则移到最左对应前缀 +1+ 1+1，移到最前对应后缀 −1- 1−1，树状数组维护即可。 对于有相同元素的情况，每次移动距离最短的那个即可。 提交记录 ...

符号及基本定义及约定 整除、取模、质数、算术基本定理等的定义。这部分直接 skip 了。 以下无特殊说明则默认变量为正整数，函数为数论函数。 以下用 P\mathbb{P}P 表示素数集合。 数论函数 定义域为正整数的函数被称为数论函数。 积性函数 若数论函数 f(x)f(x)f(x) 满足对于任意 a⊥ba \bot ba⊥b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为积性函数。 若数论函数 f(x)f(x)f(x) 满足对于任意 a,ba, ba,b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为完全积性函数。 性质 若 f(x)f(x)f(x) 和 g(x)g(x)g(x) 均为积性函数，则以下函数也是积性函数。 h(x)=f(xp)h(x) = f(x ^ p)h(x)=f(xp)。 h(x)=fp(x)h(x) = f ^ p(x)h(x)=fp(x)。 h(x)=f(x)g(x)h...