Re: [闲聊] LeetCode Weekly Contest 413

楼主: involution (内卷是好文明)   2024-09-01 12:00:11
还行
https://i.imgur.com/aPpvWJd.png
Q1:
等价于xy相加的奇偶是否一致
可以直接用字符的奇偶来做
Q2:
维护一个大小为 k 的 max heap
Q3:
第一感 从大的开始挑 如果全场只有某一行有最大的值 那显然可以无脑挑
如果不能呢 那就递回下去每个有最大值的行都试一遍
决定能不能挑的状态受: 1) 哪些行被挑过 2) 最后挑了谁 来决定
因为行数 <= 10 且值 <= 100, 状态总共有 2^10 * 100 ~= 10^5
用 memorization 就可以了
我一开始 TLE 还在想是不是递回常数太大要优化一下
吃了两次之后才发现是我 memorization 最后一步没有存进去 = =
早知道用 python 无脑 lru_cache
Q4:
看到 n <= 2000, 代表 O(n^2) 应该扛的住
直接求出 n^2 个解再拿去 query 也可以
令 X[a][b] 是 a..b 的 XOR SCORE
根据定义 有 X[a][b] = X[a][b-1] ^ X[a+1][b]
所以可以 O(n^2) 求出 X[]
我们要求的是 subarray 里 XOR SCORE 最大的
因此有 Ans[a][b] = max(Ans[a+1][b], X[a][a], X[a][a+1], ..., X[a][b])
我们可以花 O(n^2) 先求出所有 Y[a][b] := max(X[a][a], ..., X[a][b])
就能再花 O(n^2) 求出 Ans[]
感觉有点绕 不知道有没有更好的做法
作者: oin1104 (是oin的说)   2024-09-01 12:03:00
干 我哭了 你怎么这么强
作者: sustainer123 (caster)   2024-09-01 12:04:00
大师 我第三题直接死去 我以为要dp
作者: DJYOMIYAHINA (通通打死)   2024-09-01 12:06:00
第三题我知道要这样 但我写不出来 唉==
作者: Furina (芙宁娜)   2024-09-01 12:08:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com