#! https://zhuanlan.zhihu.com/p/542681315
tags:
- Codeforces
- 翻译
abbrlink: 32037
date: 2022-07-17 16:10:07
前言
今天给大家带来7.16的Codeforces Round #808 (Div. 2)翻译
感谢大家支持🤞
益题交流群：1019201086 (QQ)
作者：xyzlh
A. Difference Operations
题面翻译
你将得到一个由$n$个正整数组成的数组$a$。
你可以执行此操作任意次数（可能为零）：
选择一个索引 $i(2≤i≤n)$，并将$a_i$改为$a_i−a_{i−1}$
是否可能对所有$2≤i≤n$使得$a_i=0$？
输入格式
The input consists of multiple（多重的） test cases. The first line contains a single integer（整数） $t (1≤t≤100)$ — the number of test cases. The description of the test cases follows.
The first line contains one integer $n (2≤n≤100)$ — the length of array $a$.
The second line contains $n$ integers $a_1,a_2,…,a_n (1≤a_i≤10^9)$.
输出格式
For each test case, print “YES” (without quotes（引号）), if it is possible to change $a_i$ to 0 for all $2≤i≤n$, and “NO” (without quotes) otherwise.
You can print letters in any case (upper or lower).
样例输入
1 | 4 |
样例输出
1 | YES |
提示
In the first test case, the initial（初始的） array is $[5,10]$. You can perform 2 operations to reach the goal:
Choose $i=2$, and the array becomes $[5,5]$.
Choose $i=2$, and the array becomes $[5,0]$.
In the second test case, the initial array is $[1,2,3]$. You can perform 4 operations to reach the goal:
Choose $i=3$, and the array becomes $[1,2,1]$.
Choose $i=2$, and the array becomes $[1,1,1]$.
Choose $i=3$, and the array becomes $[1,1,0]$.
Choose $i=2$, and the array becomes $[1,0,0]$.
In the third test case, you can choose indices（索引） in the order 4, 3, 2.
B. Difference of GCDs
题面翻译
你将得到三个整数$n$,$l$和$r$。你需要构造一个数组包含$a_1,a_2,…,a_n (l≤a_i≤r)$，使得$gcd(i,a_i)$各不相同或输出没有解决方案。
这里$gcd ( x , y)$表示两个整数$x$和$y$的最大公约数 (GCD)。
输入格式
The input consists of multiple（多重的） test cases. The first line contains a single integer $t (1≤t≤10^4)$ — the number of test cases. The description of the test cases follows.
The first line contains three integers $n, l, r (1≤n≤10^5, 1≤l≤r≤10^9)$.
It is guaranteed（保证） that the sum of $n$ over all test cases does not exceed（超过） $10^5$.
输出格式
For each test case, if there is no solution, print “NO” (without quotes（引号）). You can print letters in any case (upper or lower).
Otherwise, print “YES” (without quotes). In the next line, print $n$ integers $a_1,a_2,…,a_n$ — the array you construct.
If there are multiple solutions, you may output any.
样例输入
1 | 4 |
样例输出
1 | YES |
提示
In the first test case, $gcd(1,a_1),gcd(2,a_2),…,gcd(5,a_5)$ are equal to 1, 2, 3, 4, 5, respectively（分别地）.
C. Doremy’s IQ
D. Difference Array
E. DFS Trees
F. Partial Virtual Trees
这期到这里就结束了，我们下期再见！😊
益题交流群：1019201086 (QQ)
发布时间： 2022-07-17
最后更新： 2022-07-17
本文标题： Codeforces Round #808 (Div. 2)翻译
本文链接： https://yitee.top/posts/32037.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！
