AWC67#

非常有意思的一场AWC，AB模拟难度挺高，C是完全背包板子，D是Floyd板子，E是bash尼莫博弈，质量在AWC中感觉算是很高的了

Tasks - AtCoder Weekday Contest 0067 Beta

难度：

Easy: A

Mid: C、B、E

Hard: D

A-模拟

按照题意给定的三种情况模拟即可

1
n, q = map(int, input().split())
2
score = [0] * (n + 1)
3
for _ in range(q):
4
    op = list(map(int, input().split()))
5
    if op[0] == 1:
6
        _, a, b, v = op
7
        score[a] -= v
8
        score[b] += v
9
    elif op[0] == 2:
10
        _, x, l, r = op
11
        ans = 0
12
        for i in range(l, r + 1):
13
            if score[i] > score[x]:
14
                ans += 1
15
        print(ans)
16
    else:
17
        _, l, r, v = op
18
        for i in range(l, r + 1):
19
            score[i] += v

B-Kadane

给定 N 天的盈亏数据序列，问题是为每个 k=1,2,…,N 找出 “前 k 天的连续子序列的最大和”

Kadane 算法（最大子数组和）生成 “每个前缀 1..k 的答案”。

cur ：在当前位置结束的最大子序列和

icur=max(Bi, cur+Bi)

best ：到目前为止的最大区间和（ 1..i ）

best=max(best, cur)

1
n = int(input())
2
b = list(map(int, input().split()))
3
pre = [0] * (n + 1)
4
for i in range(n):
5
    pre[i+1] = pre[i] + b[i]
6
cur = b[0]
7
best = b[0]
8
print(best)
9
for i in range(1,n):
10
    x = b[i]
11
    cur = max(x,cur + x)
12
    if cur > best:
13
        best = cur
14
    print(best)

C-完全背包

每个食品可以无限购买，目标是使总天数达到或超过D所需要的最小成本

1
n, d = map(int, input().split())
2
a = [tuple(map(int, input().split())) for _ in range(n)]
3
INF = 10**18
4
dp = [INF] * (d + 1)
5
dp[0] = 0
6
for c, f in a:
7
    for j in range(d + 1):
8
        if dp[j] == INF:
9
            continue
10
        nxt = min(d, j + f)
11
        dp[nxt] = min(dp[nxt], dp[j] + c)
12
print(dp[d])

D-Floyd

正解貌似是Dijkstra，但是Floyd可做

1
n, m = map(int, input().split())
2
s = [0] + list(map(int, input().split()))
3
INF = 10 ** 15
4
dist = [[INF] * (n + 1) for _ in range(n + 1)]
5
for i in range(1, n + 1):
6
    dist[i][i] = 0
7
for _ in range(m):
8
    u, v, w = map(int, input().split())
9
    dist[u][v] = min(dist[u][v], w)
10
    dist[v][u] = min(dist[v][u], w)
11
# Floyd
12
for k in range(1, n + 1):
13
    for i in range(1, n + 1):
14
        if dist[i][k] == INF: continue
15
        for j in range(1, n + 1):
16
            nd = dist[i][k] + dist[k][j]
17
            if nd < dist[i][j]:
18
                dist[i][j] = nd
19
c = [0] * (n + 1)
20
for i in range(1, n + 1):
21
    cnt = 0
22
    for j in range(1, n + 1):
23
        if i == j: continue
24
        if dist[i][j] > s[i]:
25
            cnt += 1
26
    c[i] = cnt
27
ans = 0
28
for i in range(1, n + 1):
29
    for j in range(i + 1, n + 1):
30
        if dist[i][j] <= s[i] and dist[i][j] <= s[j]:
31
            if c[i] == c[j]:
32
                ans += 1
33
print(ans)

E-bash尼莫博弈

尼莫博弈的变题，

1
n,k = map(int, input().split())
2
a = list(map(int, input().split()))
3
xor_sum = 0
4
for x in a:
5
    xor_sum ^= (x % (k + 1))
6
if xor_sum != 0:
7
    print("Takahashi")
8
else:
9
    print("Aoki")

一系列尼莫博弈结论：

（1）尼莫博弈

有 n 堆硬币，每堆有若干枚
两人轮流行动，每次可以从任意一堆中拿走任意数量的硬币（至少1枚，最多全拿）
取走最后一枚硬币的人获胜
小明先手，员工后手

问：员工(后手)能否获胜？

如果所有堆的硬币数异或（XOR）结果为0，则后手必胜；否则先手必胜。

1
def f(a:list):
2
    xor_ = 0
3
    for x in a:
4
        xor_ ^= x
5
    if xor_ == 0:
6
        return 1 # 后手胜
7
    else:
8
        return 0 # 后手输

（2）反尼莫游戏

有 n 堆硬币，每堆若干枚
两人轮流，每次从某一堆中取至少 1 枚（可以全取）
取走最后一枚硬币的人输
小明先手，员工后手

如果所有堆都只有 1 枚硬币：
- 堆数为奇数 → 先手必败，后手胜利
- 堆数为偶数 → 先手必胜，后手失败
如果存在至少一堆超过 1 枚硬币：
- 所有堆异或为 0 → 先手必败，后手失败
- 所有堆异或 ≠ 0 → 先手必胜，后手胜利

1
def f(a:list):
2
    n = len(a)
3
    all_ = all(x == 1 for x in a)
4
    if all_:
5
        if n % 2 == 1:
6
            return 1 # 后手胜
7
        else:
8
            return 0
9
    else:
10
        xor_ = 0
11
        for x in a:
12
            xor_ ^= x
13
        if xor_ == 0:
14
            return 1 # 后手胜
15
        else:
16
            return 0

（3）Bash模拟转尼莫模拟

有 n 堆石子，每堆有 aᵢ 个
两人轮流，每次可以从某一堆中取 1 到 k 个石子
取走最后一颗石子的人获胜
小明先手，员工后手

计算所有堆的 aᵢ mod (k+1) 的异或值：

如果异或值 = 0，则先手必败，后手（员工）必胜 → 输出 YES
如果异或值 ≠ 0，则先手必胜，后手（员工）必败 → 输出 NO

1
def solve():
2
    T = int(input())
3
    for _ in range(T):
4
        n, k = map(int, input().split())
5
        piles = list(map(int, input().split()))
6
        # 计算所有堆对(k+1)取模后的异或值
7
        xor_sum = 0
8
        for x in piles:
9
            xor_sum ^= (x % (k + 1))
10
        if xor_sum == 0:
11
            print("YES")  # 先手必败 → 后手胜
12
        else:
13
            print("NO")  # 先手必胜 → 后手败
14
if __name__ == "__main__":
15
    solve()

（4）Bash博弈

有 n 元钱
两人轮流，每次可以拿 1 到 m 元
取走最后一元钱的人获胜
小明先手，员工后手

1
def solve():
2
    T = int(input())
3
    for _ in range(T):
4
        n, m = map(int, input().split())
5
        if n % (m + 1) == 0:
6
            print("YES")  # 先手必败 → 员工胜
7
        else:
8
            print("NO")   # 先手必胜 → 员工败
9

10
if __name__ == "__main__":
11
    solve()

音乐

音乐

AWC67#

音乐

目录

音乐

音乐

AWC67-完全背包/Floyd/bash尼莫博弈

AWC67#

音乐

目录