今天还行 不过因为这次难度比以往简单
所以把 < 写成 <= 扣的五分钟就损失很大了
https://i.imgur.com/FRr45LE.png
1. Left and Right Sum Differences
直接照他说的做出 leftSum 和 rightSum 就可以了
leftSum[0] = 0
leftSum[i] = leftSum[i-1] + num[i-1]
然后因为 n <= 1000，所以甚至用 O(n^2) 的写法也没问题
2. Find the Divisibility Array of a String
我们要计算出 div，其中 div[i] 为 word[0..i] % m 是否是 0
可以发现
word[0..i] % m == (word[0..(i-1)] * 10 + word[i]) % m
== ((word[0..(i-1)] % m) * 10 + word[i]) % m
所以就一直 *10 加上 word[i] 再看 %m 后是不是 0 即可
注意 10^9 * 10 会超 32-bit
3. Find the Maximum Number of Marked Indices
首先，能不能 mark 跟 i, j 的位置无关所以我们就无脑先 sort
接着因为组数一定 <= n/2，假设答案是 k 且是以下几组
(a_1, b_1), ..., (a_k, b_k)
观察到，我们一定可以让
a_1 <= a_2 <= ... <= a_k <= b_1 <= b_2 <= ... <= b_k
因为如果有一组 a_i <= a_j <= b_j <= b_i 的话
我们可以改成配对 (a_i, b_j), (a_j, b_i) 也是合法的
接着我们发现我们可以让
a_1 = nums[0], a_2 = nums[1], ...
b_k = nums[n-1], b_{k-1} = nums[n-2], ...
因为 a 只会变小 b 只会变大所以还是一定合法
因此只要用 two-pointer
让 a 从 0 开始，b 从 n/2 开始 greedy 的取就好了
因为如果存在解，就必定存在有 nums[0] 的解...
把 < 写成 <= 错了一次 :(
4. Find the Maximum Number of Marked Indices
首先观察到，会失败若且唯若 grid[0][1] > 1 且 grid[1][0] > 1
因为如果其中一个 <= 1, 可以来回移动到宇宙毁灭再出发
这样就一定每一格都可以走
接着看奇偶性，偶数的点一定只能在 time 是偶数时抵达
因此如果一个偶数的点的值是奇数 2k + 1
他可能的最佳解最好就是 2k + 2
我们可以先扫一遍 grid 处理完
因为来回移动的特性，我们发现如果存在邻近的点能在 t = k 时走到
则从那个邻近的点过来的最佳解就会是 max(k + 1, grid[x][y])
所以就用 dijkstra 做一做就好了，O(|V| + |E|log|E|)
因为 |E| <= 4|V| 所以就是 O(|V|log|V|)