AtCoder abc130

F题提交了无数遍，最后发现是三分求解的写法错了
C - Rectangle Cutting
盲猜都在xy的中心点时可以无限分割，否则不能
D - Enough Array
前缀和二分求位置
E - Common Subsequence
公共子序列求有几种组合
设$dp[i][j]$代表s取到i t取到j时的序列数
当s[i]!=t[j] 时
$dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]$
因为$dp[i][j]$可以视作为$dp[i-1][j]$添上s[i]后总的序列数
$dp[i-1][j]$是$dp[i-1][j-1]$添上t[j]的序列数
另一边$dp[i][j-1]$也将$dp[i-1][j-1]$包含在内，因此计算了两次$dp[i-1][j-1]$需要减去
当s[i]==t[j]时，$dp[i][j]$在$dp[i-1][j-1]$的序列上各增加一个长度，因此在刚才的计算后再加上$dp[i-1][j-1]$

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo.cn
# @desc     :
# @file     : atcoder.py
# @software : PyCharm
import bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)

mod = 10 ** 9 + 7


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    n, m = map(int, fp.readline().split())
    s = list(map(int, fp.readline().split()))
    t = list(map(int, fp.readline().split()))
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(m + 1):
        dp[0][i] = 1

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            dp[i][j] %= mod
    print(dp[n][m])


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

F - Minimum Bounding Box
max-min显然是凸函数（忘了证明方法），暴力三分可以过
还有一种不那么暴力的解法：
不需要维护所有的x y
只需要维护向上、向下的y中最大值与最小值
向左向右x最大值与最小值

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo.cn
# @desc     :
# @file     : atcoder.py
# @software : PyCharm
import bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    n = int(fp.readline())
    min_x, min_y, max_x, max_y = 10 ** 20, 10 ** 20, -10 ** 20, -10 ** 20
    uy, dy, lx, rx = [], [], [], []
    for i in range(n):
        items = fp.readline().strip().split()
        x, y = int(items[0]), int(items[1])
        d = items[2]
        if d == 'U':
            uy.append(y)
            min_x, max_x = min(min_x, x), max(max_x, x)
        elif d == 'D':
            dy.append(y)
            min_x, max_x = min(min_x, x), max(max_x, x)
        elif d == 'L':
            lx.append(x)
            min_y, max_y = min(min_y, y), max(max_y, y)
        else:
            rx.append(x)
            min_y, max_y = min(min_y, y), max(max_y, y)
    uy.sort()
    dy.sort()
    lx.sort()
    rx.sort()

    def get(t):
        x0, y0, x1, y1 = min_x, min_y, max_x, max_y
        if len(uy) > 0:
            y0 = min(uy[0] + t, y0)
            y1 = max(uy[-1] + t, y1)
        if len(dy) > 0:
            y0 = min(dy[0] - t, y0)
            y1 = max(dy[-1] - t, y1)
        if len(rx) > 0:
            x0 = min(rx[0] + t, x0)
            x1 = max(rx[-1] + t, x1)
        if len(lx) > 0:
            x0 = min(lx[0] - t, x0)
            x1 = max(lx[-1] - t, x1)

        return (y1 - y0) * (x1 - x0)

    lo, hi = 0, 10 ** 13
    c = 0
    ans = 1e18
    while c < 400:
        m0, m1 = lo + (hi - lo) / 3, hi - (hi - lo) / 3
        a0, a1 = get(m0), get(m1)
        if a0 > a1:
            lo = m0
        else:
            hi = m1
        ans = min(ans, a0)
        ans = min(ans, a1)
        c += 1
    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
73
74
75
76
77
78
79
80
81
82
83