题意描述

洛谷链接

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

题意描述

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 获胜。若两人均按最优策略决策，求出最终的获胜方。