赛题

A

U607526 「Monkey Mountine Round I」乔迁新居

题目背景

天大的喜事，游荡几十载之后，猴王找到了水帘洞！ 但是，洞口较小，不知猴族老小和辎重几次能运完。善武不通文的猴王一代广招贤才，找你算算。

题目描述

共有 \(n\) 只猴子，\(m\) 车辎重。洞口每次可以进入 \(x\) 只猴子或 \(y\) 车辎重。几次能全伙入内？

输入格式

一行，分别为 \(n\)，\(m\)，\(x\)，\(y\)。空格分开

输出格式

输出一行，即需要多少次

输入输出样例 #1

输入 #1

8 8 8 8

输出 #1

2

输入输出样例 #2

输入 #2

6 9 2 3

输出 #2

6

说明/提示

\(1<n,m,x,y\leq 2^{63}-1\)

你并不需要惊讶于洞口能这么大。世界之大，无奇不有；

B

U607527 「Monkey Mountain Round I」领土分配

题目背景

猴王伟业，英明无限！

自猴王开山之后，领土日益壮大，现今已占领花果山为中心的大量领土。为了控制手下猴群，猴王决定对山头进行分配，但是管理问题，甚是重大，特招贤才，以码力之强悍，助力猴山复兴！

题目描述

总共有 \(n\) 个山头，\(m\) 只猴子。山头序号为 \(1\) 到 \(n\)。第 \(i\) 个猴子（\(1\leq i \leq m\)）要第 \(x_i\) 个山头。给出相关数据，请输出第 \(i\) 个山头的主人的编号。

输入格式

两行。

第一行两个整数 \(n,m\)。

第二行 \(m\) 个整数，第 \(i\) 个为 \(x_i\)，表示第 \(i\) 只猴大王要第 \(x_i\) 个山头

输出格式

输出仅一行，长度为 \(n\)，第 \(i\) 个为第 \(i\) 号山头的主人的编号，空格分开。特别的，如果无主，输出 air

输入输出样例 #1

输入 #1

3 2
2 3

输出 #1

air 1 2

说明/提示

\(1\leq m \leq n \leq 10^5\)

\(1\leq x_i \leq n\)

C

U607528 「Monkey Mountine Round I」舆图修订

题目背景

猴山图册，编绘进行中……

猴山之大，无奇不有；猴土广袤，居山拥水

而制图，却制图徒甚愚钝，竟错反了两列！

题目描述

猴山地图中有两列反了，请你修改，并给出修改后的正确地图。

猴山地图有 \(n\) 行 \(m\) 列。其中 \(x\) 行和 \(y\) 列之间混了，给出错误地图，请输出正确地图。

输入格式

第一行为 \(n,m,x,y\) 。

接下来 \(n \times m\) 的矩阵，保证矩阵中所有元素为字符。

输出格式

输出一个 \(n\times m\) 的矩阵，表示修改完的地图。

输入输出样例 #1

输入 #1

5 5 2 3
*****
--*--
///==
aaaaa
23468

输出 #1

*****
-*---
///==
aaaaa
24368

说明/提示

\(1 \leq n,m \leq 10^2\)

\(1 \leq x,y \leq m\)

\(x ≠ y\)

D

U607530 「Monkey Mountine Round I」天赐良缘

题目背景

缘分，就是这样，很神奇，不可捉摸，你一伸手，哎，它就没了。

通灵的猴啊，也有自己的一段缘分呵

题目描述

猴王要测试猴山老小的缘分，选取代表性的一群猴子。

猴群中有 \(n\) 只猴子，每只猴子都有一个名字和一个性别。名字是一个字符串，性别用 \(0\) 或 \(1\) 表示。如果两只猴子性别不同，那么它们有缘。它们的缘分值可以用它们名字的相似程度来衡量。

对于两只猴子 \(a\) 和 \(b\)，它们的缘分值定义为：

• 以猴子 \(a\) 的名字字符串 \(S\) 为主串，猴子 \(b\) 的名字字符串 \(T\) 为模式串，计算 \(S\) 的每个后缀与 \(T\) 的最长公共前缀长度之和
• 以猴子 \(b\) 的名字字符串 \(T\) 为主串，猴子 \(a\) 的名字字符串 \(S\) 为模式串，计算 \(T\) 的每个后缀与 \(S\) 的最长公共前缀长度之和

这两者的和就是猴子 \(a\) 和 \(b\) 的缘分值。

整个猴群的总缘分就是所有有缘的猴子对的缘分值之和。

输入格式

第一行一个整数 \(n\)，表示猴子的数量。

接下来 \(n\) 行，每行一个字符串和一个整数，分别表示猴子的名字和性别。保证字符串非空且仅包含大小写字母和数字。

输出格式

输出一个整数，表示总缘分。

输入输出样例 #1

输入 #1

3
aaa 0
aa 1
a 0

输出 #1

11

说明/提示

猴子数量 \(n\) 满足 $ 2 ≤ n ≤ 10$

所有字符串长度之和不超过 \(2×10⁷\)

字符串仅包含大小写字母和数字

E

U607532 「Monkey Mountine Round I」猿猴衔环

题目背景

猴王正在清点手下的猴子。猴子们起初按资历深浅（编号 \(1\) 到 \(N\)）排成一圈。猴王决定用一种特别的方式来筛选身边的孩儿们。他规定了一个规则，每次从队伍中剔除特定位置的猴子，直到剩下最后一只猴子，这将作为他的警卫连战士。然而，猴群中最近有探子报告了一些猴子实力不凡，猴王便有了计策。但是显然，他的智力并不很好，还得请人给计算……………………

题目描述

现在有 \(N\) 只猴子，编号从 \(1\) 到 \(N\)，围成一个圆圈。猴王决定从当前编号为 \(1\) 的猴子开始报数，但报数的上限不再是固定的，而是由当前圈中剩余猴子的平均实力值（向下取整）决定。

具体规则如下：

1. 将猴子们按编号顺序（1, 2, 3, ..., N）排成一个圆圈。
2. 从当前的第一个猴子开始报数。
3. 报数的上限 \(M\) 是当前圈中所有猴子实力值的平均值（向下取整）。即 \(M = \lfloor \frac{\sum_{i=1}^{k} shili_i}{k} \rfloor\)，其中 \(k\) 是当前剩余的猴子数量,\(shili_i\) 是第 \(i\) 只猴子的实力。
4. 每当有猴子报数到 \(M\)，该猴子便会从队伍中离开，下一个猴子重新从 \(1\) 开始报数。
5. 猴王的最新要求是：你需要输出每一次被剔除的猴子的编号和实力值。
6. 重复过程 2~5，直到只剩下一只猴子。

输入格式

第一行，一个整数 \(N\)，表示初始猴子的数量。
接下来 \(N\) 行，每行一个整数。第 \((i+1)\) 行的整数 \(S_i\) 表示编号为 \(i\) 的猴子的实力值。

输出格式

输出共 \(N-1\) 行，每行包含两个整数，依次表示每次被剔除的猴子的编号和实力值。
最后一行输出一个整数，表示最后剩下的猴子的编号

输入输出样例 #1

输入 #1

5
10
20
5
15
25

输出 #1

3 5
1 10
5 25
2 20
4

说明/提示

\(1 \leq N \leq 1000\)，\(1 \leq S_i \leq 100000\)。

F

U607533 「Monkey Mountine Round I」与时俱进

题目背景

若想猴山发展好，新型科技不能少

这不是嘛，猴王购置了个机器人玩，玩腻了给机灵的猴子拆解了研究去（毕竟，现在猴山除了武器之外，没啥先进货，猴山创收厂由于技术落后，生意也不咋地）。言归正传哈，这机器人也会坏的，还得算算给它个指令跑，会不会坏。于是，完美的，又得请人给算了……

此刻的猴王：

题目描述

机器人接受一系列指令，指令由四种字符组成：R, B, r, b。其中：

• R 表示红色前进
• B 表示蓝色前进
• r 表示红色后退
• b 表示蓝色后退

机器人从起点开始，按顺序执行指令。当执行后退指令（r 或 b）时，它必须与最近的前进指令（R 或 B）颜色相同（即 r 对应 R，b 对应 B），否则机器人将发生故障。请注意，后退指令总是与最近的前进指令匹配，且匹配后该前进指令被消耗。

请判断机器人在执行所有指令过程中是否会发生故障。如果发生故障，输出 No，否则输出 Yes。

输入格式

一行字符串 $ s $，表示指令序列，字符串只包含 R, B, r, b 四种字符。

输出格式

一行，"Yes" 或 "No"，表示是否发生故障。

输入输出样例 #1

输入 #1

RBrb

输出 #1

No

输入输出样例 #2

输入 #2

RBbr

输出 #2

Yes

说明/提示

字符串长度 \(n\) 满足 $ 1 \leq n \leq 10^4 $。

G

U607873 「Monkey Mountine Round I」科技脱贫

题目背景

猴山创收厂在研究了大量的科技书籍和科技产物之后，突然有一批猴子开窍了，他们懂得了大道理，科学的道理。同样的，他们也懂得了赚钱的道理。

他们找到了金库，求拨款......这可是个大项目，给全山上猴子高兴的不行。但是需要请人给当核心程序员，毕竟，猴子不怎么会思考啊！

在“MKK通讯网络”项目中，我们需要处理从多个深空探测器传回的数据包。这些数据包通过一个高延迟的卫星中继站传输。由于卫星带宽有限，它只能同时处理一个数据包，并严格按照“先到先得”的原则进行转发。猴山控制中心需要实时监控数据包的排队情况，并可能跳过一些重复或低优先级的数据包。

——猴山创收厂汇报员上猴王书

题目描述

你作为地面控制中心的核心逻辑员，需要编写一个核心逻辑来模拟卫星中继站的操作。你需要处理以下三种指令：

1. SEND [PacketID]：表示一个编号为 [PacketID] 的数据包抵达卫星，并进入等待队列的末尾。PacketID 是一个由大小写字母和数字组成的字符串。
2. QUERY：查询当前正在被卫星处理（即队列最前端）的数据包编号。如果队列为空，则输出 “Not Found”（不含引号）。
3. SKIP：跳过当前正在处理的数据包。卫星将立即开始处理队列中的下一个数据包（如果存在）。如果队列为空，则此指令无效。

你的任务是正确模拟这一过程，并对每个 QUERY 指令输出相应的结果。

输入格式

从标准输入读入数据。

第一行包含一个整数 \(N\) (\(1 \le N \le 10^5\))，表示指令的总数。

接下来 \(N\) 行，每行一个指令。指令格式仅为上述三种之一。SEND 指令的格式保证为 SEND 后跟一个空格，再跟数据包编号。

输出格式

对于每个 QUERY 指令，输出一行，表示查询的结果。

输入输出样例 #1

输入 #1

11
SEND DataPacket1
QUERY
SEND DataPacket2_Alpha
QUERY
SKIP
QUERY
SKIP
QUERY
SKIP
QUERY
SEND FinalPacket

输出 #1

DataPacket1
DataPacket1
DataPacket2_Alpha
Not Found
Not Found

说明/提示

\(1 \le N \le 10^5\)，[PacketID] 的长度不超过 \(20\)，且仅包含大小写字母和数字。

H

U607880 「Monkey Mountine Round I」猴山有木

题目背景

科技项目蒸蒸日上，终于有点正当钱了，真好！

但是，

树高千尺不忘根，人行万里不忘本

不忘初心，方得始终。

猴王要搞种植业。种果树，自己有果子吃，还能卖果子赚钱。真好。

猴山是个人杰地灵的好地方，山中盆地里有一颗神树，它很奇怪，你道它怎么着：

猴山秘境幽，丹树碧云浮

老君种玄丹，杨枝洒露稠

叶叠千重秀，果生万象周

根深通九地，冠妙映三洲

三载垂芳后，长生共鹤俦

猴王精心栽培，帮助其繁殖，于是有了一个果园。

在猴子滋养下，果子一年半一熟了！

但是，一年半只是能够采摘食用，生长时间越久质量越好。商人来买果子的时候，猴王要挑选现在价值最大的树采摘，剩下的留着继续长。可是谁会算那么大的树的收益嘛，还请 OIer 给算吧……

题目描述

猴山果园中有 \(n\) 棵树。每棵果树由多个节点组成，每个节点上结有一个果子，果子价值用一个整数表示。每棵果树有一个根节点（编号为0），每个节点最多有两个分支（左分支和右分支）。

猴子采用以下方式采摘：

• 先采摘左分支上的所有果子
• 然后采摘当前节点的果子
• 最后采摘右分支上的所有果子

货郎要求采摘的果子序列必须按照价值非递减的顺序排列（即从小到大排列，允许相等），否则拒绝购买。

猴子从满足货郎要求的果树中采摘总价值最大的那一棵。如果有多棵满足条件且总价值相同，选择最先出现的那一棵。

请帮助猴子判断哪棵果树满足条件。

输入格式

第一行一个整数 \(n\)，表示果树的数量。

接下来逐行输入每棵果树的信息：
对于每棵果树，第一行一个整数 \(m\)，表示果树的节点数。
接下来 \(m\) 行，每行包含三个整数 \(p\), \(l\), \(r\)，表示每个节点的果子价值、左分支节点编号、右分支节点编号。其中节点编号按输入顺序从 \(0\) 开始编号，如果左分支或右分支不存在，则用 \(-1\) 表示。

输出格式

如果存在满足条件的果树，输出一行两个整数：果树编号（从 \(0\) 开始）和总价值，中间用空格隔开。否则输出 -1。

输入输出样例 #1

输入 #1

1
3
2 1 2
1 -1 -1
3 -1 -1

输出 #1

0 6

说明/提示

\(1 ≤ n ≤ 10\)

\(1 ≤ m ≤ 1000\)

$-1000 ≤ p ≤ 1000 $

根节点总是节点 \(0\)

树很大，所以并不需要很多，并且，这也不是猴山唯一的创收途径。

I

U608362 「Monkey Mountine Round I」果熟燕尔

题目背景

“燕尔”意为安乐，“宴尔新昏”为其原始表述，源自《诗经》诗句“宴尔新昏，如兄如弟”，其中“宴”通“燕”，“昏”通“婚”。

——百度百科

对于猴子来说，没有什么比神树的果子熟了更令人欣喜的了。

怎么个事，甭急，且听我细细道来。神树太难熟了，长太慢了，于是猴子们研究基因技术，编辑神树基因，反复培育，培育出了新神树品种。这个树好啊，果子五年一熟，但是熟了之后可以采摘数次，也就是说，采摘干净之后，只需要一天时间，它就能再长满熟透的果子，但是数量是上一次的二分之一，直到再除二等于零的时候，就是一季果子采完了。所以，每隔五年，果子成熟，开长生果宴，全山庆祝。欢歌数日不绝。今年，是第10次果子成熟，猴王打算这次不卖了，开盛宴，山上猴子分吃所有果子。不管咋样，得算算能采多少果子吧……同样的，高智商的你帮着算吧，猴王算是算不明白了……

题目描述

种植了 \(n\) 棵杂交神树，每棵神树初始有 \(a_i\) 个果子。猴子们要举办 \(K\) 天的宴会。每天，猴子们会选择当前果子最多的神树，摘取所有果子用于宴会。摘取后，该神树会重新长出果子，新果子数等于摘取果子数的一半（向下取整）。如果摘取后果子数为零，则这段时间内不再长出果子。

请计算 \(K\) 天后，猴子们一共摘了多少果子。

输入格式

第一行两个整数 \(n\), \(K\)，表示果树数量和天数。
第二行 \(n\) 个整数，第 \(i\) 个为 \(a_i\) ，表示每棵果树的初始果子数。

输出格式

输出一个整数，表示总摘果数。

输入输出样例 #1

输入 #1

3 2
1 2 3

输出 #1

5

说明/提示

\(1 ≤ n ≤ 10^5\)

\(1 ≤ K ≤ 10^5\)

\(1 ≤ a_i ≤ 10^9\)

J

U609027 「Monkey Mountine Round I」占山为王

题目背景

猴山辖区内众山林立，每座山都有一个猴子首领。但是太分散了就像历史学的诸侯国似的，容易造反。猴王决定，对于任意一段连续山脉，最高的那座山的头领就是该段的山长，山长经过仔细的洗脑，政治正确，不会反叛。但是山系众多，猴王的脑子炸了不提，得，你给算吧……

题目描述

给出猴山下所有的山的数据，每座山有一个高度。接下来有 \(M\) 个查询，每个查询给出一个区间 \([L, R]\)，表示一段山脉。对于每个查询，请给出该区间内最高的山的高度（即山长的高度）。

输入格式

第一行输入两个整数 \(N\) 和 \(M\)，分别表示山的数量和查询的数量。
第二行输入 \(N\) 个整数 \(H_i\)，表示每座山的高度。
接下来 \(M\) 行，每行输入两个整数 \(L\) 和 \(R\)，表示山脉的起点和终点（从1开始索引）。

输出格式

输出 \(M\) 行，每行一个整数，表示对应查询区间内的最高山高。

输入输出样例 #1

输入 #1

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

输出 #1

3
5
5

说明/提示

\(1 ≤ N ≤ 10^5，1 ≤ M ≤ 10^6\)

\(1 ≤ H_i ≤ 10^9\)

\(1 ≤ L ≤ R ≤ N\)

K

U609041 「Monkey Mountine Round I」刨根问底

题目背景

生活安宁了，开始思索了。

一群猴子找到猴王问祖宗。祖宗，无非就是和猴王一块征战的亲信。但是猴山记录较少，只能靠一条条关系理祖宗，有时候还得复查，脑子不得炸了嘛。脑力不好的猴王，唉……

猴王：

题目描述

\(n\) 只猴子要查询他的祖宗，编号从 \(1\) 到 \(n\)。每只猴子都有一个直接父亲，但父亲可能还有父亲，如此追溯下去，最终会有一只猴子是猴王征战四方时的亲信，它就是这只猴子的祖宗。猴王逐步给猴子们明确关系，猴王有以下两种行为：

• 确认父子关系：猴子 \(a\) 的父亲是猴子 \(b\)。
• 询问祖宗：询问猴子 \(a\) 的祖宗是谁。

由于年代久远，猴子们可能会重复确认已知的父子关系，但不会出现矛盾（即同一只猴子的父亲不会改变）。初始时，每只猴子都不知道自己的父亲，因此祖宗默认是自己（可能吗？没准呢，长寿的呗）。

输入格式

第一行包含两个整数 \(n\) 和 \(m\)，分别表示猴子的数量和操作的数量。
接下来 \(m\) 行，每行描述一个操作，格式如下：

• 1 a b：表示确认猴子 \(a\) 的直接父亲是猴子 \(b\)。
• 2 a：询问猴子 \(a\) 的祖宗编号。

输出格式

对于每个询问操作（2 a），输出一行，包含一个整数，表示猴子 \(a\) 的祖宗编号。

输入输出样例 #1

输入 #1

5 10
2 1
1 1 2
2 1
1 2 3
2 1
2 2
1 4 5
2 4
1 5 3
2 4

输出 #1

1
2
3
3
5
3

说明/提示

\(1 \leq n, m \leq 10^5\)

（\(1 \leq a, b \leq n\), \(a \neq b\)）

L

U609044 「Monkey Mountine Round I」时年几何

题目背景

祖宗查清了查年纪。

猴子多高寿，年龄不知晓。

新投奔的猴子找猴王报备年龄，老猴子问自己活了多少年了。一时间，混乱无比。

你经过前几题的重重考验，便应当是贵人了，施舍些个智慧，帮帮吧，ཨོཾ་མ་ཎི་པདྨེ་ཧཱུྃ。

题目描述

有 \(n\) 只猴子来问。每只猴子要不然是新来的报备，要不然是老头子查年纪。

输入格式

第一行包含一个正整数 \(n\)，表示操作的数量。
接下来 \(n\) 行，每行描述一个操作，操作分为两种类型：

• Add [name] [age]：添加一只名字为 name 年龄为 age 的猴子。如果猴山中已经存在名字为 name 的猴子，则忽略此次操作。
• Query [name]：查询名字为 name 的猴子的年龄。如果猴山中存在该猴子，则输出其年龄；否则输出 Not found。

输出格式

对于每个 Query 操作，输出一行结果。

输入输出样例 #1

输入 #1

6
Add MonkeyKing 1000
Add Wukong 500
Query MonkeyKing
Add MonkeyKing 2000
Query MonkeyKing
Query SunWukong

输出 #1

1000
1000
Not found

说明/提示

$ n \leq 100000 $

每个名字由小写字母组成，长度不超过 10。

年龄是正整数且不超过 1000。