前言

整体评价

补了下题，顺便占个位子, 感觉还是挺难的，而且出题出得非常用心。

D. 我不是大富翁

思路: 0-1背包

很典的一道0-1背包的变形题

构建2个集合，其和分别为x,y，总和为s

则 x + y = s, x - y = k * n

推导 2 * x - s = k * n

转换为0-1背包模型， 能否找到一个集合，其和2*x和s的差值是n的倍数

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

arr = [v % n for v in arr if v % n != 0]
s = sum(arr) 

s = s % n

dp = [False] * (n + 1)
dp[0] = True

for v in arr:
    dp2 = [v for v in dp]
    for i in range(n + 1):
        if dp[i]:
            dp2[(i + v) % n] = True
    dp = dp2

ok = False
for i in range(n + 1):
    if dp[i] and (2 * i - s) % n == 0:
        ok = True
        break
print ("YES" if ok else "NO")

E. 多重映射

思路: 并查集 + 双向映射

很侧重数据结构的一道题，理论上它属于模拟题

并查集和双向映射，都是显而易见的，但是两者结合起来，感觉确实有点绕.

class Dsu(object):
    
    def __init__(self, n):
        self.n = n
        self.arr = [0] * (n + 1)
    
    def find(self, a):
        if self.arr[a] == 0:
            return a
        fa = a
        while self.arr[fa] != 0:
            fa = self.arr[fa]
        while self.arr[a] != 0:
            self.arr[a], a = fa, self.arr[a]
        return fa
    
    def union(self, a, b):
        ai, bi = self.find(a), self.find(b)
        if ai != bi:
            self.arr[ai] = bi
    

from collections import Counter
t = int(input())
for _ in range(t):
    
    n, m = list(map(int, input().split()))
    arr = [0] + list(map(int, input().split()))
    
    dsu = Dsu(n)
    mp = Counter()
    hp = Counter()
    for i in range(1, n + 1):
        v = arr[i]
        if v in mp:
            dsu.union(mp[v], i)
        else:
            mp[v] = i
    for i in range(1, n + 1):
        v = arr[i]
        hp[v] = dsu.find(i)
    
    for _ in range(m):
        fr, to = list(map(int, input().split()))
        if fr == to:
            continue
        if fr in hp:
            if to not in hp:
                hp[to] = hp[fr]
                del hp[fr]
            else:
                dsu.union(hp[fr], hp[to])
                del hp[fr]
    revMap = Counter()
    for (k, v) in hp.items():
        revMap[v] = k
    
    res = []
    for i in range(1, n + 1):
        res.append(revMap[dsu.find(i)])
    
    print (*res, sep=' ')

写在最后