0127 第 4 场 小白入门赛/强者挑战赛

• 小白入门赛：https://www.lanqiao.cn/oj-contest/newbie-4/
• 强者挑战赛：https://www.lanqiao.cn/oj-contest/senior-4/
• 题解回放：https://www.bilibili.com/video/BV1pN4y1n7fW/

T1. 美丽的 2024【算法赛】

问题描述

小蓝刚学习完二进制知识，所以现在他对任何数字的二进制都特别感兴趣。恰好即将迎来 $2024$ 年，他想知道 $2024$ 的二进制中几个 $1$？

请你帮忙解决这个问题

输入格式

本题为填空题，无输入。

输出格式

输出一个整数表示答案。

T2. 自助餐【算法赛】

问题描述

食堂最近推出了自助取餐功能，可以通过盘子的形状自动计算费用。你参与到自助计算价格的项目工作中，视觉组的同学已经帮你通过图像识别把盘子图片转换为了字符串，你只需要计算具体的价格即可。

餐盘的费用如下表所示：

餐盘种类	yuanxing	zhengfangxing	changfangxing
价格	1	2	3
餐盘种类	sanjiaoxing	tuoyuanxing	liubianxing
价格	4	5	6

你将会得到 $n$ 个字符串，请按照价格表计算价格。

输入格式

第一行一个整数 $n$，表示盘子个数。

接下来一行 $n$ 个字符串，用空格隔开，表示不同的盘子。保证每个字符串都是题目描述中提到的六种之一。

输出格式

一行，一个整数，表示答案。

样例输入

5
yuanxing zhengfangxing changfangxing sanjiaoxing changfangxing

样例输出

13

说明

$13 = 1+2+3+4+3$

评测数据规模

对于 $100$% 的评测数据，$0 < n \leq 100$。

T3. 玩游戏【算法赛】

问题描述

小 A 和小 B 两个人在海边找到了 $n$ 个石子，准备开始进行一些游戏，具体规则如下：小 B 首先将 $n$ 个石子分成若干堆，接下来从小 A 开始小 A 和小 B 轮流取石子，每次可以任选一堆石子取走任意个，不可不取，没石子可取的输。问在最优策略的情况下，小 A 和小 B 到底谁能赢得游戏。

输入格式

一行一个整数 $n$，表示石子个数。

输出格式

一行一个字符 A 或者 B，输出 A 表示小 A 能赢得游戏，输出 B 表示小 B 能赢得游戏。

样例输入

2

样例输出

B

说明

对于 $2$ 个石子，小 B 将其分成两堆，每堆 $1$ 个石子即可获胜。

评测数据规模

对于 $25$% 的评测数据，$0 < n \leq 10$。

对于 $100$% 的评测数据，$0 < n \leq 10^9$。

T4. 乘飞机【算法赛】

问题描述

等待登机的你看着眼前有老有小长长的队伍十分无聊，你突然想要知道，是否存在两个年龄相仿的乘客。每个乘客的年龄用一个 $0$ 到 $36500$ 的整数表示，两个乘客的年龄相差 $365$ 以内就认为是相仿的。

具体来说，你有一个长度为 $n$ 的数组，每个数组元素都是一个 $0 \sim 36500$ 的整数。给出 $q$ 个二元组 $l, r$，判断数组在区间 $[l,r]$ 上是否存在两个差值小于等于 $365$ 的数，若存在输出 YES，否则输出 NO。

输入格式

第一行两个整数 $n, q$，表示乘客数和询问数。

接下来一行 $n$ 个整数，表示乘客的年龄。

接下来 $q$ 行，每行两个整数 $l, r$ 表示查询。

输出格式

$q$ 行，每行输出 YES 或者 NO，分别表示区间内存在/不存在年龄相仿的乘客。

样例输入

6 3
20 800 400 175 146 456
1 3
1 4
1 6

样例输出

NO
YES
YES

说明

对于区间 $[1,3]$，最小相邻为 $400-20 = 380 > 365$。

评测数据规模

对于 $50$% 的评测数据，$0 < n \leq 1000$。

对于 $100$% 的评测数据，$0 < n, q \leq 10^5$，$1 \leq l \leq r \leq n$。

T5. 压制二元组的总价值【算法赛】

问题描述

给定两个长度为 $N$ 的排列 $A$ 和 $B$。若一对二元组下标 $(i,j)$ 满足以下关系则被称之为压制二元组：

• $1 \leq i < j \le N$。
• $p_{A_i}<p_{A_j}$，其中 $p_{x}$ 表示值 $x$ 在数组 $B$ 中的下标。

一对压制二元组的价值被定义为 $j-i$，请你计算出所有压制二元组的价值之和。

排列的定义：长度为 $N$ 的排列表示一个长度为 $N$ 的数组，其中 $[1,N]$ 每个数都恰好出现一次。

输入格式

第一行输入一个整数 $N(1 \leq N \leq 2 \times 10^5)$ 表示排列的长度。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N$ 表示排列 $A$。

第三行输入 $N$ 个整数 $B_1,B_2,B_3,\cdots,B_N$ 表示排列 $B$。

保证 $A,B$ 是一个排列。

输出格式

输出一个整数表示答案。

样例输入

4
2 4 1 3
4 1 2 3

样例输出

7

说明

样例中有效的压制二元组有 $(1,4),(2,3),(2,4),(3,4)$，总价值为 $4-1+3-2+4-2+4-3=7$。

注意：二元组指的是下标对。

T6. 机器人【算法赛】

问题描述

在 VLN 任务中，机器人会根据当前的场景推断下一步的行为。我们将地图简化到一个编号为 $1 \sim n$ 的环上，其中编号为 $n$ 的下一个位置是编号为 $1$ 的位置。当机器人到达环上的第 $i$ 个位置时，机器人会根据其预训练参数的计算结果将会以 $p_i$ 的概率移动向下一个位置，或者以 $1 - p_i$ 的概率停在当前位置。机器人初始从环的 $1$ 号位置出发，你已知机器人通过预训练参数的计算结果（即行动的概率 $p_i$），想知道机器人最终停在每一个位置的概率以及位置之间的概率大小关系。

为了避免精度造成的问题，机器人的神经网络在输出时对 $2$ 的次幂进行了对齐，即概率 $p_i$ 均可以表示成 $2^{-k}$ 的形式。

如果有不明确之处可以结合样例解释进行理解。

为了方便进行答案检测，请将概率对 $998244353$ 取模后输出。可以被证明答案一定可以被表示成一个分数：$\frac{p}{q}$，其中 $p, q$ 的最大公因数是 $1$。当输出答案对 $M$ 取模的时候，你应该输出满足下列式子的 $x$：$0 \leq x < M, x \times q \equiv p(\bmod M)$。

输入格式

第一行一个整数 $n$，表示环的大小。

接下来一行 $n$ 个整数，$k_1, k_2, ..., k_n$，其中 $p_i = 2^{-k_i}$。

输出格式

两行，两个整数，代表答案。

原本的第一行应该是 $n$ 个整数，第 $i$ 个整数表示机器人停在位置 $i$ 的概率对 $998244353$ 取模的结果，原本的第二行应该是 $n$ 个整数，第 $i$ 个整数表示机器人停在位置 $i$ 的概率（取模之前的值）是所有位置中第几大的，如果两个位置的概率一样大，认为编号小的排在前面（更大）。为了减少输出量，我们将要求你仅输出答案数组的哈希值。对一个 $1 \sim n$ 的数组 $a$，其哈希值为 $\sum_{i=1}^{n} {i \times a_i}$ 对 $998244353$ 取模的结果。

样例输入

2
1 1

样例输出

332748119
5

说明

原本的输出第一行为 $665496236$ $332748118$，第二行为 $1$ $2$。

机器人首先从 $1$ 号点开始，以 $\frac{1}{2}$ 的概率走到 $2$，以 $\frac{1}{2}$ 的概率停下。如果走到了 $2$ 号点，以 $\frac{1}{2}$ 的概率走到 $1$，以 $\frac{1}{2}$ 的概率停下。因此可以发现停在 $1$ 号点的概率是 $\sum\limits_{n=1}^{+\infin}\frac{1}{2}^{2n-1} = \frac{2}{3}$，停在 $2$ 号点的概率是 $\sum\limits_{n=1}^{+\infin}\frac{1}{2}^{2n} = \frac{1}{3}$，故最终答案为 $665496236$ 和 $332748118$。

评测数据规模

对于 $30$% 的评测数据，$0 < n \leq 10, 0 \leq k_i \leq 5$。

对于 $100$% 的评测数据，$0 < n \leq 2 \times 10^6, 0 \leq k_i \leq 5 \times 10^6$。

T7. 终极 PK【算法赛】

问题描述

又到了终极 $\text{PK}$ 的时间来了！

给定一个长度为 $N$ 的整数数组 $A$，小蓝和小桥总共进行 $\frac{N}{2}$ 轮选数，具体的 选数规则如下：

• 对于第 $i(i\in[1,\frac{N}{2}])$ 轮选数，若 $i$ 为奇数则小蓝先手从数组中选择一个数，小桥后手选。若 $i$ 为偶数则小桥先选小蓝后选。
• 两人不能选择同一个位置的数，且每轮选数结束后将两人选择的数从 $A$ 中删除。

两人的得分计算为各自选的数之和，若两人都想最大化自己的分数，按照最佳策略进行选数。

请你计算出小蓝的最终得分和小桥的最终得分。

输入格式

第一行输入一个整数 $N(2 \leq N \leq 10^5)$ 表示 $A$ 的长度。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 10^5)$ 表示数组 $A$。

保证 $N$ 为偶数。

输出格式

输出一行两个整数，分别表示小蓝的得分和小桥的得分。

样例输入

4
3 1 2 1

样例输出

4 3

T8. 缺页异常 1【算法赛】

问题描述

你有一台拥有 $n$ 个缓存页面空间的服务器，有 $k$ 个用户在同时使用。你预知了这 $k$ 个用户将会一共给出 $m$ 条页面请求。每条请求以 $x, y$ 的形式表示，表示编号为 $x$ 的用户请求了页面 $y$。这里不同用户的相同编号页面认为是不同的。你需要在开始给每个用户分配一个固定的缓存页面空间大小 $ps_i$，满足 $\sum_{i=1}^{k}{ps_i} = n$，并且使用 OPT 页面置换算法，使得总的缺页中断次数最小。

OPT 算法的具体描述为：每次当需要访问一个页面的时候，假设当前用户持有 $n_i$ 个缓存空间，首先查询该页面是否存在 $n_i$ 个缓存页面空间中，若在，则结束；若不存在，则将该页面置入 $n_i$ 个位置的其中一个（若 $n_i=0$则不操作），并触发一次缺页中断。

置入位置的选择规则如下：如果当前空间中有空的位置（为初始状态，历史未在这个位置插入过任何页面），则选择任意一个空位置插入；否则选择当前在缓存中并且未来最久才会被访问到的页面（未来不被再访问的认为无穷久，所如果有多个，任选一个），在该页面的位置插入新页面。一个用户的初始缓存页面空间的每个位置均处在初始状态。

输入格式

本题包含多组数据。

第一行一个整数 $T$，表示数据组数。

对于每一组数据：

第一行三个整数，$n,k,m$，表示缓存页面空间，用户数，页面请求条数。

接下来 $m$ 行，每行两个整数 $x, y$ 表示一个请求。其中 $1 \leq x \leq k$。

输出格式

$T$ 行，对应 $T$ 组数据的答案，每一行一个整数，表示最小缺页次数。

样例输入

1
2 2 4
1 1
1 2
1 3
1 1

样例输出

3

说明

可以证明分配给第一个用户 $2$ 的空间，第二个用户 $0$ 的空间是最优的方案之一，在第 $1,2,3$ 次请求发生了缺页中断。

如果只给第一个用户分配 $1$ 的空间，则页面 $2$ 插入的时候根据规则会占用原本页面 $1$ 所占用的缓存空间，使得最后一次访问页面 $1$ 也发生缺页，总缺页中断次数为 $4$。

评测数据规模

对于 $30$% 的评测数据，$0 < n, k \leq 10$。

对于 $100$% 的评测数据，$0 < T \leq 3, 0 < n, k, m \leq 1000, 0 < y \leq 10^9$。

T9. 缺页异常 2【算法赛】

问题描述

你有一台拥有 $n$ 个缓存页面空间的服务器，只有 $1$ 个用户在同时使用。这个用户将会一共给出 $m$ 条页面请求。每条请求用一个整数 $y$ 表示请求了页面 $y$。请你计算出对于 $n \in [0, m]$，使用 LRU 页面置换算法的缺页中断次数是多少。

LRU 算法的具体描述为：每次当需要访问一个页面的时候，假设当前用户持有 $n_i$ 个缓存空间，首先查询该页面是否存在 $n_i$ 个缓存页面空间中，若在，则更新该页面访问时间并结束；若不存在，则将该页面置入 $n_i$ 个位置的其中一个，并记录当前访问时间，并触发一次缺页中断。

置入位置的选择规则如下：如果当前空间中有空的位置（为初始状态，历史未在这个位置插入过任何页面），则选择任意一个空位置插入；否则选择当前在缓存中并且之前最久未被访问过的页面（记录的访问时间距离现在最久），在该页面的位置插入新页面。用户的初始缓存页面空间的每个位置均处在初始状态。

输入格式

第一行一个整数，$m$，表示页面请求条数。

接下一行，$m$ 个整数，表示 $m$ 个页面请求的编号。

输出格式

一行，$m+1$ 个整数，表示当缓存大小为 $[0, m]$ 时的答案。

样例输入

6
1 3 1 2 1 1

样例输出

6 5 3 3 3 3 3

说明

当缓存大小为 $2$ 时的执行过程如下： 初始：[] 访问：[1] （缺页） 访问：[3, 1] （缺页） 访问：[1, 3] 访问：[2, 1] （缺页） 访问：[1, 2] 访问：[1, 2] 故缺页中断次数为 $3$ 次。

评测数据规模

对于 $30$% 的评测数据，$0 < m \leq 1000$。

对于 $70$% 的评测数据，$0 < m \leq 10^5$。

对于 $100$% 的评测数据，$0 < m, y \leq 10^6$。