AWC66#

Tasks - AtCoder Weekday Contest 0066 Beta

AB的题意很长，像是做阅读理解，CD倒是很板子，评价说CD比AB容易，E赛时写的DFS，当然是TLE了，正解是状压DP

A-模拟

题意是对于给定序列a以及给定的操作序列b，对于每个bi将a[i]的值加到a[i+1]上，如果i+1 > n，则置零

1
n,q = map(int,input().split())
2
a = list(map(int,input().split()))+[0]
3
for _ in range(q):
4
    b = int(input()) - 1
5
    a[b+1] += a[b]
6
    a[b] = 0
7
print(*a[:-1])

B-模拟

雷霆题目，题目描述像是写小作文，理解起来非常困难，大致的题意如下：

有 N 部手机，初始电量 Ai。
阈值 L：电量 ≤ L 的手机立即关机（无法使用）。
在时间 0，可以选择至多 K 部当前开机的手机连接到移动电池，这些手机在接下来的 Y 秒内电量不会减少。
时间从 1 到 Y，每秒：
1. 未连接电池且仍开机的手机，电量减少 1。
2. 电量变得 ≤ L 的手机立即关机（无法再使用）。
问：Y 秒后，最多还有多少手机开机（包括连接电池的）？

考虑三种情况：

初始电量 ≤L，不予考虑

初始电量>L+Y，不连接也能在最后可以使用

其余情况，不充电会关机

1
  N, L, K, Y = map(int, input().split())
2
  A = list(map(int, input().split()))
3
  normal = []
4
  need = []
5
  for a in A:
6
      if a <= L:
7
          continue
8
      if a > L + Y:
9
          normal.append(a)
10
      else:
11
          need.append(a)
12
  # 优先连接必须连的
13
  connect = min(K, len(need))
14
  ans = len(normal) + connect
15
  print(ans)

C-差分

按照题意差分即可

1
n,q = map(int,input().split())
2
w = [0] + [0] + list(map(int,input().split())) + [0]
3
a = [0]*(n+3)
4
for _ in range(q):
5
    l,r,d = map(int,input().split())
6
    a[l] += d
7
    a[r+1] -= d
8
pre = [0]*(n+3)
9
ans = 0
10
for i in range(n+2):
11
    pre[i+1] = pre[i] + a[i]
12
    if 2 <= i <= n+1 and pre[i] - w[i] >= 0:
13
        ans += 1
14
print(ans)

D-二分答案

经典的二分答案求最小化最大值

1
n,k = map(int,input().split())
2
a = list(map(int,input().split()))
3
def check(mid):
4
    cur = 0
5
    cnt = 1
6
    for x in a:
7
        if x > mid:
8
            return False
9
        if cur + x > mid:
10
            cnt += 1
11
            cur = x
12
        else:
13
            cur += x
14
    return cnt <= k
15

16
left =  max(a) - 1
17
right = sum(a)
18
while left + 1 < right:
19
    mid = (left + right) // 2
20
    if check(mid):
21
        right = mid
22
    else:
23
        left = mid
24
print(right)

E-状压DP

计算从 S 到 T 的所有简单路径上每条路径的顶点权重之和，并求得平均值

1
import sys
2

3
def main():
4
    input = sys.stdin.readline
5

6
    N, M, S, T = map(int, input().split())
7
    S -= 1
8
    T -= 1
9

10
    c = [int(input()) for _ in range(N)]
11

12
    adj = [0] * N
13
    for _ in range(M):
14
        u, v = map(int, input().split())
15
        u -= 1
16
        v -= 1
17
        adj[u] |= 1 << v
18
        adj[v] |= 1 << u
19

20
    size = 1 << N
21

22
    # dp_count[mask][v]: number of simple paths from S to v using exactly vertices in mask
23
    # dp_sum[mask][v]: total score sum over those paths
24
    dp_count = [[0] * N for _ in range(size)]
25
    dp_sum = [[0] * N for _ in range(size)]
26

27
    start_mask = 1 << S
28
    dp_count[start_mask][S] = 1
29
    dp_sum[start_mask][S] = c[S]
30

31
    for mask in range(size):
32
        if (mask & start_mask) == 0:
33
            continue
34
        for v in range(N):
35
            cnt = dp_count[mask][v]
36
            if cnt == 0:
37
                continue
38
            sm = dp_sum[mask][v]
39

40
            nxt = adj[v] & (~mask)
41
            while nxt:
42
                lsb = nxt & -nxt
43
                u = lsb.bit_length() - 1
44
                nmask = mask | lsb
45
                dp_count[nmask][u] += cnt
46
                dp_sum[nmask][u] += sm + cnt * c[u]
47
                nxt ^= lsb
48

49
    total_count = 0
50
    total_sum = 0
51
    bit_t = 1 << T
52
    for mask in range(size):
53
        if (mask & bit_t) == 0:
54
            continue
55
        total_count += dp_count[mask][T]
56
        total_sum += dp_sum[mask][T]
57

58
    ans = total_sum / total_count
59
    print("{:.10f}".format(ans))
60

61
if __name__ == "__main__":
62
    main()

音乐

音乐

AWC66#

音乐

目录

音乐

音乐

AWC66-二分答案/状压DP

AWC66#

音乐

目录