你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 \(A\) 依赖软件包 \(B\)，那么安装软件包 \(A\) 以前，必须先安装软件包 \(B\)。同时，如果想要卸载软件包 \(B\)，则必须卸载软件包 \(A\)。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 \(0\) 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 \(0\) 号软件包不依赖任何一个软件包。依赖关系不存在环（若有 \(m \ (m \geq 2)\) 个软件包\(A_1, A_2, A_3, \ldots ,A_m\)，其中 \(A_1\) 依赖 \(A_2\)，\(A_2\) 依赖 \(A_3\)，\(A_3\) 依赖 \(A_4\)，……，\(A_{m−1}\) 依赖 \(A_m\)，而 \(A_m\) 依赖 \(A_1\)，则称这 \(m\) 个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 \(0\)。

对于所有数据，\(n \leq 100000, \ q \leq 100000\)。

阅读全文 »

树链剖分学习笔记

发表于 2022-11-05 更新于 2024-11-30 分类于 OI ，学习笔记

树链剖分是一个很常见的处理树上问题的算法，但之前一直没学 /kk，现在终于把这个坑补了。

这里只讲了重链剖分，不涉及其他剖分方式。

概念

树链剖分是一种把树上问题转化为序列问题的算法。它可以将树上的一条路径所经过的点用序列中的若干条区间表示。

首先我们需要知道几个概念：重儿子、轻儿子、重边、轻边。我们定义对于一个节点 \(u\) 的儿子为 \(v\)，我们定义以 \(v\) 为根的子树中节点最多的子树所对应的 \(v\) 为重儿子，其余的 \(v\) 为轻儿子。父亲连向重儿子的边为重边，父亲连向轻儿子的边为轻边。如果同时有多个以 \(v\) 为根的子树节点数相同且最大，则选取任意一个 \(v\) 为重儿子，其余为轻儿子。这样对于每个非叶节点，我们都有一个重儿子和一个重边。

阅读全文 »

「SPOJ 4354」Snowflakes - Hash

发表于 2022-11-04 分类于 OI ，题解

题意描述

SPOJ 链接

有 \(n (n \le 10^5)\) 个雪花。每个雪花是 \(6\) 个数组成的一个环。若两个环经过旋转（也可不旋转）后环上数字相等，则两个雪花相同。若两个环顺时针和逆时针数字相同则两个环也相同。判断是否有相同的雪花。

阅读全文 »

「CSP-S 2022」星战 - 图论 + Hash

发表于 2022-11-04 更新于 2022-11-14 分类于 OI ，题解

题意描述

洛谷链接

LibreOJ 链接

在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。

战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：

敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。

注意：摧毁只会导致虫洞不可用，而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：

A 型特种部队则可以将某个特定的虫洞修复。
B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。

为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：

如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。

总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。

对于所有数据保证：\(1 \le n \le 5 \times {10}^5\)，\(1 \le m \le 5 \times {10}^5\)，\(1 \le q \le 5 \times {10}^5\)。

阅读全文 »

「CSP-S 2022」策略游戏 - 贪心 + 线段树

发表于 2022-11-04 更新于 2022-11-14 分类于 OI ，题解

题意描述

洛谷链接

LibreOJ 链接

小 L 和小 Q 在玩一个策略游戏。

有一个长度为 \(n\) 的数组 \(A\) 和一个长度为 \(m\) 的数组 \(B\)，在此基础上定义一个大小为 \(n \times m\) 的矩阵 \(C\)，满足 \(C_{i j} = A_i \times B_j\)。所有下标均从 \(1\) 开始。

游戏一共会进行 \(q\) 轮，在每一轮游戏中，会事先给出 \(4\) 个参数 \(l_1, r_1, l_2, r_2\)，满足 \(1 \le l_1 \le r_1 \le n\)、\(1 \le l_2 \le r_2 \le m\)。

游戏中，小 L 先选择一个 \(l_1 \sim r_1\) 之间的下标 \(x\)，然后小 Q 选择一个 \(l_2 \sim r_2\) 之间的下标 \(y\)。定义这一轮游戏中二人的得分是 \(C_{x y}\)。

小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

对于所有数据，\(1 \le n, m, q \le {10}^5\)，\(-{10}^9 \le A_i, B_i \le {10}^9\)。对于每轮游戏而言，\(1 \le l_1 \le r_1 \le n\)，\(1 \le l_2 \le r_2 \le m\)。

阅读全文 »

「CSP-S 2022」假期计划 - 最短路 + BFS + 贪心

发表于 2022-11-04 更新于 2022-11-14 分类于 OI ，题解

题意描述

洛谷链接

LibreOJ 链接

小熊的地图上有 \(n\) 个点，其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\) 与 \(z_1\)、\(z_1\) 与 \(z_2\)、……、\(z_{k - 1}\) 与 \(z_k\)、\(z_k\) 与 \(y\) 之间均有直达的线路，那么我们称 \(x\) 与 \(y\) 之间的行程可转车 \(k\) 次通达；特别地，如果点 \(x\) 与 \(y\) 之间有直达的线路，则称可转车 \(0\) 次通达。

很快就要放假了，小熊计划从家出发去 \(4\) 个不同的景点游玩，完成 \(5\) 段行程后回家：家 \(\to\) 景点 A \(\to\) 景点 B \(\to\) 景点 C \(\to\) 景点 D \(\to\) 家且每段行程最多转车 \(k\) 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A \(\to\) 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D \(\to\) 家这段行程转车时经过的点。