牛客周赛 Round 52 解题报告 | 珂学家_小红的数字对对碰题解

---

前言

---

题解

好难的场, 从第二题开始，就感觉画风不对.

---

A. 两数之和

签到

特判<=2的情况

z = int(input())

if z <= 2:
    print("NO")
else:
    print ("YES")
    print (1, z - 1)
1
2
3
4
5
6
7

---

B. 小红装匣子

思路: 贪心

• B型1*3方块，一定成对出现(偶数次)
• 优先使用B型方块，但是其数量和n存在制约关系

把握了这两点，基本就能AC

• 题目只要能填满就行，不需要使用完

def check(a, b, n):
    z = n // 3
    if b % 2 == 0:
        return a * 2 + min(z * 2, b) * 3 >= 2 * n
    else:
        return a * 2 + min(z * 2, (b - 1)) * 3 >= 2 * n
 
t = int(input())
for _ in range(t):
    a, b, n = list(map(int, input().split()))
    print ("YES" if check(a, b, n) else "NO")
1
2
3
4
5
6
7
8
9
10
11

---

C. 小红的数字对对碰

思路: 贪心

• 负数能对消正数(异或), 对消负数/0
• 非负数相等对消

从贪心的角度，交换法则，

$$非负数先对消，在用负数对消，结果只会更好，至少不变差$$

因此

• 先用非负数相等对消
• 在用负数对消非负数
• 负数对消负数

n = int(input())
arr = list(map(int, input().split()))

from collections import Counter
cnt = Counter()

neg = 0
for v in arr:
    if v < 0: 
        neg += 1
    else:
        cnt[v] += 1
non = 0
for (k, v) in cnt.items():
    non += v % 2

s = min(neg, non)
neg -= s
non -= s

neg %= 2

print (non + neg)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

---

D. 小红的最大字典序

思路: 多路归并

先考虑两个字符串S和T的合并

• 若 s[i] != t[j], 贪心选最大的
• 若 s[i] == t[j], 就需要一直往后看，直到两者分出大小

这个合并方式，其实挺难写的。

如果按照多路归并的方式

引入优先队列，则其时间复杂度为

$$O(|C|\ast logn\ast \sum _{i=0}^{i=n-1}|C_i|)$$

$$\sum _{i=0}^{i=n-1}|C_i|\le 2\ast 10^5$$

$|C|$越大，时间复杂度越高

因为 $ai\le 10^9$,因此 $|C|\le 10$, 此时多路归并 $O(3.2\ast 10^7)$

注：python的heapq没法自定义比较函数，所以字符串按字母序逆序排，挺麻烦的

n = int(input())

arr = input().split()

import heapq

hp = []

def change(c):
    return chr(ord('9') - ord(c) + ord('0'))

for s in arr:
    # 转换后，尾巴还要加个？，可以想下为什么？
    heapq.heappush(hp, ''.join([change(c) for c in s]) + '?')
    
r = []
while len(hp) > 0:
    s = heapq.heappop(hp)
    r.append(change(s[0]))
    if len(s) > 2:
        heapq.heappush(hp, s[1:])
    
print (''.join(r))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

E. 小红的图上加边

思路: 连通图 + 贪心

贪心合并，感觉结论为

$\sum w_i-\min w_i$

$w_i为连通块中的最大值$

n, m = list(map(int, input().split()))

arr = list(map(int, input().split()))

g = [[] for _ in range(n)]

for _ in range(m):
    u, v = list(map(int, input().split()))
    u, v = u - 1, v - 1
    g[u].append(v)
    g[v].append(u)
    
vis = [False] * n

from collections import deque
def bfs(s):
    r = arr[s]
    deq = deque()
    deq.append(s)
    vis[s] = True
    while len(deq) > 0:
        u = deq.popleft()
        for v in g[u]:
            if not vis[v]:
                vis[v] = True
                r = max(r, arr[v])
                deq.append(v)
    return r

w = []
for i in range(n):
    if not vis[i]:
        c = bfs(i)
        w.append(c)
        
print (sum(w) - min(w))
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
30
31
32
33
34
35
36

---

F. 小红的括号串

猜结论: 满足组合解，必然存在一个循环转移使得括号匹配

那最后就是单纯的组合解

后期再补证明吧

mod = 10 ** 9 + 7

n = int(input())
s = input()

mx = 10 ** 5
fac = [0] * (mx + 1)
inv = [0] * (mx + 1)

fac[0] = 1
for i in range(1, mx + 1):
    fac[i] = fac[i - 1] * i % mod
    
inv[mx] = pow(fac[mx], mod - 2, mod)
for i in range(mx - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod
     
l1, l2 = 0, 0
for c in s:
    if c == '(':
        l1 += 1
    elif c == ')':
        l2 += 1

if n % 2 == 1 or l1 > n // 2 or l2 > n // 2:
    print (0)
else:
    x = n - l1 - l2
    x1 = n // 2 - l1 
    r = fac[x] * inv[x1] % mod * inv[x - x1] % mod
    print (r)
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
30
31

---

写在最后