题意描述

洛谷链接

LibreOJ 链接

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

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

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

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

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

• 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\)。

题意描述

洛谷链接

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\)。

题意描述

洛谷链接

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\) 家这段行程转车时经过的点。

假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

对于所有数据，保证 \(5 \le n \le 2500\)，\(1 \le m \le 10000\)，\(0 \le k \le 100\)，所有景点的分数 \(1 \le s_i \le {10}^{18}\)。保证至少存在一组符合要求的行程。

寄

省流

代码

题面

Day -3

考点出来了，在七高考试 总算在成都了。

下午练手写了一道 大模拟 然后被 C++ 的除法向 0 取整坑了几个小时 QWQ

打算明天复习一下模板，避免考试写挂。

题意描述

Codeforces 链接

你有一个只含 \(0\) 和 \(1\) 的 \(n\) 位序列，你需要将这个序列排序。对于这个序列，你每次可以随机地选择两个数进行交换，求将这个序列排好序所交换次数的期望 \(\mod 998244353\)。

题意描述

洛谷链接

LibreOJ 链接

小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 \(\texttt{random}\) 和 C/C++ 中的 \(\texttt{rand}\)）来获得随机性。事实上，随机数生成函数也不是真正的「随机」，其一般都是按某个算法计算得来的。

比如，下面这个二次多项式递推算法就是一个常用算法：

算法选定非负整数 \(x_0,a,b,c,d\)，并采用如下公式递推进行计算。 \[\forall i \geq 1,\ x_i=(ax_{i-1}^2+bx_{i-1}+c)\bmod d\] 这样可以得到一个任意长度的非负整数 数列 \(\{x_i\}_{i \geq 1}\)。一般说来，我们认为这个 数列 是随机的。

利用随机序列 \(\{x_i\}_{i \geq 1}\)，我们还可以采用如下算法产生一个从 \(1\) 到 \(K\) 的 随机排列 \(\{T_i\}^K_{i \geq 1}\)：

1. 初始设 \(T\) 为 \(1 \sim K\) 的递增序列；
2. 对 \(T\) 进行 \(K\) 次交换，第 \(i\) 次交换，交换 \(T_i\) 和 \(T_{(x_i \bmod i)+1}\) 的值。

此外，小 H 在这 \(K\) 次交换的基础上，又 额外 进行了 \(Q\) 次交换工作，对于第 \(i\) 次交换，小 H 会选定两个额外下标 \(u_i\) 和 \(v_i\)，并交换 \(T_{u_i}\) 和 \(T_{v_i}\) 的值。

为了检验这个随机生成算法的实用性，小 H 设计了如下问题：

小 H 有一个 \(N\) 行 \(M\) 列的棋盘，她首先按照上述过程，通过 \(N\times M+Q\) 次交换操作，生成一个 \(1 \sim N \times M\) 的随机排列 \(\{T_i\}^{N \times M}_{i \geq 1}\)，然后将这 \(N \times M\) 个数逐行逐列依次填入这个棋盘：也就是第 \(i\) 行第 \(j\) 列的格子上所填入的数应为 \(T_{(i-1)M+j}\)。

接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 \(N\) 行第 \(M\) 列的格子。

小 H 把所经过格子上的数字都记录了下来，并 从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 \(N+M-1\) 的升序序列，我们称之为 路径序列。

小 H 想知道，她可能得到的 字典序最小 的 路径序列 应该是怎样的呢？

题意描述

Codeforces 链接

给定一个 \(n\) 个节点的树，其节点被标记为 \(1\) 到 \(n\)，而且该树的根为 \(1\)，另外也给定一个积分序列 \(s\)

如果下列两个条件都满足，则我们称路径集合k可用：

• 该集合内所有路径从 \(1\) 开始

• \(c_i\) 为覆盖节点 \(i\) 的路径数量，对于每对拥有同个父节点的节点 \((u,v)\)，要求\(|c_u-c_v|\) 小于等于1

对于每个路径集合，其权值被定义为 \(\sum\limits_{i=1}^n{c_i s_i}\)

显而易见，每组数据至少有一个可用的路径集合，找出所有可用路径集合中的最大权值

题意描述

YbtOJ 链接（需付费）

小 K 有一棵 \(n\) 个点，\(n - 1\) 条边的苹果树，将树上的边称为 A 类边。

小 K 还往这棵树上加上了 \(m\) 条边，称加上的边为 B 类边。

作为小 K 的好朋友，你想要砍掉小 K 的苹果树，但是你发现砍掉一条边不一定能使苹果树不连通，于是你需要求出：有多少选取 恰好一条 A 类边和恰好一条 B 类边 的方案，使得这两条边删去之后，原图不连通。

两种方案不同当且仅当一条边在第一种方案中被删除了但在第二种方案中没有被删除。

题意描述

牛客链接（需付费）

鸡尾酒是一个多操手，他可以同时操作 \(m\) 个账号。今天，他使用这些账号一起打一个 boss。这个 boss 战的地图共有 \(n\) 个关键点，其中有 \(n - 1\) 条边，每条边连接着两个不同的点，使得从任意点出发可以到达其他所有的点。鸡尾酒的 \(m\) 个账号分别编号 \(1\) 至 \(m\)，一开始，第 \(i\) 个账号在点 \(s_i\)。可能有两个账号在同一位置。

现在，boss 放出了一个致命技能。boss 在地图上标出了 \(m\) 个关键点，想成功躲避这个技能，必须在每一个被标记的点上，都有一个账号站在上面。注意，可能会有点被多次标记，多次标记的点需要有多个账号站在上面。

由于鸡尾酒无法分身，所以 他必须先把一个账号移动到一个位置，才能动另一个账号，不能同时移动多个账号。假设鸡尾酒的任意账号通过第 \(i\) 条边的时间为 \(w_i\)，请帮鸡尾酒求出他成功躲避技能所需要的最少时间。

数据范围：\(1 \le n, m \le 10^5\)，\(1 \le w_i \le 10^{100}\)。

题意描述

牛客链接（需付费）

在一个 \(2 \times 2\) 的网格上有四盏灯，每个网格一盏。这四盏灯的位置分别是左上角，右上角，左下角，右下角。

每盏灯有一个可供调节的耗电量，耗电量越高，则灯对周围提供的亮度越多。具体来说，若某一盏灯的耗电量为 \(x\)，那么它将会为自己的格子提供 \(x\) 的亮度，为相邻的两个格子提供 \(\lfloor \frac{x}{2} \rfloor\) 的亮度，为对角的格子提供 \(\lfloor \frac{x}{4} \rfloor\)。其中 \(\lfloor x \rfloor\) 表示对 \(x\) 向下取整。

某一个格子的亮度是四盏灯对它提供的亮度之和。例如左上角的灯耗电量为 \(4\)，右上角的灯耗电量为 \(7\)，右下角的灯耗电量为 \(8\)，左下角的灯耗电量为 \(0\)，那么左上角这个格子的亮度就是 \(4 + \lfloor \frac{7}{2} \rfloor + \lfloor \frac{8}{4} \rfloor + 0 = 9\)

现在我们对 四个格子的最低亮度 提出了要求，我们想要让四个格子的亮度都达到标准。你可以将每一盏灯的耗电量调节为任何一个大于等于零的整数，为了省电，你希望四盏灯的耗电量之和尽可能的小，请问 四盏灯的最小耗电量之和 是多小？

数据范围：四个格子的最低亮度均为正整数且不超过 \(1500\)。