牛客周赛145-补EF#

https://ac.nowcoder.com/acm/contest/134981

Easy：A、B、C

Mid：D

Hard：E、F

A-Counter

Counter计数即可

1
from collections import Counter
2
s = input().strip()
3
cnt = Counter(s)
4
if len(cnt) == 2:
5
    print("Yes")
6
else:
7
    print("No")

B-滑动窗口

题意：

给定一个01串，求该01串的子串中满足同时包含0和1的数目

由于是01串，满足题意的答案即为：总子串的数量减去单子串的数量即可

使用的f(k)函数统计字符串 s 中所有不同字符个数不超过 k 的子串数量

1
from collections import defaultdict
2
def f(k):
3
    if k <= 0:
4
        return 0
5
    cnt = defaultdict(int)
6
    left = 0
7
    d = 0
8
    ans = 0
9
    for right in range(len(s)):
10
        c = s[right]
11
        cnt[c] += 1
12
        if cnt[c] == 1:
13
            d += 1
14
        while d > k:
15
            c_left = s[left]
16
            cnt[c_left] -= 1
17
            if cnt[c_left] == 0:
18
                d -= 1
19
            left += 1
20
        ans += right - left + 1
21
    return ans
22
n = int(input())
23
s = input().strip()
24
ans = n*(n+1)//2 - f(1)
25
print(ans)

C-数学

题意：

给你一个数组以及一个01子串，对于第i位，表示：该位置位颜色红色其数目位ai。可以进行如下操作任意次：选择i,j，使ai+1，aj-1

求最小的操作数，使得两种颜色的平均数相等

题解：

显然的总数是不变的，为了：

$sum0 / cnt0 = sum1 / cnt1 \\ sum0 × cnt1 = sum1 × cnt0$

由 $sum1 = tot - sum0，cnt1 = n - cnt0$ ：

sum0 × (n - cnt0) = (tot - sum0) × cnt0 \\sum0 × n - sum0 × cnt0 = tot × cnt0 - sum0 × cnt0 \\sum0 × n = tot × cnt0

显然的：

$sum0 = (cnt0 × tot) / n$

1
n = int(input())
2
a = list(map(int, input().split()))
3
s = input().strip()
4
cnt0 = 0
5
cnt1 = 0
6
sum0 = 0
7
sum1 = 0
8
for i in range(n):
9
    if s[i] == '0':
10
        cnt0 += 1
11
        sum0 += a[i]
12
    else:
13
        cnt1 += 1
14
        sum1 += a[i]
15
tot = sum0 + sum1
16
if (cnt0 * tot) % n != 0:
17
    print(-1)
18
else:
19
    print(abs((cnt0*tot)//n) - sum0)

D-构造

对于某个值 x，排列 b,c中都只能各出现一次，因此 a 中同一个值最多只能出现两次；若出现超过两次，必然无解。

对于只出现一次的数字，需要决定它在 b 还是 c 中与 a 匹配。目标是让 b 和 c 各自至少有 n/2 个匹配位置。通过变量 need 计算每个排列还需要多少个匹配，然后将前 need 个单次出现的数字分配给 b，其余的分配给c；

若出现两次，就分别放入 b 和 c的不同位置；

若没有出现，收集 b 和 c 各自缺失的数字，按顺序填入未填充的位置。

1
def main():
2
    n = int(input())
3
    a = list(map(int, input().split()))
4
    pos = [[] for _ in range(n + 1)]
5
    for i, val in enumerate(a):
6
        pos[val].append(i)
7
    for x in range(1, n + 1):
8
        if len(pos[x]) > 2:
9
            print(-1)
10
            return
11
    b = [0] * n
12
    c = [0] * n
13
    in_b = [False] * n
14
    in_c = [False] * n
15
    cnt = 0
16
    for x in range(1, n + 1):
17
        if len(pos[x]) == 2:
18
            i, j = pos[x]
19
            b[i] = x
20
            c[j] = x
21
            in_b[i] = True
22
            in_c[j] = True
23
            cnt += 1
24
    sg = []
25
    for x in range(1, n + 1):
26
        if len(pos[x]) == 1:
27
            sg.append(pos[x][0])
28
    need = n // 2 - cnt
29
    for idx in sg[:need]:
30
        b[idx] = a[idx]
31
        in_b[idx] = True
32
    for idx in sg[need:]:
33
        c[idx] = a[idx]
34
        in_c[idx] = True
35
    used_b = set(b) - {0}
36
    used_c = set(c) - {0}
37
    miss_b = [x for x in range(1, n + 1) if x not in used_b]
38
    miss_c = [x for x in range(1, n + 1) if x not in used_c]
39
    pb = pc = 0
40
    for i in range(n):
41
        if in_b[i]:
42
            c[i] = miss_c[pc]
43
            pc += 1
44
        else:
45
            b[i] = miss_b[pb]
46
            pb += 1
47
    print(*b)
48
    print(*c)
49
if __name__ == "__main__":
50
    main()

对于某个值 x，排列 b,c 中都只能各出现一次，因此 a 中同一个值最多只能出现两次；

若出现超过两次，必然无解。

若 x 出现一次，就让对应位置的 bi,ci都等于 x；若出现两次，就分别放入 b 和 c；

若没有出现，则作为缺失值填入 b,c 尚未填的位置。这样 b,c 都是排列，且两个排列中与 a 相等的位置数都不少于 n//2。

1
def solve() -> None:
2
    n = int(input())
3
    a = list(map(int, input().split()))
4
    b = [0] * n
5
    c = [0] * n
6
    p = [[] for _ in range(n + 1)]
7

8
    for i, val in enumerate(a):
9
        p[val].append(i)
10

11
    ms = []
12
    for x in range(1, n + 1):
13
        if len(p[x]) > 2:
14
            print(-1)
15
            return
16
        if not p[x]:
17
            ms.append(x)
18
        elif len(p[x]) == 1:
19
            pos = p[x][0]
20
            b[pos] = c[pos] = x
21
        else:
22
            b[p[x][0]] = x
23
            c[p[x][1]] = x
24

25
    eb = [i for i in range(n) if not b[i]]
26
    ec = [i for i in range(n) if not c[i]]
27

28
    for i in range(len(ms)):
29
        b[eb[i]] = ms[i]
30
        c[ec[i]] = ms[i]
31

32
    print(' '.join(map(str, b)))
33
    print(' '.join(map(str, c)))
34

35
if __name__ == "__main__":
36
    solve()

E-图论+生成树+DSU

不太会DSU，赛时写的并查集，通过枚举排除一种颜色，检查剩下的边能否构成生成树，以及这棵树是否有两种颜色

错误点在于当单色足以联通时会误判

1
def find(p, x):
2
    root = x
3
    while p[root] != root:
4
        root = p[root]
5
    while x != root:
6
        nxt = p[x]
7
        p[x] = root
8
        x = nxt
9
    return root
10
def union(p, rank, x, y):
11
    rx, ry = find(p, x), find(p, y)
12
    if rx == ry:
13
        return False
14
    if rank[rx] < rank[ry]:
15
        p[rx] = ry
16
    elif rank[rx] > rank[ry]:
17
        p[ry] = rx
18
    else:
19
        p[ry] = rx
20
        rank[rx] += 1
21
    return True
22
ok = False
23
n, m = map(int, input().split())
24
g = []
25
for _ in range(m):
26
    u, v, w = map(int, input().split())
27
    g.append((u, v, w))
28

29
for mss in (0, 1, 2):
30
    p = list(range(n + 1))
31
    rank = [0] * (n + 1)
32
    ch = []
33
    use = set()
34
    for u, v, w in g:
35
        if w == mss:
36
            continue
37
        if union(p, rank, u, v):
38
            ch.append((u, v))
39
            use.add(w)
40
    if len(ch) == n - 1 and len(use) == 2:
41
        ok = True
42
        for u, v in ch:
43
            print(u, v)
44
        break
45
if not ok:
46
    print(-1)

合法生成树恰好使用两种颜色。枚举颜色对 (x,y)，只保留这两种颜色的边。如果该颜色对构成的子图连通，并且两种颜色各至少有一条边，那么可以先强制加入一条颜色 x 的边和一条颜色 y 的边，再用 DSU 继续扩展成生成树。因为连通图中的任意森林都可以扩展成生成树。

1
import sys
2

3
def solve() -> None:
4
    data = sys.stdin.read().strip().split()
5
    if not data:
6
        return
7
    it = iter(data)
8
    n = int(next(it))
9
    m = int(next(it))
10

11
    edges = []
12
    color_id = [-1, -1, -1]  # 记录每种颜色的一条边的索引
13

14
    for i in range(m):
15
        u = int(next(it))
16
        v = int(next(it))
17
        w = int(next(it))
18
        edges.append((u, v, w))
19
        color_id[w] = i  # 记录该颜色的一条边的索引
20

21
    if n < 3:
22
        print(-1)
23
        return
24

25
    # 并查集实现
26
    parent = []
27
    rank = []
28

29
    def init_dsu(n):
30
        nonlocal parent, rank
31
        parent = list(range(n + 1))
32
        rank = [0] * (n + 1)
33

34
    def find(x):
35
        # 路径压缩
36
        while parent[x] != x:
37
            parent[x] = parent[parent[x]]
38
            x = parent[x]
39
        return x
40

41
    def union(x, y):
42
        rx, ry = find(x), find(y)
43
        if rx == ry:
44
            return False
45
        if rank[rx] < rank[ry]:
46
            parent[rx] = ry
47
        elif rank[rx] > rank[ry]:
48
            parent[ry] = rx
49
        else:
50
            parent[ry] = rx
51
            rank[rx] += 1
52
        return True
53

54
    # 枚举颜色对 (x, y)
55
    for x in range(3):
56
        for y in range(x + 1, 3):
57
            if color_id[x] == -1 or color_id[y] == -1:
58
                continue
59

60
            init_dsu(n)
61
            ans = []
62

63
            # 强制先加入颜色 x 和 y 的各一条边
64
            for idx in (color_id[x], color_id[y]):
65
                u, v, w = edges[idx]
66
                if union(u, v):
67
                    ans.append((u, v))
68

69
            # 继续用剩余边完成生成树
70
            for u, v, w in edges:
71
                if w != x and w != y:
72
                    continue
73
                if union(u, v):
74
                    ans.append((u, v))
75

76
            if len(ans) == n - 1:
77
                out_lines = [f"{u} {v}" for u, v in ans]
78
                sys.stdout.write("\n".join(out_lines))
79
                return
80

81
    print(-1)
82

83
if __name__ == "__main__":
84
    solve()

F-构造

构造一个长度为n的字符串s，使得其中恰好有k个子串是好串，保证：n−1≤k≤2×(n−2)

当k == n - 1时，构造'ab' + 'c'*(n-2)

否则，构造'a' + 'b'*(k - n + 1) + 'a'+'c'*(2*n-k-3)

1
for _ in range(int(input())):
2
    n,k = map(int,input().split())
3
    if k == n-1:
4
        s = 'ab' + 'c'*(n-2)
5
    else:
6
        # n - 2 - k + (n - 1)
7
        s = 'a' + 'b'*(k - n + 1) + 'a'+'c'*(2*n-k-3)
8
    print(s)

音乐

音乐

牛客周赛145-补EF#

音乐

目录

音乐

音乐

牛客周赛145-图论/生成树/DSU+构造

牛客周赛145-补EF#

音乐

目录