Codeforces Round 950 (Div. 3) A B C

本文主要是介绍Codeforces Round 950 (Div. 3) A B C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Problem Generator

time limit per test: 1 second memory limit per test: 256 megabytes input: standard input output: standard output

Vlad is planning to hold $m$ rounds next month. Each round should contain one problem of difficulty levels ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, and ‘G’.

Vlad already has a bank of $n$ problems, where the $i$-th problem has a difficulty level of $a_i$. There may not be enough of these problems, so he may have to come up with a few more problems.

Vlad wants to come up with as few problems as possible, so he asks you to find the minimum number of problems he needs to come up with in order to hold $m$ rounds.

For example, if $m=1$, $n=10$, $a=$ ‘BGECDCBDED’, then he needs to come up with two problems: one of difficulty level ‘A’ and one of difficulty level ‘F’.

Input

The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1\le n\le 50$, $1\le m\le 5$) — the number of problems in the bank and the number of upcoming rounds, respectively.

The second line of each test case contains a string $a$ of $n$ characters from ‘A’ to ‘G’ — the difficulties of the problems in the bank.

Output

For each test case, output a single integer — the minimum number of problems that need to come up with to hold $m$ rounds.

Example

$\mathtt{input}$
3 10 1 BGECDCBDED 10 2 BGECDCBDED 9 1 BBCDEFFGG
$\mathtt{output}$
2 5 1

Tutorial

A，B，C，D，E，F，G $7$ 个字母在字符串 $a$ 中如果出现次数不足 $m$ 个则补齐，否则不做任何操作，则答案为 ${\sum }_{c{=}^{\prime }{A}^{\prime }}^{{}^{\prime }{G}^{\prime }}m-cn{t}_c$

此解法时间复杂度为 $\mathcal{O}(n)$

Solution

for _ in range(int(input())):n, m = map(int, input().split())s = input()ss = "ABCDEFG"print(sum(max(0, m - s.count(ss[i])) for i in range(7)))

B. Choosing Cubes

time limit per test: 1 second memory limit per test: 256 megabytes input: standard input output: standard output

Dmitry has $n$ cubes, numbered from left to right from $1$ to $n$. The cube with index $f$ is his favorite.

Dmitry threw all the cubes on the table, and the $i$-th cube showed the value $a_i$ ($1\le a_i\le 100$). After that, he arranged the cubes in non-increasing order of their values, from largest to smallest. If two cubes show the same value, they can go in any order.

After sorting, Dmitry removed the first $k$ cubes. Then he became interested in whether he removed his favorite cube (note that its position could have changed after sorting).

For example, if $n=5$, $f=2$, $a=[4,3,3,2,3]$ (the favorite cube is highlighted in green), and $k=2$, the following could have happened:

• After sorting $a=[4,3,3,3,2]$, since the favorite cube ended up in the second position, it will be removed.
• After sorting $a=[4,3,3,3,2]$, since the favorite cube ended up in the third position, it will not be removed.

Input

The first line contains an integer $t$ ($1\le t\le 1000$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case description contains three integers $n$, $f$, and $k$ ($1\le f,k\le n\le 100$) — the number of cubes, the index of Dmitry’s favorite cube, and the number of removed cubes, respectively.

The second line of each test case description contains $n$ integers $a_i$ ($1\le a_i\le 100$) — the values shown on the cubes.

Output

For each test case, output one line — “YES” if the cube will be removed in all cases, “NO” if it will not be removed in any case, “MAYBE” if it may be either removed or left.

You can output the answer in any case. For example, the strings “YES”, “nO”, “mAyBe” will be accepted as answers.

Example

$\mathtt{input}$
12 5 2 2 4 3 3 2 3 5 5 3 4 2 1 3 5 5 5 2 5 2 4 1 3 5 5 5 1 2 5 4 3 5 5 4 3 1 2 4 5 5 5 5 4 3 2 1 5 6 5 3 1 2 3 1 2 3 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 42 5 2 3 2 2 1 1 2 2 1 1 2 1 5 3 1 3 3 2 3 2
$\mathtt{output}$
MAYBE YES NO YES YES YES MAYBE MAYBE YES YES YES NO

Tutorial

在解决问题前可以先选中 Dmitry 所喜爱的 cube，记为 $target$，然后对所有 cube 进行排序，如果 $target<a_k$，则最喜欢的那个 cube 必定在前 $k$ 个 cube 里，如果 $target>a_k$，则最喜欢的那个 cube 必定不在前 $k$ 个 cube 里，如果 $target=a_k$，如果第 $a_{k+1}$ 的数值和 $target$ 相等，则说明 $target$ 有可能被移除，否则 $target$ 也是必定被移除

此解法时间复杂度为 $\mathcal{O}(n\log n)$，即排序的时间复杂度

Solution

for _ in range(int(input())):n, f, k = map(int, input().split())a = list(map(int, input().split()))if k >= n:print("YES")continuetarget = a[f - 1]a.sort(reverse = True)if target > a[k - 1]:print("YES")elif target < a[k - 1]:print("NO")else:print("YES" if k == n or a[k] != target else "MAYBE")

C. Sofia and the Lost Operations

time limit per test: 2 second memory limit per test: 256 megabytes input: standard input output: standard output

Sofia had an array of $n$ integers $a_1,a_2,\dots ,a_n$. One day she got bored with it, so she decided to sequentially apply $m$ modification operations to it.

Each modification operation is described by a pair of numbers $⟨c_j,d_j⟩$ and means that the element of the array with index $c_j$ should be assigned the value $d_j$, i.e., perform the assignment $a_{c_j}=d_j$. After applying all modification operations sequentially, Sofia discarded the resulting array.

Recently, you found an array of $n$ integers $b_1,b_2,\dots ,b_n$. You are interested in whether this array is Sofia’s array. You know the values of the original array, as well as the values $d_1,d_2,\dots ,d_m$. The values $c_1,c_2,\dots ,c_m$ turned out to be lost.

Is there a sequence $c_1,c_2,\dots ,c_m$ such that the sequential application of modification operations $⟨c_1,d_1,⟩,⟨c_2,d_2,⟩,\dots ,⟨c_m,d_m⟩$ to the array $a_1,a_2,\dots ,a_n$ transforms it into the array $b_1,b_2,\dots ,b_n$?

Input

The first line contains an integer $t$ ($1\le t\le 10^4$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains an integer $n$ ($1\le n\le 2\cdot 10^5$) — the size of the array.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the original array.

The third line of each test case contains $n$ integers $b_1,b_2,\dots ,b_n$ ($1\le b_i\le 10^9$) — the elements of the found array.

The fourth line contains an integer $m$ ($1\le m\le 2\cdot 10^5$) — the number of modification operations.

The fifth line contains $m$ integers $d_1,d_2,\dots ,d_m$ ($1\le d_j\le 10^9$) — the preserved value for each modification operation.

It is guaranteed that the sum of the values of $n$ for all test cases does not exceed $2\cdot 10^5$, similarly the sum of the values of $m$ for all test cases does not exceed $2\cdot 10^5$.

Output

Output $t$ lines, each of which is the answer to the corresponding test case. As an answer, output “YES” if there exists a suitable sequence $c_1,c_2,\dots ,c_m$, and “NO” otherwise.

You can output the answer in any case (for example, the strings “yEs”, “yes”, “Yes” and “YES” will be recognized as a positive answer).

Example

$\mathtt{input}$
7 3 1 2 1 1 3 2 4 1 3 1 2 4 1 2 3 5 2 1 3 5 2 2 3 5 7 6 1 10 10 3 6 1 11 11 3 4 3 11 4 3 1 7 8 2 2 7 10 5 10 3 2 2 1 5 5 7 1 7 9 4 10 1 2 9 8 1 1 9 8 7 2 10 4 4 1000000000 203 203 203 203 1000000000 203 1000000000 2 203 1000000000 1 1 1 5 1 3 4 5 1
$\mathtt{output}$
YES NO NO NO YES NO YES

Tutorial

首先对于所有的 $d_i(i\in [1,n])$，都必须在数组 $b$ 中出现，不然更改的数字 $d_i$ 就会“不翼而飞”，对于位置 $i$ 如果有 $a_i=b_i$，那么可以对该位置不做任何操作，对于其他所有的位置 $i$ 如果满足 $a_i\ne b_i$，都必须进行覆盖操作，而多余的操作可以被正确的操作覆盖，所以只需要检查满足满足 $a_i\ne b_i$ 的条件的位置 $i$ 上的 $b_i$ 是否都在数组 $d$ 中即可，可以用一个 $\mathtt{hash}$ 表进行计数操作实现这一判断，$\mathtt{C}++$ 需要注意不要用 $unordered\_map$

需要特别判断的是，数组 $d$ 的最后一个元素一定要在数组 $b$ 中出现，因为其无法被覆盖

此解法时间复杂度为 $\mathcal{O}((n+m)\log n)$，即排序的时间复杂度

Solution

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdictout = []for _ in range(int(input())):n = int(input())a = list(map(str, input().split()))b = list(map(str, input().split()))m = int(input())d = list(map(str, input().split()))mp = defaultdict(int)for x, y in zip(a, b):if x != y:mp[y] += 1for x in d:if mp[x] > 0:mp[x] -= 1if (not sum(mp.values()) and d[-1] in b):out.append("YES")else:out.append("NO")print('\n'.join(out))

这篇关于Codeforces Round 950 (Div. 3) A B C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---