#! https://zhuanlan.zhihu.com/p/542494145
tags:
- Codeforces
- 翻译
abbrlink: 39924
date: 2022-07-16 16:08:03
前言
今天给大家带来7.15的Codeforces Round #807 (Div. 2)翻译及题解
感谢大家支持🤞
益题交流群：1019201086 (QQ)
作者：xyzlh
A. Mark the Photographer
题面翻译
Mark被要求给$2n$个人合影，第$i$个人的身高为$h_i$。
为了拍好合影，他将这些人分成了前排和后排这两行，每行有$n$个人。但为了保证每个人都能被看见，后排的第$j(1\leq j \leq n)$个人必须至少比前排的第$j$个人高$x$。
现在请你帮助Mark判断是否可能。
输入格式
第一行包含一个整数$t(1 \leq t \leq 100)$,表示测试用例的数量。每次测试用例包括两行。
每个测试用例的第一行包含两个正整数$n$和$x (1≤n≤100, 1≤x≤10^3)$，分别表示每行的人数和 Mark 想要的最小差异。
每个测试用例的第二行包含$2n$个正整数$h_1,h_2,…,h_{2n} (1≤h_i≤10^3)$，分别表示合影队伍里每个人的身高。
请注意，总和$n$在所有测试用例中是没有界限的。
输出格式
对于每个测试用例，如果 Mark 可以安排满足他条件的人，则打印一行包含“ YES ”，否则打印“ NO ”。
您可以以任何形式打印每个字母（例如，YES、Yes、yes、yEs都将被识别为肯定答案）。
样例输入
1 | 3 |
样例输出
1 | YES |
提示
在第一个测试用例中，一个可能的顺序是让第三、第五和第六人在后排，第二、第一和第四人在前排。如下表：
后排 9 12 16
前排 3 1 10
它满足条件，因为
- $h_3−h_2=9−3≥6$
- $h_5−h_1=12−1≥6$
- $h_6−h_4=16−10≥6$
在第二个测试用例中，可以证明无法以满足条件的方式对人员进行排序。
在第三个测试用例中，满足条件的唯一安排是让第一个人在后排，第二个人在前排。
B. Mark the Dust Sweeper
题面翻译
Mark正在打扫一排$n$个房间。第$i$个房间有一个非负的灰尘量$a_i$。他有一台神奇的清洁机，可以做到以下三步操作。
- 选择两个指数$i<j$，使灰尘量$a_i，a_{i+1}，…，a_{j−1}$都大于0
- 将$a_i$设置为$a_i-1$
- 将$a_j$设置为$a_j+1$
Mark的目标是使$a_1=a_2=…=a_{n−1}=0$，这样他才能更好地打扫第$n$个房间。请你确定实现其目标所需的最少操作次数。
输入格式
The first line contains a single integer（整数） $t (1≤t≤10^4)$ — the number of test cases.
The first line of each test case contains a single integer $n (2≤n≤2⋅10^5)$ — the number of rooms.
The second line of each test case contains $n$ integers $a_1, a_2, …, a_n (0≤a_i≤10^9)$ — the dust level of each room.
It is guaranteed(保证) that the sum of $n$ across all test cases does not exceed $2⋅10^5$.
输出格式
For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of（一系列） operations that meets the goal.
样例输入
1 | 4 |
样例输出
1 | 3 |
提示
In the first case, one possible sequence of operations is as follows.
Choose $i=1$ and $j=2$, yielding the array $[1,1,0]$.
Choose $i=1$ and $j=3$, yielding the array $[0,1,1]$.
Choose $i=2$ and $j=3$, yielding the array $[0,0,2]$.
At this point, $a_1=a_2=0$, completing the process.
In the second case, one possible sequence of operations is as follows.
Choose $i=4$ and $j=5$, yielding the array $[0,2,0,1,1]$.
Choose $i=2$ and $j=3$, yielding the array $[0,1,1,1,1]$.
Choose $i=2$ and $j=5$, yielding the array $[0,0,1,1,2]$.
Choose $i=3$ and $j=5$, yielding the array $[0,0,0,1,3]$.
Choose $i=4$ and $j=5$, yielding the array $[0,0,0,0,4]$.
In the last case, the array already satisfies the condition.
C. Mark and His Unfinished Essay
题面翻译
一天晚上，Mark意识到明天有一篇论文要交。他还没写任何东西，所以Mark决定从提示中随机复制粘贴子字符串来完成这篇论文。
更正式地说，提示是一个初始长度为$n$的字符串$s$。Mark将对这个字符串进行$c$次复制粘贴操作。每次操作将给出两个整数$l$和$r$，这意味着Mark将添加字母$s_l,s_{l + 1}…s_r$到字符串$s$的末尾。注意每次操作后$s$的长度会增加。
当然，Mark要能看到他写的内容。每次复制以后，Mark将给出$q$次询问：给定一个整数k，试确定最终字符串s的第k个字母。
输入格式
The first line contains a single integer（整数） $t(1≤t≤1000)$ — the number of test cases.
The first line of each test case contains three integers $n, c, $and $ q (1≤n≤2⋅10^5, 1≤c≤40, 1≤q≤10^4)$ — the length of the initial（初始的） string s, the number of copy-pasting operations, and the number of queries（询问）, respectively（分别地）.
The second line of each test case contains a single string $s$ of length $n$. It is guaranteed（保证） that $s$ only contains lowercase（小写） English letters.
The following $c$ lines describe the copy-pasting operation. Each line contains two integers $l$ and $r (1≤l≤r≤10^{18})$. It is also guaranteed that $r$ does not exceed the current length of $s$.
The last $q$ lines of each test case describe the queries. Each line contains a single integer $k (1≤k≤10^{18})$. It is also guaranteed that $k$ does not exceed（超过） the final length of $s$.
It is guaranteed that the sum of $n$ and $q$ across all test cases does not exceed $2⋅10^5$ and $10^4$, respectively.
输出格式
For each query, print the $k$-th letter of the final string $s$.
样例输入
1 | 2 |
样例输出
m
a
r
e
a
r提示
In the first test case, the copy-paste process is as follows.
The first step is pasting string mark at the end, yielding（产生） the string markmark.
The second step is pasting string mar at the end, yielding the string markmarkmar.
The third step is pasting string rkmark at the end, yielding the string markmarkmarrkmark.
In the second test case, the copy-paste process is as follows.
The first step is pasting string re at the end, yielding the string creamiire.
The second step is pasting string ea at the end, yielding the string creamiireea.
The third step is pasting string reamiire at the end, yielding the string creamiireeareamiire.
D. Mark and Lightbulbs
E. Mark and Professor Koro
F. Mark and the Online Exam
这期到这里就结束了，我们下期再见！😊
益题交流群：1019201086 (QQ)
发布时间： 2022-07-16
最后更新： 2022-07-17
本文标题： Codeforces Round #807 (Div. 2)翻译及题解
本文链接： https://yitee.top/posts/18831.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！
