寄

省流

代码

题面

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

题意描述

Codeforces 链接

有一个 \(n\) 个数的排列 \(a\) 和一个数 \(k (0 \le k \le n)\)，你计算出了一个有 \(n\) 个数的序列 \(b\)，计算方法如下：

• 当 \(a_i \le k\) 时，若存在 \(a_j > k (1 \le j < i)\) 且 \(i - j\) 最小，则 \(b_{a_i} = a_j\)，否则 \(b_{a_i} = n + 1\)；
• 当 \(a_i > k\) 时，若存在 \(a_j \le k (1 \le j < i)\) 且 \(i - j\) 最小，则 \(b_{a_i} = a_j\)，否则 \(b_{a_i} = 0\)。

目前你知道 \(b\) 与 \(n\)，请求出任意一种 \(a\) 及对应的 \(k\)。

题意描述

Codeforces 链接

Alice 和 Bob 玩一个游戏，这个游戏中有一个有 \(n\) 项的序列 \(a\)，Alice 先手，两人轮流在 \(a\) 中取走一个数。若最终取完后 Alice 取走的数的和为偶数则 Alice 获胜，否则 Bob 获胜。若两人均按最优策略决策，求出最终的获胜方。

题意描述

洛谷链接

LibreOJ 链接

Sylvia 是一个热爱学习的女孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有 \(n \times m\) 名学生，方阵的行数为 \(n\)，列数为 \(m\)。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中 的学生从 \(1\) 到 \(n \times m\) 编上了号码。即：初始时，第 \(i\) 行第 \(j\) 列 的学生的编号是 \((i-1)\times m + j\)。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了 \(q\) 件这样的离队事件。每一次离队事件可以用数对 \((x,y) (1 \le x \le n, 1 \le y \le m)\) 描述，表示第 \(x\) 行第 \(y\) 列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：

1. 向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条 指令之后，空位在第 \(x\) 行第 \(m\) 列。

2. 向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条 指令之后，空位在第 \(n\) 行第 \(m\) 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 \(n\) 行 第 \(m\) 列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学 的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。