Acwing 周赛142 解题报告 | 珂学家

本文主要是介绍Acwing 周赛142 解题报告 | 珂学家 | BFS集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

整体评价

VP了这场比赛，感觉T2挺有意思的，超级容易错，T3到时中规中矩，算Middle更合适。

A. 倒序排列

思路: 模拟

n = int(input())l = [i for i in range(n, 0, -1)]print (*l, sep=' ')

B. 最有价值字符串

思路: 思维

这题难在思维，容易错

这边有两个小难点

如何评估得分
- 分情况讨论
  - 最大频数非唯一
  - 所有数都相等
最后结果判定
- n-largest的方式

n = int(input())a, b, c = input(), input(), input()from collections import Counterdef evalute(s) -> int:cnt = Counter(s)t1 = max(cnt.values())t2 = len(s) - t1if t2 > 0:return t1 + min(t2, n)else:return t1 - (1 if n == 1 else 0)# 模拟n-largest操作
l = [(evalute(a), 'A'), (evalute(b), 'B'), (evalute(c), 'C')]
l.sort(key=lambda x: -x[0])# 判定第一个元素和第二个元素，值是否相等
if l[0][0] > l[1][0]:print (l[0][1])
else:print ('D')

C. 有效点对

思路: 两次bfs+容斥

分别从x,y两点出发做bfs，然后进行染色A，B

比如从x点出发，止于y这个阻塞点，其他点全遍历为s1，则y这个阻塞点覆盖点集 A = n - s1

反之亦然 B = n - s2

最后结果为

$n * (n - 1) - A * B$

n, x, y = list(map(int, input().split()))g = [[] for _ in range(n + 1)]for i in range(n - 1):u, v = list(map(int, input().split()))g[u].append(v)g[v].append(u)from collections import dequedef bfs(u, v):vis = [1] * (n + 1)vis[0] = 0deq = deque()deq.append(u)vis[u] = 0while len(deq) > 0:cur = deq.popleft()for ver in g[cur]:if vis[ver] == 1 and ver != v:deq.append(ver)vis[ver] = 0return sum(vis)c1, c2 = bfs(x, y), bfs(y, x)print (n * (n - 1) - c1 * c2)