AWC68#

Tasks - AtCoder Weekday Contest 0068 Beta

Easy: A、B

Mid: C

Hard: D、E

A/B-模拟

A判断序列每个元素的范围是否在\[l,r]中即可

1
n,l,r = map(int,input().split())
2
ans = 0
3
for _ in range(n):
4
    t = int(input())
5
    if l <= t <= r:
6
        ans += 1
7
print(ans)

B维护最大值最小值即可

1
n,m = map(int,input().split())
2
a = [0] + list(map(int,input().split()))
3
INF = 10**99
4
max_ = 0
5
min_ = 10**99
6
for _ in range(m):
7
    l,r = map(int,input().split())
8
    t = sum(a[l:r+1])
9
    if t > max_:
10
        max_ = t
11
    if t < min_:
12
        min_ = t
13
print(max_ - min_)

C-并查集

题意：

有N个队伍，每个队伍只有一个人，且没有颜色

有M次操作，第i次操作，合并ui和vi所在的队伍，将合并后的队伍颜色设为ci

所求为所有操作结束后，有颜色的队伍中，不同颜色的数量

题解：

值得注意的是，如果两个队伍已经合并，其颜色仍需被更改

用并查集维护队伍合并，记录每个队伍根节点最终颜色，对于每个操作i：

找到ui和vi的跟ru,rv，如果ru≠rv，则合并并将新根的颜色设为ci

如果ru==rv，则直接将根的颜色设为ci

最后遍历所有根节点，如果颜色非空，加入集合

1
def find(p, x):
2
    if p[x] != x:
3
        p[x] = find(p, p[x])
4
    return p[x]
5

6
def union(p, rank, color, x, y, c):
7
    rx, ry = find(p, x), find(p, y)
8
    if rx == ry:
9
        color[rx] = c
10
        return
11
    if rank[rx] < rank[ry]:
12
        p[rx] = ry
13
        color[ry] = c
14
    elif rank[rx] > rank[ry]:
15
        p[ry] = rx
16
        color[rx] = c
17
    else:
18
        p[ry] = rx
19
        rank[rx] += 1
20
        color[rx] = c
21

22
n, m = map(int, input().split())
23
p = list(range(n + 1))
24
rank = [0] * (n + 1)
25
color = [0] * (n + 1)
26
for _ in range(m):
27
    u, v, c = map(int, input().split())
28
    union(p, rank, color, u, v, c)
29

30
colors = set()
31
# 统计所有根节点
32
for i in range(1, n + 1):
33
    if p[i] == i and color[i] != 0:
34
        colors.add(color[i])
35
print(len(colors))

D-Dijkstra最短路

题意：

图：N 个节点，M 条无向边，无重边。
每个节点的度数 = 拥堵程度。
路线：从 1 到 N，允许重复走节点和边。
代价 = 边数（每条 1 分钟）+ 对于每条内部节点（不包括起点和终点），如果它的度数 ≥ K，则额外 +1 分钟。
求最小总时间，若不可达输出 -1。

题解：

节点代价只看度数≥k时才加1，且只在路径内部节点才计算，故把节点权值转化为”经过该节点时，如果度数≥k”则加1

将每个节点 u 拆成两个点：u_in 和 u_out。

对于原图中每条边 (u, v)：
- 添加有向边 u_out → v_in，权值 1
- 添加有向边 v_out → u_in，权值 1
对于每个节点 u：
- 添加有向边 u_in → u_out，权值 = (1 if deg[u] ≥ K else 0)

这样，从 1_in 出发，到 N_in 结束，走一条路径，总权值 = 边数 + 内部节点数（满足条件）。

边：u_out → v_in 权值 1；v_out → u_in 权值 1 节点内部：u_in → u_out 权值 = 1 if deg[u] ≥ K and u not in {1, N} else 0

1
import heapq
2
import sys
3

4
def solve():
5
    input = sys.stdin.readline
6
    N, M, K = map(int, input().split())
7
    g = [[] for _ in range(N + 1)]
8
    degree = [0] * (N + 1)
9
    for _ in range(M):
10
        u, v = map(int, input().split())
11
        g[u].append(v)
12
        g[v].append(u)
13
        degree[u] += 1
14
        degree[v] += 1
15

16
    # 拆点：0~N-1 为 in，N~2N-1 为 out
17
    def in_node(x):
18
        return x - 1
19
    def out_node(x):
20
        return N + x - 1
21

22
    total_nodes = 2 * N
23
    adj = [[] for _ in range(total_nodes)]
24
    for u in range(1, N + 1):
25
        # 内部边：in -> out
26
        if u == 1 or u == N:
27
            adj[in_node(u)].append((out_node(u), 0))
28
        else:
29
            adj[in_node(u)].append((out_node(u), 1 if degree[u] >= K else 0))
30
        # 对外边：out -> 相邻的 in
31
        for v in g[u]:
32
            adj[out_node(u)].append((in_node(v), 1))
33

34
    INF = 10**18
35
    dist = [INF] * total_nodes
36
    start = in_node(1)
37
    dist[start] = 0
38
    pq = [(0, start)]
39
    while pq:
40
        d, u = heapq.heappop(pq)
41
        if d != dist[u]:
42
            continue
43
        for v, w in adj[u]:
44
            nd = d + w
45
            if nd < dist[v]:
46
                dist[v] = nd
47
                heapq.heappush(pq, (nd, v))
48

49
    ans = dist[in_node(N)]
50
    print(ans if ans != INF else -1)
51

52
if __name__ == "__main__":
53
    solve()

E-二维前缀和+滑窗

题意：

有一个 N×N 的网格，每个格子有风景得分 Ai,j。
高桥选一个 K×K的子矩阵（连续的行和列）。
青木在这个子矩阵内选一个格子，将其分数改成 0（可以选已经是 0 的格子）。
青木的目的是最小化这个子矩阵的总分。
高桥的目的是最大化青木操作后的总分。
求最终的最大可能总分。

题解：

对于高桥选定的一个 $K \times K$ 区域，设区域内的格子的分数为 $a_1, a_2, \dots, a_{K^2}$

青木会选择一个格子改成 0，使得新总和最小

显然，青木会选择区域内分数最大的那个格子改成 0

所以青木操作后的总分 = 区域总和 - 区域内的最大值

高桥希望最大化这个值：

\text{score}(R) = \text{sum}(R) - \max(R)

其中 $R$ 是选定的 $K \times K$ 区域。

因此，问题转化为：

在 $N \times N$ 的网格中，找到所有 $K \times K$ 子矩阵，计算其总和减去最大值，并取最大值。

预先计算每个 $K \times K$ 子矩阵的总和（二维前缀和）。

同时需要快速得到子矩阵的最大值。

求子矩阵最大值可以用：

预处理每行的滑动窗口最大值（对每行用单调队列），然后对每列再套一次单调队列，得到每个 $K \times K$ 子矩阵的最大值。

算法设计：

计算二维前缀和 psum，方便 O(1) 求子矩阵和。
对每个行，计算长度为 $K$ 的滑动窗口最大值，得到 row_max[i][j] 表示第 i 行从 j 列开始的 K 个元素的最大值。
对 row_max 的每一列，计算长度为 $K$ 的滑动窗口最大值，得到 sub_max[i][j] 表示左上角为 (i,j) 的 K×K 子矩阵的最大值。
对于每个 (i,j) 子矩阵，计算和 = psum[i+K-1][j+K-1] - psum[i-1][j+K-1] - psum[i+K-1][j-1] + psum[i-1][j-1]，然后减去 sub_max[i][j]，取最大值。

1
def solve():
2
    import sys
3
    input = sys.stdin.readline
4
    N, K = map(int, input().split())
5
    A = [[0] + list(map(int, input().split())) for _ in range(N)]
6
    # 补一行一列方便前缀和
7
    prefix = [[0] * (N + 1) for _ in range(N + 1)]
8
    for i in range(1, N + 1):
9
        row_sum = 0
10
        for j in range(1, N + 1):
11
            row_sum += A[i-1][j]
12
            prefix[i][j] = prefix[i-1][j] + row_sum
13

14
    # 子矩阵和函数
15
    def sub_sum(x1, y1, x2, y2):
16
        return prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
17

18
    # 第一步：每行滑动窗口最大值
19
    row_max = [[0] * (N - K + 2) for _ in range(N + 1)]
20
    from collections import deque
21
    for i in range(1, N + 1):
22
        q = deque()
23
        for j in range(1, N + 1):
24
            while q and A[i-1][q[-1]] <= A[i-1][j]:
25
                q.pop()
26
            q.append(j)
27
            if q[0] <= j - K:
28
                q.popleft()
29
            if j >= K:
30
                row_max[i][j - K + 1] = A[i-1][q[0]]
31

32
    # 第二步：对行方向做滑动窗口最大值
33
    sub_max = [[0] * (N - K + 2) for _ in range(N - K + 2)]
34
    for j in range(1, N - K + 2):
35
        q = deque()
36
        for i in range(1, N + 1):
37
            while q and row_max[q[-1]][j] <= row_max[i][j]:
38
                q.pop()
39
            q.append(i)
40
            if q[0] <= i - K:
41
                q.popleft()
42
            if i >= K:
43
                sub_max[i - K + 1][j] = row_max[q[0]][j]
44

45
    ans = 0
46
    for i in range(1, N - K + 2):
47
        for j in range(1, N - K + 2):
48
            total = sub_sum(i, j, i + K - 1, j + K - 1)
49
            mx = sub_max[i][j]
50
            ans = max(ans, total - mx)
51

52
    print(ans)
53
if __name__ == "__main__":
54
    solve()

音乐

音乐

AWC68#

音乐

目录

音乐

音乐

AWC68-并查集/Dijkstra最短路/二维前缀和+滑窗

AWC68#

音乐

目录