前言

alt

题解

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

A. 两数之和

签到

特判<=2的情况

z = int(input())

if z <= 2:
    print("NO")
else:
    print ("YES")
    print (1, z - 1)

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")

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)

D. 小红的最大字典序

思路: 多路归并

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

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

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

如果按照多路归并的方式

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

越大，时间复杂度越高

因为 ,因此 , 此时多路归并

如果

所以这题的前置条件为

alt

n = int(input())

arr = input().split()

import heapq

# python3的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))

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

如果字符串S和T合并的，时间复杂度为

那么采用分治归并，或者说采用类似哈夫曼编码的合并方式

那最终的时间复杂度为

关键在于X(n)的时间复杂度, 如果能保证线性, 那就更有普遍意义。

E. 小红的图上加边

思路: 连通图 + 贪心

贪心合并，感觉结论为

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))

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)

写在最后

alt