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   : [e-mail]
# @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 + 7def main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdinn, 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] = 1for i in range(m + 1):dp[0][i] = 1for 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] %= modprint(dp[n][m])if __name__ == "__main__":main()

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

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : [e-mail]
# @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.stdinn = int(fp.readline())min_x, min_y, max_x, max_y = 10 ** 20, 10 ** 20, -10 ** 20, -10 ** 20uy, 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_yif 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 ** 13c = 0ans = 1e18while c < 400:m0, m1 = lo + (hi - lo) / 3, hi - (hi - lo) / 3a0, a1 = get(m0), get(m1)if a0 > a1:lo = m0else:hi = m1ans = min(ans, a0)ans = min(ans, a1)c += 1print(ans)if __name__ == "__main__":main()