Atcoder ABC159

总体来说本期比较简单

C - Maximum Volume
答案显然是$O(N^3)$

D - Banned K
先统计总的，然后减去选到的那个数再重新计算

E - Dividing Chocolate
既然n范围是10，那么在n的宽度上做一个位操作，若i位与i+1位之间有切割，i位设为1，枚举横方向的切割方案，然后在竖方向上做贪心

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(1000)


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    n, m, K = map(int, fp.readline().split())
    a = []
    for i in range(n):
        s = fp.readline().strip()
        a.append(s)
    sm = [[0] * m for _ in range(n + 1)]
    for j in range(m):
        for i in range(n):
            sm[i + 1][j] = sm[i][j] + ord(a[i][j]) - ord('0')

    ans = 10 ** 18
    for mask in range(1 << (n - 1)):
        last = 0
        temp = []
        div_cnt = 0
        ac = 1
        for j in range(n):
            if mask >> j & 1 or j == n - 1:
                b = []
                for k in range(m):
                    x = sm[j + 1][k] - sm[last][k]
                    if x > K:
                        ac = 0
                    b.append(x)
                last = j + 1
                temp.append(b)
            if mask >> j & 1:
                div_cnt += 1
        if ac == 0:
            continue
        l = len(temp)
        t = [0] * l
        for j in range(m):
            d = 0
            for i in range(l):
                t[i] += temp[i][j]
                if t[i] > K:
                    d = 1
            if d:
                div_cnt += 1
                for i in range(l):
                    t[i] = temp[i][j]
        ans = min(ans, div_cnt)
    print(ans)


if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

F - Knapsack for All Segments

观察了一下，发现在做到 i位时，可以去计算$F(i,sum)$
其中sum是当前计算的和，F代表方案数
$F(i,sum)=\sum F(j,sum-a[i])\ast (n-i)$
但是这样是$O(N^2\ast S)$的三重循环，因此要记录一下前缀和$G(sum)=\sum F(i,sum)$

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(1000)


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    n, S = map(int, fp.readline().split())
    a = list(map(int, fp.readline().split()))
    dp = [0] * (S + 1)
    mod = 998244353
    ans = 0
    for i in range(n):
        if a[i] == S:
            ans += (i + 1) * (n - i)
            ans %= mod
        elif S - a[i] > 0:
            ans += dp[S - a[i]] * (n - i)
            ans %= mod
            for j in range(S, -1, -1):
                if j >= a[i]:
                    dp[j] = (dp[j] + dp[j - a[i]]) % mod
            dp[a[i]] += i + 1
            dp[a[i]] %= mod
    print(ans)


if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46