Codeforces Round 950 (Div. 3) A B

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

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

import sys
input = lambda: sys.stdin.readline().strip()
mod = 10 ** 9 + 7 # 998244353for _ 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")

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

---