[Codeforces ROUND 991 Div.3] 1205

CatIsNotFound 随时更新
  2024-12-06 12:07:26 2024-12-06 12:07:26 创建   2024-12-06 12:07:26 2024-12-06 12:07:26 更新      
官方题单

A. Line Breaks

time limit per test: 1 second

memory limit per test: 256 megabytes

题解

题目

Kostya has a text consisting of words made up of Latin alphabet letters. He also has two strips on which he must write the text. The first strip can hold characters, while the second can hold as many as needed.

Kostya must choose a number and write the first words from on the first strip, while all the remaining words are written on the second strip. To save space, the words are written without gaps, but each word must be entirely on one strip.

Since space on the second strip is very valuable, Kostya asks you to choose the maximum possible number such that all words fit on the first strip of length .

科斯佳（Kostya）有一段文本 ，它由 个由拉丁字母组成的单词构成。他还有两张纸条，必须把这段文本写在这两张纸条上。第一张纸条能容纳 个字符，而第二张纸条则能容纳任意数量的字符。

科斯佳必须选择一个数字 ，并将文本 中的前 个单词写在第一张纸条上，而其余所有单词则写在第二张纸条上。为了节省空间，单词之间不留空格书写，但每个单词必须完整地写在一张纸条上。

由于第二张纸条上的空间非常宝贵，科斯佳请你选择最大可能的数字 ，使得所有单词 都能写在长度为 的第一张纸条上。

样例

INPUT

The first line contains an integer — the number of test cases.

The first line of each test case contains two integers and ; — the number of words in the list and the maximum number of characters that can be on the first strip.

The next lines contain one word of lowercase Latin letters, where the length of does not exceed .

OUTPUT

For each test case, output the maximum number of words such that the first words have a total length of no more than .

输入

第一行包含一个整数 ： 测试用例数。

每个测试用例的第一行包含两个整数 和 ； ： 列表中的字数和第一条上的最大字符数。

接下来的 行包含一个由小写拉丁字母组成的单词 ，其中 的长度不超过 。

输出

对于每个测试用例，输出最大字数 ，使得前 个字的总长度不超过 。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
5
3 1
a
b
c
2 9
alpha
beta
4 12
hello
world
and
codeforces
3 2
ab
c
d
3 2
abc
ab
a
1
2
3
4
5
1
2
2
1
0

B. Transfusion

time limit per test: 2 seconds

memory limit per test: 256 megabytes

题解

题目

You are given an array of length . In one operation, you can pick an index from to inclusive, and do one of the following actions:

  • Decrease by , then increase by .
  • Decrease by , then increase by .

After each operation, all the values must be non-negative. Can you make all the elements equal after any number of operations?

给定一个长度为 的数组 。在一次操作中，你可以从包含两端的索引范围为 到 中选取一个索引 ，并执行以下操作之一：

  • 将 减 1，然后将 加 1。
  • 将 减 1，然后将 加 1。

在每次操作之后，所有的值都必须是非负的。经过任意次数的操作后，你能否使所有元素都相等呢？

样例

INPUT

First line of input consists of one integer — the number of test cases.

First line of each test case consists of one integer .

Second line of each test case consists of integers .

It is guaranteed that the sum of of all test cases doesn’t exceed .

OUTPUT

For each test case, print "YES" without quotation marks if it is possible to make all the elements equal after any number of operations; otherwise, print "NO" without quotation marks.

You can print answers in any register: "yes", "YeS", "nO" — will also be considered correct.

输入

第一行输入包括一个整数 - 测试用例数。

每个测试用例的第一行由一个整数 组成。

每个测试用例的第二行由 个整数 组成。

保证所有测试用例的 之和不超过 。

输出

对于每个测试用例，如果经过任意次数的运算后可以使所有元素相等，则打印 “YES”，不加引号；否则，打印 “NO”，不加引号。

您可以在任何寄存器中打印答案： “yes”、“YeS”、“nO” - 也会被认为是正确的。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
8
3
3 2 1
3
1 1 3
4
1 2 5 4
4
1 6 6 1
5
6 2 1 4 2
4
1 4 2 1
5
3 1 2 1 3
3
2 4 2
1
2
3
4
5
6
7
8
YES
NO
YES
NO
YES
NO
NO
NO

C. Uninteresting Number

time limit per test: 2 seconds

memory limit per test: 256 megabytes

题解

题目

You are given a number with a length of no more than .

You can perform the following operation any number of times: choose one of its digits, square it, and replace the original digit with the result. The result must be a digit (that is, if you choose the digit , then the value of must be less than ).

Is it possible to obtain a number that is divisible by through these operations?

给定一个长度不超过 的数字 。

你可以任意多次执行以下操作：选择它的其中一位数字，将其平方，然后用所得结果替换原来的数字。结果必须是一位数字（也就是说，如果你选择数字 ，那么 的值必须小于 10）。

通过这些操作，是否有可能得到一个能被 9 整除的数字呢？

样例

INPUT

The first line contains an integer — the number of test cases.

The only line of each test case contains the number , without leading zeros. The length of the number does not exceed .

It is guaranteed that the sum of the lengths of the numbers across all test cases does not exceed .

OUTPUT

For each test case, output "YES" if it is possible to obtain a number divisible by using the described operations, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

输入

第一行包含一个整数 –测试用例数。

每个测试用例的唯一一行包含数字 ，不含前面的零。数字长度不超过 。

保证所有测试用例的数字长度之和不超过 。

输出

对于每个测试用例，如果可以通过所述操作得到一个能被 整除的数，则输出“yes”，否则输出`“no”。

您可以以任何大小写（小写或大写）输出每个字母。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES”将被视为肯定答案。

示例

1
2
3
4
5
6
7
8
9
10
9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632
1
2
3
4
5
6
7
8
9
NO
YES
YES
NO
NO
YES
NO
YES
YES

D. Digital string maximization

time limit per test: 2 seconds

memory limit per test: 256 megabytes

题解

题目

You are given a string , consisting of digits from  to . In one operation, you can pick any digit in this string, except for  or the leftmost digit, decrease it by , and then swap it with the digit left to the picked.

For example, in one operation from the string , you can get  or .

Find the lexicographically maximum string you can obtain after any number of operations.

给定一个字符串 ，它由 0 到 9 的数字组成。在一次操作中，你可以选取这个字符串中除了 0 或者最左边的数字之外的任意一个数字，将其减 1，然后将它与所选数字左边的那个数字进行交换。

例如，对字符串 进行一次操作后，你可以得到 或者 。

求出经过任意次数的操作后，你所能得到的按字典序最大的字符串。

样例

INPUT

The first line of the input consists of an integer    — the number of test cases.

Each test case consists of a single line consisting of a digital string  , where  denotes the length of . The string does not contain leading zeroes.

It is guaranteed that the sum of  of all test cases doesn’t exceed .

OUTPUT

For each test case, print the answer on a separate line.

输入

输入的第一行是一个整数 - 测试用例的数量。

每个测试用例由一行数字字符串 组成，其中 表示 的长度。字符串不包含前导零。

保证所有测试用例的 之和不超过 。

输出

对于每个测试用例，每一行输出一个单独的答案。

示例

1
2
3
4
5
6
7
6
19
1709
11555
51476
9876543210
5891917899
1
2
3
4
5
6
81
6710
33311
55431
9876543210
7875567711

示例解释

In the first example, the following sequence of operations is suitable: 19 → 81.

In the second example, the following sequence of operations is suitable: 1709 → 1780 → 6180 → 6710.

In the fourth example, the following sequence of operations is suitable: 51476 → 53176 → 53616 → 53651 → 55351 → 55431.

在第一个例子中，以下操作顺序是合适的： 19 → 81.

在第二个例子中，以下运算顺序是合适的： 1709 → 1780 → 6180 → 6710.

在第四个例子中，适合采用以下运算顺序： 51476 → 53176 → 53616 → 53651 → 55351 → 55431.

E. Three Strings

time limit per test: 2.5 seconds

memory limit per test: 256 megabytes

题解

题目

You are given three strings: , , and , consisting of lowercase Latin letters. The string  was obtained in the following way:

  1. At each step, either string  or string  was randomly chosen, and the first character of the chosen string was removed from it and appended to the end of string , until one of the strings ran out. After that, the remaining characters of the non-empty string were added to the end of .
  2. Then, a certain number of characters in string  were randomly changed.

For example, from the strings a=abra and b=cada, without character replacements, the strings caabdraa, abracada, acadabra could be obtained.

Find the minimum number of characters that could have been changed in string .

给定三个字符串：、 和 ，它们均由小写拉丁字母组成。字符串 是通过以下方式得到的：

  1. 在每一步中，随机选择字符串 或者字符串 ，将所选字符串的第一个字符从该字符串中移除，并添加到字符串 的末尾，直到其中一个字符串中的字符被取完为止。之后，将非空字符串中剩余的字符添加到 的末尾。
  2. 然后，字符串 中的若干字符被随机更改了。

例如，对于字符串 abra 和  cada，在不进行字符替换的情况下，可能会得到诸如  caabdraa 、abracada、acadabra 这样的字符串。

求出字符串 中可能被更改的最少字符数量。

样例

INPUT

The first line of the input contains a single integer   — the number of test cases.

The first line of each test case contains one string of lowercase Latin letters   — the first string, where  denotes the length of string .

The second line of each test case contains one string of lowercase Latin letters   — the second string, where  denotes the length of string .

The third line of each test case contains one string of lowercase Latin letters   — the third string.

It is guaranteed that the sum of  across all test cases does not exceed . Also, the sum of  across all test cases does not exceed .

OUTPUT

For each test case, output a single integer — the minimum number of characters that could have been changed in string .

输入

输入的第一行包含一个整数 - 测试用例数。

每个测试用例的第一行包含一个小写拉丁字母字符串 - 第一个字符串，其中 表示字符串 的长度。

每个测试用例的第二行包含一个小写拉丁字母字符串 - 第二字符串，其中 表示字符串 的长度。

每个测试用例的第三行包含一个小写拉丁字母字符串 - 第三字符串。

保证所有测试用例中 的总和不超过 。同时，所有测试用例中的 之和不超过 。

输出

对于每个测试用例，输出一个整数： 字符串 中可能被更改的最少字符数。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
7
a
b
cb
ab
cd
acbd
ab
ba
aabb
xxx
yyy
xyxyxy
a
bcd
decf
codes
horse
codeforces
egg
annie
egaegaeg
1
2
3
4
5
6
7
1
0
2
0
3
2
3

F. Maximum modulo equality

time limit per test: 5 seconds

memory limit per test: 256 megabytes

题解

题目

You are given an array  of length  and  queries , .

For each query, find the maximum possible , such that all elements  are equal modulo . In other words, , where — is the remainder of division  by . In particular, when  can be infinite, print .

给定一个长度为 的数组以及 个查询，每个查询包含 和 两个参数。

对于每个查询，找出最大可能的 ，使得所有元素 、、、对取模的结果都相等。换句话说，，其中   表示 除以 的余数。特别地，当 可以为无穷大时，输出 。

样例

INPUT

The first line contains a single integer  — the number of test cases.

The first line of each test case contains two integers ,  — the length of the array and the number of queries.

The second line of each test case contains  integers  — the elements of the array.

In the following  lines of each test case, two integers ,  are provided  — the range of the query.

It is guaranteed that the sum of  across all test cases does not exceed , and the sum of  does not exceed .

OUTPUT

For each query, output the maximum value  described in the statement.

输入

第一行包含一个整数 —— 测试用例数。

每个测试用例的第一行包含两个整数 , —— 数组长度和查询次数。

每个测试用例的第二行包含 整数 —— 数组的元素。

在每个测试用例的下面 行中，提供了两个整数 、 ——查询范围（）。

保证所有测试用例中的 之和不超过 ，而 之和不超过 。

输出

对于每个查询，输出语句中描述的最大值 。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
5 5
5 14 2 6 3
4 5
1 4
2 4
3 5
1 1
1 1
7
1 1
3 2
1 7 8
2 3
1 2
1
2
3
3 1 4 1 0 
0 
1 6

示例解释

In the first query of the first sample, . It can be shown that for greater , the required condition will not be fulfilled.

In the third query of the first sample, . It can be shown that for greater , the required condition will not be fulfilled.

在第一个示例的第一个查询中， 。可以证明，对于更大的 ，将满足所需的条件。

在第一个示例的第三个查询中， 。可以证明，对于更大的 ，将满足所需的条件。

G. Tree Destruction

time limit per test: 2 seconds

memory limit per test: 256 megabytes

题解

题目

Given a tree∗ with  vertices. You can choose two vertices  and  once and remove all vertices on the path from  to , including the vertices themselves. If you choose , only one vertex will be removed.

Your task is to find the maximum number of connected components† that can be formed after removing the path from the tree.

∗ A tree is a connected graph without cycles.

† A connected component is a set of vertices such that there is a path along the edges from any vertex to any other vertex in the set (and it is not possible to reach vertices not belonging to this set)

给定一棵有 个顶点的树∗。你可以一次性选择两个顶点 和 ，并移除从到路径上的所有顶点（包括这两个顶点本身）。如果选择 ，则只会移除一个顶点。

你的任务是找出从这棵树中移除该路径后，所能形成的连通分量†的最大数量。

∗ 树是一种无环的连通图。

† 连通分量是一组顶点的集合，在这个集合中，从任意一个顶点沿着边都能到达集合内的任意其他顶点（并且无法到达不属于这个集合的顶点）。

样例

INPUT

The first line of the input contains one integer  — the number of test cases.

The first line of each test case contains one integer  — the size of the tree.

The next n−1 lines contain two integers u and  — the vertices connected by an edge. It is guaranteed that the edges form a tree.

It is guaranteed that the sum of  across all test cases does not exceed .

OUTPUT

For each test case, output one integer — the maximum number of connected components that can be achieved using the described operation.

输入

输入的第一行包含一个整数 ： 测试用例的数量。

每个测试用例的第一行包含一个整数 ： 树的大小。

接下来的 行包含两个整数 和 （： 由一条边连接的顶点。保证边构成一棵树。

保证所有测试用例的 之和不超过 。

输出

对于每个测试用例，输出一个整数： 使用所述操作可实现的最大连接部件数。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
6
2
1 2
5
1 2
2 3
3 4
3 5
4
1 2
2 3
3 4
5
2 1
3 1
4 1
5 4
6
2 1
3 1
4 1
5 3
6 3
6
2 1
3 2
4 2
5 3
6 4
1
2
3
4
5
6
1
3
2
3
4
3
  • 标题: [Codeforces ROUND 991 Div.3] 1205
  • 作者: CatIsNotFound
  • 创建于 : 2024-12-06 12:07:26
  • 更新于 : 2024-12-06 12:07:26
  • 链接: https://catisnotfound.github.io/2024/12/CF-R991-D3/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
[Codeforces ROUND 991 Div.3] 1205
  1. A. Line Breaks
    1. 题目
    2. 样例
      1. INPUT
      2. OUTPUT
      3. 输入
      4. 输出
      5. 示例
  2. B. Transfusion
    1. 题目
    2. 样例
      1. INPUT
      2. OUTPUT
      3. 输入
      4. 输出
      5. 示例
  3. C. Uninteresting Number
    1. 题目
    2. 样例
      1. INPUT
      2. OUTPUT
      3. 输入
      4. 输出
      5. 示例
  4. D. Digital string maximization
    1. 题目
    2. 样例
      1. INPUT
      2. OUTPUT
      3. 输入
      4. 输出
      5. 示例
      6. 示例解释
  5. E. Three Strings
    1. 题目
    2. 样例
      1. INPUT
      2. OUTPUT
      3. 输入
      4. 输出
      5. 示例
  6. F. Maximum modulo equality
    1. 题目
    2. 样例
      1. INPUT
      2. OUTPUT
      3. 输入
      4. 输出
      5. 示例
      6. 示例解释
  7. G. Tree Destruction
    1. 题目
    2. 样例
      1. INPUT
      2. OUTPUT
      3. 输入
      4. 输出
      5. 示例