KeBlog

The OI Algorithm Blog of Kewth

0%

发表于 更新于 分类于

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

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

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

营员交流 20 分钟 100 页 ppt ？

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

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

阅读全文 »

发表于 分类于

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

一些定义

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

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

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

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

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

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

阅读全文 »

发表于 更新于 分类于

没有摘要。

cf1368f Lamps on a Circle

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

  1. Alice 选择是否结束游戏。如果是则游戏结束。
  2. Alice 选择一个参数 \(k\) ，并将任意 \(k\) 个开关打开。
  3. Bob 将任意连续的 \(k\) 个开关关闭。

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

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

题解

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

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

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

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

\[\sum_{i=1}^p a_i - max\{a_i\}\]

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

\[R(n) = max\{n - p - \lceil \frac{n-p}{p} \rceil\}\]

用上述策略实现 Alice 即可。

阅读全文 »

发表于 更新于 分类于

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

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

这类博弈即 Green Hackenbush 。

树

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

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

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

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

阅读全文 »

发表于 更新于 分类于

没有摘要。

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 \rightarrow v\) ，若 \(u < v\) 则把 \((u, v)\) 换成 \((0, v)\) ，否则换成 \((u, 0)\) 。容易发现每条边的代价不增，并且新图仍然是一颗树。此时每条边必然连向 \(0\) 或 \(n\) ，并且必然有边 \((0, n)\) 。

引理 2

存在最优解满足：存在参数 \(p\) 使得选择的区间由 \([1, n]\) ，\([1, i] (p \le i < n)\) 和 \([j, n] (1 < j \le 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 查询或者把二分放在线段树上。具体细节不在讨论范围内。

阅读全文 »

发表于 更新于 分类于

没有摘要。

th1690-a

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

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

题解

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

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

阅读全文 »

发表于 更新于 分类于

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

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

NOI2017

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

集训队线 438 。

整数

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

阅读全文 »

发表于 分类于

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

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

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

阅读全文 »

发表于 更新于 分类于

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

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

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

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

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

阅读全文 »

发表于 更新于 分类于

理论基础

一个拟阵是一个二元组 \(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 \rightarrow R\) ，要在 \(I\) 中找到一个 \(S\) 使得 \(\sum_{x \in S} f(x)\) 最大。

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

  1. 设 \(U_0 := U\) 表示可选集合，\(S := \varnothing\) 表示要求的集合。
  2. 在集合 \(U_0\) 中找出 \(f(x)\) 最大的元素 \(x\) 。
  3. 如果 \(S \cup \{x\} \in I\) ，令 \(S := S \cup \{x\}\) 。
  4. 令 \(U_0 := U_0 \setminus \{x\}\) ，若 \(U_0\) 非空，返回第 2 步。
阅读全文 »