F
明天学一下后缀自动机。
https://blog.csdn.net/qq_35649707/article/details/66473069
G
二合一，Kruskal重构树 + 线段树合并求子树众数。
昨天状态不好没时间写了。
D
除了硬核的分析与转化外，最优化问题可以用到的套路：
- 二分
- 流程
- 图论
- 随机
- 搜索
C
题意：给定一个序列，找至多两个段，没有相同的数，最大化总长度。
我的做法：枚举第二个点，第一个点往里缩，维护第二段的最大值。
反思：ljm很有可能会丢假结论，这时候我的作用就要体现出来，把假结论叉掉，而不是被他骗去写。
L
以后还是用标准检查流程去查一遍，确保正确性。
过编译，过样例，看一遍代码，检查各种常见错误：
- 数组大小
- 初始化
- 参数设置
- 访问非法
- LL（IO，运算）
- 取模（及时取模，负数）
- corner case
- 时间：big case
- 空间：算
E
需要练习一下 python，包括 IO 和一些基本操作。
LeetCode 1458
建立二维数组：
f = [[0 for j in range(m)] for i in range(n)]
不能写为
f = n * [m * [0]]
m * [0] 是对 0 进行深拷贝，没问题，但是 n * [m * [0]] 是对 m * [0] 进行浅拷贝，一个改则所有改。
LeetCode 685
- 以下代码：
def run(self, x, visited, graph):
visited[x] = 1
for y in graph[x]:
if not visited[y]:
self.run(y, visited, graph)
类中函数的第一个参数是 self，调用类中函数时需要用 self.函数名。
2. 以下代码：
def get(self, x, pr):
if pr[x] == x:
return x
pr[x] = self.get(pr[x], pr)
return pr[x]
(1) Python 中的 return 语句中，不能有 =，写作 return pr[x] = self.get(pr[x], x) 甚至于写 return pr[x] = 1 都会报错。
(2) Python 中没有三目运算符，但是可以用以下方法来写：
def get(x, f):
ret = x if x == f[x] else f[x] = get(x, f[x])
return ret
a if 条件 else b：如果满足条件，值为 a，否则为 b。
3. j 从 n-1 枚举到 0。
(1) 下面写法：
j = n
while j >= 0:
...
j -= 1
可能会出问题，因为如果中间有 continue，那么就不能成功使 j -= 1。如果要实现，那么每个 continue 前要写 j -= 1。
(2) Python 中没有自增、自减运算符，只能写 j += 1, j -= 1。
(3) 解决办法二：可以考虑在循环开始的时候减一。
j = n + 1
while j >= 1:
j -= 1
...
(4) 解决办法三：可以考虑用 range 来实现。
for j in range(n - 1, -1, -1):
...
LeetCode 131
- 切片
a = [1, 2, 3, 4, 5]
b = a[::-1]
c = a[::-1]
b[0] = 10
print(a)
print(b)
print(c)
(1) 切片格式与基本参数
s[a:b:c]
切片的第一个参数：起点
切片的第二个参数：终点
切片的第三个参数：步长
(2) 切片拷贝了选中的每一位的信息。
对于基本类型，实现的是深拷贝；
对于列表、元组等对象，实现的是浅拷贝。
(3) 反转：a[::-1]
需要学习这几个点：
- 类相关
- Input
- Output
别人这道题的代码：
class Rational:
def __init__(self, p, q):
self.p = p
self.q = q
def __add__(self, other):
return Rational(self.p * other.q + self.q * other.p, self.q * other.q)
def __lt__(self, other):
return self.p * other.q < self.q * other.p
if __name__ == '__main__':
t = int(input())
for z in range(1, t + 1):
n = int(input())
q = [Rational(0, 1)] * n
for i in range(n):
a, b = map(float, input().split(':'))
a = int(a * 1000)
b = int(b * 1000)
q[i] = Rational(a, a + b)
q.sort()
cur = Rational(0, 1)
cnt = 0
for i in range(n):
if cur + q[i] < Rational(1, 1):
cur += q[i]
cnt += 1
else:
break
print(f'Case #{z}: {cnt}')
找几份代码，粘到模板上，这是目前性价比最高的办法。