KeBlog

WC2020

发表于 2020-08-04 更新于 2021-03-23 分类于总结

别人在放暑假的时候，我却在参加冬令营。

不愧是冬眠营，前面四天的授课和营员交流都没听懂啥，真就冬眠去了。。。

第一天上来就是松松松手把手教你写一个路由器？

营员交流 20 分钟 100 页 ppt ？

授课讲的东西太多是 OI 无关的，营员交流信息量又太大~~（把课件蒯走就完事了）~~，还好是线上冬令营，掉线了反正也重连不上，干脆颓废折腾去了。

总而言之，前四天全都在划水，一点也不夸张。所以重点就全在 Day5 的考试上了。

阅读全文 »

弦图相关

发表于 2020-08-04 分类于算法

简单记录弦图相关概念和算法。

一些定义

弦：连接环上不相邻两点的边。

弦图：每个简单环都有至少一条弦的无向图。

事实上，可以预见的是，弦图的每个简单环都可以表示为若干三元环的对称差。

团：任意两点都有边的无向图。

单纯点：与其相邻的点集的导出子图是团。

完美消除序列：点集的一个排列 ${p}$ ，满足每个点 $p_{i}$ 在 $p_{j} (j > i)$ 的导出子图中都是单纯点。

阅读全文 »

好题题解整理（三）

发表于 2020-08-03 更新于 2021-03-29 分类于整理

没有摘要。

cf1368f Lamps on a Circle

有一个长为 $n$ 的环，环上每个点是一个开关，Alice Bob 玩游戏，每轮执行以下流程：

Alice 选择是否结束游戏。如果是则游戏结束。
Alice 选择一个参数 $k$ ，并将任意 $k$ 个开关打开。
Bob 将任意连续的 $k$ 个开关关闭。

Alice Bob 分别想要最大最小化最后打开的开关数量。设 $R (n)$ 是双方执行最优策略时最后打开的开关数量。

交互题，实现 Alice 的策略，使得最后打开的开关数量不少于 $R (n)$ 。

题解

不妨让 Alice 去复制 Bob 的操作，那么只要 Bob 选择连续 $k$ 个开关不是全开的，通过一次复制后回到 Bob 操作，局面不变，但是 $k$ 会变小，因为 Alice 只需要选择那些实际上被 Bob 关闭的开关。

那么可以发现 Bob 实际上只能关掉不超过 $k$ 的一个全部打开的连续段。游戏的一轮可以转换为以下流程：

Alice 选择是否结束游戏。如果是则游戏结束。
Alice 选择一个参数 $k$ ，并将任意 $k$ 个开关打开。
Bob 选择长度不超过 $k$ 的连续的一段 打开的 开关关闭。

进一步可以发现这个游戏只需要进行一轮，进行多轮是没有意义的。这样一来，游戏的最终局面仅仅由 Alice 第一次打开的开关集合有关，设 Alice 打开了 $p$ 个连续段，第 $i$ 个连续段长度为 $a_{i}$ 。那么问题就是在满足 $\sum_{i = 1}^{p} (a_{i} + 1) \leq n$ 的前提下最大化

$\sum_{i = 1}^{p} a_{i} - m a x {a_{i}}$

显然前者的和最大不超过 $n - p$ ，只需要最小化后者，尽量使得 $a$ 平均时最优，可以得到

$R (n) = m a x {n - p - ⌈ \frac{n - p}{p} ⌉}$

用上述策略实现 Alice 即可。

阅读全文 »

Green Hackenbush

发表于 2020-08-01 更新于 2021-03-29 分类于算法

最近看到一个有意思的博弈问题。

对于一张无向连通图（不一定是简单图），规定一个点为根，两个玩家轮流操作，每次可以删掉根可以到达的一条边，不能操作者输。

这类博弈即 Green Hackenbush 。

树

从简单情况入手，对一棵有根树做 Green Hackenbush ，如何得到一棵树的 SG 值？

首先，如果树的点数恰为 1 ，SG 值显然为 0 。

如果根的度数恰为 1 ，设与根相连的点为 $u$ ，设 $u$ 的子树对应的 SG 值为 $k$ ，不难发现原树的 SG 值即 $k + 1$ 。

如果根的度数大于 1 ，那么可以把根“分裂”，把原树拆成一个森林，每个森林的根的度数都恰好为 1 。容易发现这个森林与原树等价，那么应用 SG 定理，原树的 SG 值就是每个子树的 SG 值加一的异或和。

阅读全文 »

好题题解整理（二）

发表于 2020-07-28 更新于 2021-03-29 分类于整理

没有摘要。

loj576 「LibreOJ NOI Round #2」签到游戏

有一个长为 $n$ 的序列 ${B}$ ，每次可以选一个区间 $[l, r]$ ，代价是 $B$ 在该区间的 $gcd$ ，得到一个方程 $\sum_{i = l}^{k} x_{i} = K$ ，要求花费最小的代价得到 $n$ 个线性无关的方程。

$q$ 次询问和修改，每次修改会修改 $B$ 的一个位置的值。

时间复杂度： $O (n \log + q \log^{2})$ 。

题解

（未实现）

引理 1

存在最优解选择的每个区间满足 $l = 1 \lor r = n$ 且存在 $[1, n]$ 。

设 $y_{i} = \sum_{j = 1}^{i} x_{j}$ ，那么选择区间 $[l, r]$ 实质上是选择方程 $y_{r} - y_{l - 1} = K$ ，注意有 $y_{0} = 0$ 。

转换为图论问题，每个 $y_{i}$ 是一个节点，一个方程是一条边，方程线性无关等价于图无环~~，那么这个问题本质上是求最小生成树~~。

在这个图论问题的基础上该引理是很自然的。定 $0$ 为树根，把边定向，从父亲指向儿子，那么对于一条边 $u \to v$ ，若 $u < v$ 则把 $(u, v)$ 换成 $(0, v)$ ，否则换成 $(u, 0)$ 。容易发现每条边的代价不增，并且新图仍然是一颗树。此时每条边必然连向 $0$ 或 $n$ ，并且必然有边 $(0, n)$ 。

引理 2

存在最优解满足：存在参数 $p$ 使得选择的区间由 $[1, n]$ ， $[1, i] (p \leq i < n)$ 和 $[j, n] (1 < j \leq p)$ 组成。

根据引理 1 ，由于选了 $[1, n]$ ，选前缀 $[1, i]$ 和选后缀 $[i + 1, n]$ 是等价的。那么最优解显然就是在每个 $[1, i]$ 和 $[i + 1, n]$ 中选代价较小的一个，前者随 $i$ 单调不增，后者随 $i$ 单调不减。那么选前者的必然是一段后缀 $i$ ，选后者的必然是一段前缀 $i$ 。

正题

由引理 2 ，可以二分参数 $p$ ，比较 $[1, p]$ 和 $[p, n]$ 的 gcd 大小进行判定。然后根据不同前后缀 gcd 的数量是 $O (\log)$ 的，求答案枚举不同的 gcd 算贡献数量即可。

用线段树维护序列 $B$ ，需要支持 $O (\log)$ 的区间 gcd 查询或者把二分放在线段树上。具体细节不在讨论范围内。

阅读全文 »

好题题解整理（一）

发表于 2020-07-27 更新于 2021-06-08 分类于整理

没有摘要。

th1690-a

给定一个 $n$ 个点的竞赛图，求一个 $m$ 边染色方案。（ $n = 3000, m = 14$ ）

竞赛图是任意一对点都有恰好一条有向边的有向图。

题解

这样转换问题：允许边染上多种颜色，给每个点 $u$ 一个颜色集合 $S_{u}$ ，对于一条边 $(u, v)$ ，它染上颜色 $c$ 当且仅当 $c \in S_{u} \land c \notin S_{v}$ 。

这样一来很容易给出一个构造方案：把大小恰为 $\frac{m}{2}$ 的颜色集合任意分配给每个点即可。这样任意一对点 $u, v$ 都存在一个 $u$ 拥有而 $v$ 没有的颜色。并且有 $(\binom{m}{\frac{m}{2}}) \geq n$ 。

阅读全文 »

NOI真题训练

发表于 2020-07-26 更新于 2021-03-29 分类于其他

真题训练，不依靠外力做题，多写几个部分分，研究高效得分方法。

以下评测分数以 loj 提交为准（冒泡排序除外）。分数统计仅代表极限水平，并不代表真实水平，不供参考。

NOI2017

0 + 76 + 100 + 70 + 100 + 88 + 20 = 454

集训队线 438 。

整数

看完题就有了一个压位的平方暴力的思路，码了码 WA 在了减法的情况，改对后得到了 56 分，本来对照数据表以为只有 30 分左右。

阅读全文 »

拉格朗日反演

发表于 2020-07-22 分类于算法

拉格朗日反演常用于提取一个幂级数 $A (x)$ 的 $n$ 次项系数。

对于常数项为 0 ，一次项非零的幂级数 $A (x)$ ，设其复合逆为 $F (x)$ ，有

$[x^{n}] A (x) = \frac{1}{n} [x^{n - 1}] (\frac{x}{F (x)})^{n}$

阅读全文 »

万能欧几里得

发表于 2020-07-19 更新于 2020-07-26 分类于算法

有一类问题可以归结为以下模型：

有一种元素，它们之间可以定义乘法，且乘法满足结合律。给定两个元素 $X, Y$ 和正整数 $n$ ，求

$F (P, R, Q, n, X, Y) = \prod_{i = 0}^{n} Y^{f (i) - f (i - 1)} X$

其中 $f (x) = ⌊ \frac{x P + R}{Q} ⌋$ ，特别的 $f (- 1) = 0$ ，也就是说第 $i$ （从 $0$ 开始）个 $X$ 前面都有恰好 $f (i)$ 个 Y 。

不难发现所有类欧几里得都可以归结为该模型。

阅读全文 »

拟阵和贪心

发表于 2020-07-16 更新于 2020-08-11 分类于算法

理论基础

一个拟阵是一个二元组 $M = (U, I)$ ，其中 $U$ 是一个有限集合，一般是待研究元素的全集， $I$ 是 $U$ 的一些子集的集合，一般是满足给定限制的子集的集合。

另外，拟阵要满足两个性质：

遗传性： $\forall S \in I, T \subseteq S$ 满足 $T \in I$ 。
交换性： $\forall A \in I, B \in I, | A | < | B |$ 满足 $\exists x \in B, x \notin A$ 使得 $A \cup {x} \in I$ 。

有一部分贪心可以为这样的形式：给定一个映射 $f : U \to R$ ，要在 $I$ 中找到一个 $S$ 使得 $\sum_{x \in S} f (x)$ 最大。

这类贪心都可以用如下流程解决：

设 $U_{0} := U$ 表示可选集合， $S := \emptyset$ 表示要求的集合。
在集合 $U_{0}$ 中找出 $f (x)$ 最大的元素 $x$ 。
如果 $S \cup {x} \in I$ ，令 $S := S \cup {x}$ 。
令 $U_{0} := U_{0} ∖ {x}$ ，若 $U_{0}$ 非空，返回第 2 步。

阅读全文 »