A. Problem Generator
Vlad is planning to hold m m 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 n n problems, where the i i i-th problem has a difficulty level of a i a_i ai. 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 m m rounds.
For example, if m = 1 m=1 m=1, n = 10 n = 10 n=10, a = a= 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 t t ( 1 ≤ t ≤ 1000 1 \le t \le 1000 1≤t≤1000) — the number of test cases.
The first line of each test case contains two integers n n n and m m m ( 1 ≤ n ≤ 50 1 \le n \le 50 1≤n≤50, 1 ≤ m ≤ 5 1 \le m \le 5 1≤m≤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 a a of n n 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 m m rounds.
Example
| i n p u t \tt input input |
|---|
| 3 10 1 BGECDCBDED 10 2 BGECDCBDED 9 1 BBCDEFFGG |
| o u t p u t \tt output output |
| 2 5 1 |
Tutorial
A，B，C，D，E，F，G
7
7
7 个字母在字符串
a
a
a 中如果出现次数不足
m
m
m 个则补齐，否则不做任何操作，则答案为
∑
c
=
′
A
′
′
G
′
m
−
c
n
t
c
\sum_{c = 'A'}^{'G'} m - cnt_c
∑c=′A′′G′m−cntc
此解法时间复杂度为 O ( n ) \mathcal O(n) 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
Dmitry has n n n cubes, numbered from left to right from 1 1 1 to n n n. The cube with index f f f is his favorite.
Dmitry threw all the cubes on the table, and the i i i-th cube showed the value a i a_i ai ( 1 ≤ a i ≤ 100 1 \le a_i \le 100 1≤ai≤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 k 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 n=5 n=5, f = 2 f=2 f=2, a = [ 4 , 3 , 3 , 2 , 3 ] a = [4, {\color{green}3}, 3, 2, 3] a=[4,3,3,2,3] (the favorite cube is highlighted in green), and k = 2 k = 2 k=2, the following could have happened:
- After sorting a = [ 4 , 3 , 3 , 3 , 2 ] a=[4, {\color{green}3}, 3, 3, 2] 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 ] a=[4, 3, {\color{green}3}, 3, 2] 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 t t ( 1 ≤ t ≤ 1000 1 \le t \le 1000 1≤t≤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 n n, f f f, and k k k ( 1 ≤ f , k ≤ n ≤ 100 1 \le f, k \le n \le 100 1≤f,k≤n≤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 n n integers a i a_i ai ( 1 ≤ a i ≤ 100 1 \le a_i \le 100 1≤ai≤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
| i n p u t \tt input 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 |
| o u t p u t \tt output output |
| MAYBE YES NO YES YES YES MAYBE MAYBE YES YES YES NO |
Tutorial
在解决问题前可以先选中 Dmitry 所喜爱的 cube，记为 t a r g e t target target，然后对所有 cube 进行排序，如果 t a r g e t < a k target < a_k target<ak，则最喜欢的那个 cube 必定在前 k k k 个 cube 里，如果 t a r g e t > a k target > a_k target>ak，则最喜欢的那个 cube 必定不在前 k k k 个 cube 里，如果 t a r g e t = a k target = a_k target=ak，如果第 a k + 1 a_{k + 1} ak+1 的数值和 t a r g e t target target 相等，则说明 t a r g e t target target 有可能被移除，否则 t a r g e t target target 也是必定被移除
此解法时间复杂度为 O ( n log n ) \mathcal O(n \log n) O(nlogn)，即排序的时间复杂度
Solution
for _ in range(int(input())):
n, f, k = map(int, input().split())
a = list(map(int, input().split()))
if k >= n:
print("YES")
continue
target = 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
Sofia had an array of n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an. One day she got bored with it, so she decided to sequentially apply m m m modification operations to it.
Each modification operation is described by a pair of numbers ⟨ c j , d j ⟩ \langle c_j, d_j \rangle ⟨cj,dj⟩ and means that the element of the array with index c j c_j cj should be assigned the value d j d_j dj, i.e., perform the assignment a c j = d j a_{c_j} = d_j acj=dj. After applying all modification operations sequentially, Sofia discarded the resulting array.
Recently, you found an array of n n n integers b 1 , b 2 , … , b n b_1, b_2, \ldots, b_n b1,b2,…,bn. 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 , … , d m d_1, d_2, \ldots, d_m d1,d2,…,dm. The values c 1 , c 2 , … , c m c_1, c_2, \ldots, c_m c1,c2,…,cm turned out to be lost.
Is there a sequence c 1 , c 2 , … , c m c_1, c_2, \ldots, c_m c1,c2,…,cm such that the sequential application of modification operations ⟨ c 1 , d 1 , ⟩ , ⟨ c 2 , d 2 , ⟩ , … , ⟨ c m , d m ⟩ \langle c_1, d_1, \rangle, \langle c_2, d_2, \rangle, \ldots, \langle c_m, d_m \rangle ⟨c1,d1,⟩,⟨c2,d2,⟩,…,⟨cm,dm⟩ to the array a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an transforms it into the array b 1 , b 2 , … , b n b_1, b_2, \ldots, b_n b1,b2,…,bn?
Input
The first line contains an integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
Then follow the descriptions of the test cases.
The first line of each test case contains an integer n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1≤n≤2⋅105) — the size of the array.
The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai≤109) — the elements of the original array.
The third line of each test case contains n n n integers b 1 , b 2 , … , b n b_1, b_2, \ldots, b_n b1,b2,…,bn ( 1 ≤ b i ≤ 1 0 9 1 \le b_i \le 10^9 1≤bi≤109) — the elements of the found array.
The fourth line contains an integer m m m ( 1 ≤ m ≤ 2 ⋅ 1 0 5 1 \le m \le 2 \cdot 10^5 1≤m≤2⋅105) — the number of modification operations.
The fifth line contains m m m integers d 1 , d 2 , … , d m d_1, d_2, \ldots, d_m d1,d2,…,dm ( 1 ≤ d j ≤ 1 0 9 1 \le d_j \le 10^9 1≤dj≤109) — the preserved value for each modification operation.
It is guaranteed that the sum of the values of n n n for all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105, similarly the sum of the values of m m m for all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
Output t t 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 , … , c m c_1, c_2, \ldots, c_m c1,c2,…,cm, 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
| i n p u t \tt input 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 |
| o u t p u t \tt output output |
| YES NO NO NO YES NO YES |
Tutorial
首先对于所有的 d i ( i ∈ [ 1 , n ] ) d_i(i \in [1,n]) di(i∈[1,n])，都必须在数组 b b b 中出现，不然更改的数字 d i d_i di 就会“不翼而飞”，对于位置 i i i 如果有 a i = b i a_i = b_i ai=bi，那么可以对该位置不做任何操作，对于其他所有的位置 i i i 如果满足 a i ≠ b i a_i \not= b_i ai=bi，都必须进行覆盖操作，而多余的操作可以被正确的操作覆盖，所以只需要检查满足满足 a i ≠ b i a_i \not= b_i ai=bi 的条件的位置 i i i 上的 b i b_i bi 是否都在数组 d d d 中即可，可以用一个 h a s h \tt hash hash 表进行计数操作实现这一判断，C++ 需要注意不要用 u n o r d e r e d _ m a p \tt unordered\_map unordered_map
需要特别判断的是，数组 d d d 的最后一个元素一定要在数组 b b b 中出现，因为其无法被覆盖
此解法时间复杂度为 O ( ( n + m ) log n ) \mathcal O((n + m) \log n) O((n+m)logn)，即排序的时间复杂度
Solution
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict
out = []
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] += 1
for x in d:
if mp[x] > 0:
mp[x] -= 1
if (not sum(mp.values()) and d[-1] in b):
out.append("YES")
else:
out.append("NO")
print('\n'.join(out))
D. GCD-sequence
GCD (Greatest Common Divisor) of two integers x x x and y y y is the maximum integer z z z by which both x x x and y y y are divisible. For example, G C D ( 36 , 48 ) = 12 GCD(36, 48) = 12 GCD(36,48)=12, G C D ( 5 , 10 ) = 5 GCD(5, 10) = 5 GCD(5,10)=5, and G C D ( 7 , 11 ) = 1 GCD(7,11) = 1 GCD(7,11)=1.
Kristina has an array a a a consisting of exactly n n n positive integers. She wants to count the GCD of each neighbouring pair of numbers to get a new array b b b, called GCD-sequence.
So, the elements of the GCD-sequence b b b will be calculated using the formula b i = G C D ( a i , a i + 1 ) b_i = GCD(a_i, a_{i + 1}) bi=GCD(ai,ai+1) for 1 ≤ i ≤ n − 1 1 \le i \le n - 1 1≤i≤n−1.
Determine whether it is possible to remove exactly one number from the array a a a so that the GCD sequence b b b is non-decreasing (i.e., b i ≤ b i + 1 b_i \le b_{i+1} bi≤bi+1 is always true).
For example, let Khristina had an array a a a = [ 20 , 6 , 12 , 3 , 48 , 36 20, 6, 12, 3, 48, 36 20,6,12,3,48,36]. If she removes a 4 = 3 a_4 = 3 a4=3 from it and counts the GCD-sequence of b b b, she gets:
- b 1 = G C D ( 20 , 6 ) = 2 b_1 = GCD(20, 6) = 2 b1=GCD(20,6)=2
- b 2 = G C D ( 6 , 12 ) = 6 b_2 = GCD(6, 12) = 6 b2=GCD(6,12)=6
- b 3 = G C D ( 12 , 48 ) = 12 b_3 = GCD(12, 48) = 12 b3=GCD(12,48)=12
- b 4 = G C D ( 48 , 36 ) = 12 b_4 = GCD(48, 36) = 12 b4=GCD(48,36)=12
The resulting GCD sequence b b b = [ 2 , 6 , 12 , 12 2,6,12,12 2,6,12,12] is non-decreasing because b 1 ≤ b 2 ≤ b 3 ≤ b 4 b_1 \le b_2 \le b_3 \le b_4 b1≤b2≤b3≤b4.
Input
The first line of input data contains a single number t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — he number of test cases in the test.
This is followed by the descriptions of the test cases.
The first line of each test case contains a single integer n n n ( 3 ≤ n ≤ 2 ⋅ 1 0 5 3 \le n \le 2 \cdot 10^5 3≤n≤2⋅105) — the number of elements in the array a a a.
The second line of each test case contains exactly n n n integers a i a_i ai ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai≤109) — the elements of array a a a.
It is guaranteed that the sum of n n n over all test case does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
For each test case, output a single line:
- “YES” if you can remove exactly one number from the array a a a so that the GCD-sequence of b b b is non-decreasing;
- “NO” otherwise.
You can output the answer in any case (for example, the strings “yEs”, “yes”, “Yes”, and “YES” will all be recognized as a positive answer).
Example
| i n p u t \tt input input |
|---|
| 12 6 20 6 12 3 48 36 4 12 6 3 4 3 10 12 3 5 32 16 8 4 2 5 100 50 2 10 20 4 2 4 8 1 10 7 4 6 2 4 5 1 4 2 8 7 5 9 6 8 5 9 2 6 11 14 8 12 9 3 9 5 7 3 10 6 3 12 6 3 3 4 2 4 8 1 6 11 12 6 12 3 6 |
| o u t p u t \tt output output |
| YES NO YES NO YES YES NO YES YES YES YES YES |
Note
The first test case is explained in the problem statement.
Tutorial
如果数组 a a a 产生的 G C D GCD GCD 数组 b b b 已经是不递减的状态，那么直接删除第一个元素或者最后一个元素即可
否则找到一个位置 i i i 满足 b i > b i + 1 b_i > b_{i + 1} bi>bi+1，则分别判断删除 a i a_i ai、 a i + 1 a_{i + 1} ai+1、 a i + 2 a_{i + 2} ai+2 后的数组能否满足条件即可
**注意：**边界需要特别判断一下
此解法时间复杂度为 O ( n ) \mathcal O(n) O(n)
Solution
import sys
from math import gcd
input = lambda: sys.stdin.readline().strip()
out = []
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
pre, suf, last = [1] * n, [1] * n, 0
for i in range(1, n):
now = gcd(a[i], a[i - 1])
pre[i] = pre[i - 1] & (now >= last)
last = now
last = 10 ** 9
for i in range(n - 2, -1, -1):
now = gcd(a[i], a[i + 1])
suf[i] = suf[i + 1] & (now <= last)
last = now
ans = suf[1] | pre[-2]
for i in range(1, n - 1):
ok = 1
if i > 1 and gcd(a[i - 2], a[i - 1]) > gcd(a[i - 1], a[i + 1]):
ok = 0
if i < n - 2 and gcd(a[i - 1], a[i + 1]) > gcd(a[i + 1], a[i + 2]):
ok = 0
ans = max(ans, pre[i - 1] & suf[i + 1] & ok)
out.append("YES" if ans else "NO")
print('\n'.join(out))
E. Permutation of Rows and Columns
You have been given a matrix a a a of size n n n by m m m, containing a permutation of integers from 1 1 1 to n ⋅ m n \cdot m n⋅m.
A permutation of n n n integers is an array containing all numbers from 1 1 1 to n n n exactly once. For example, the arrays [ 1 ] [1] [1], [ 2 , 1 , 3 ] [2, 1, 3] [2,1,3], [ 5 , 4 , 3 , 2 , 1 ] [5, 4, 3, 2, 1] [5,4,3,2,1] are permutations, while the arrays [ 1 , 1 ] [1, 1] [1,1], [ 100 ] [100] [100], [ 1 , 2 , 4 , 5 ] [1, 2, 4, 5] [1,2,4,5] are not.
A matrix contains a permutation if, when all its elements are written out, the resulting array is a permutation. Matrices [ [ 1 , 2 ] , [ 3 , 4 ] ] [[1, 2], [3, 4]] [[1,2],[3,4]], [ [ 1 ] ] [[1]] [[1]], [ [ 1 , 5 , 3 ] , [ 2 , 6 , 4 ] ] [[1, 5, 3], [2, 6, 4]] [[1,5,3],[2,6,4]] contain permutations, while matrices [ [ 2 ] ] [[2]] [[2]], [ [ 1 , 1 ] , [ 2 , 2 ] ] [[1, 1], [2, 2]] [[1,1],[2,2]], [ [ 1 , 2 ] , [ 100 , 200 ] ] [[1, 2], [100, 200]] [[1,2],[100,200]] do not.
You can perform one of the following two actions in one operation:
- choose columns c c c and d d d ( 1 ≤ c , d ≤ m 1 \le c, d \le m 1≤c,d≤m, c ≠ d c \ne d c=d) and swap these columns;
- choose rows c c c and d d d ( 1 ≤ c , d ≤ n 1 \le c, d \le n 1≤c,d≤n, c ≠ d c \ne d c=d) and swap these rows.
You can perform any number of operations.
You are given the original matrix a a a and the matrix b b b. Your task is to determine whether it is possible to transform matrix a a a into matrix b b b using the given operations.
Input
The first line contains an integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases. The descriptions of the test cases follow.
The first line of each test case description contains 2 2 2 integers n n n and m m m ( 1 ≤ n , m ≤ n ⋅ m ≤ 2 ⋅ 1 0 5 1 \le n, m \le n \cdot m \le 2 \cdot 10^5 1≤n,m≤n⋅m≤2⋅105) — the sizes of the matrix.
The next n n n lines contain m m m integers a i j a_{ij} aij each ( 1 ≤ a i j ≤ n ⋅ m 1 \le a_{ij} \le n \cdot m 1≤aij≤n⋅m). It is guaranteed that matrix a a a is a permutation.
The next n n n lines contain m m m integers b i j b_{ij} bij each ( 1 ≤ b i j ≤ n ⋅ m 1 \le b_{ij} \le n \cdot m 1≤bij≤n⋅m). It is guaranteed that matrix b b b is a permutation.
It is guaranteed that the sum of the values n ⋅ m n \cdot m n⋅m for all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output
For each test case, output “YES” if the second matrix can be obtained from the first, 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.
Example
| i n p u t \tt input input |
|---|
| 7 1 1 1 1 2 2 1 2 3 4 4 3 2 1 2 2 1 2 3 4 4 3 1 2 3 4 1 5 9 6 12 10 4 8 7 11 3 2 1 5 9 6 12 10 4 8 7 11 3 2 3 3 1 5 9 6 4 2 3 8 7 9 5 1 2 4 6 7 8 3 2 3 1 2 6 5 4 3 6 1 2 3 4 5 1 5 5 1 2 3 4 4 2 5 1 3 |
| o u t p u t \tt output output |
| YES YES NO YES YES NO YES |
Note
In the second example, the original matrix looks like this:
( 1 2 3 4 ) \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} (1324)
By swapping rows 1 1 1 and 2 2 2, it becomes:
( 3 4 1 2 ) \begin{pmatrix} 3 & 4 \\ 1 & 2 \end{pmatrix} (3142)
By swapping columns 1 1 1 and 2 2 2, it becomes equal to matrix b b b:
( 4 3 2 1 ) \begin{pmatrix} 4 & 3 \\ 2 & 1 \end{pmatrix} (4231)
Tutorial
由题意得，就是需要判断两个矩阵是否相等，即能否通过初等变换变为对方
当进行初等行变换时，交换的两行元素对于自己当前行的所有元素相对位置都不会变，即不会出现原来是相同行，变换后变为不同行了
当进行初等列变换时，交换的两列元素对于自己当前列的所有元素相对位置都不会变，即不会出现原来是相同列，变换后变为不同列了
则可以对一个矩阵进行记录，记录下每个元素所在行和所在列，再在另一个矩阵中分别行（列）遍历元素，查看两两元素之间在第一个矩阵中是否处在同一行（列），如果存在两个不同的元素的行或列不同，则两个矩阵不相等
此解法时间复杂度为 O ( n m ) \mathcal O(nm) O(nm)
Solution
import sys
input = lambda: sys.stdin.readline().strip()
from collections import defaultdict
for _ in range(int(input())):
n, m = map(int, input().split())
a = [list(map(int, input().split())) for __ in range(n)]
b = [list(map(int, input().split())) for __ in range(n)]
row, col = defaultdict(), defaultdict()
ans = "YES"
for i in range(n):
for j in range(m):
row[a[i][j]] = i
col[a[i][j]] = j
for i in range(n):
for j in range(m):
if row[b[i][j]] != row[b[i][0]]:
ans = "NO"
for j in range(m):
for i in range(n):
if col[b[i][j]] != col[b[0][j]]:
ans = "NO"
print(ans)