Weekly Contest 320
今天蛮惨的，第四题在最后一分钟才写出来
唯一的好消息是连续三场一次过，没有吃到 penalty
1. Number of Unequal Triplets in Array
看到 n <= 100 就无脑用三层循环，懒的想
2. Closest Nodes Queries in a Binary Search Tree
不想管他的树，直接 dfs 抽出来到一个阵列后
再对每个 query 做 binary search (upper_bound, lower_bound)
3. Minimum Fuel Cost to Report to the Capital
最佳解是每个 node 都等人到齐之后再一起出发
所以这个 node 要花的就是 ceil(子树大小/座位大小)
记得 root 不需要加就好
4. Number of Beautiful Partitions
这题我搞很久，主要是没发现我的作法最后一段没超过 minLength 也会算进去
debug 超久，搞到差点写不完
首先，头一定要是质数，尾一定不能是质数
接着，找出那些可以当分割点的质数位置
可以当分割点的条件就是前面不能是质数，否则切下去你前一个人的结尾就变成质数
找出所有分割点的 index，例如 [0, 4, 7, 9]
接着就用 dp
定义 dp[i][j] 是考虑到 j 为止做成 i 个切割的切割法
则 dp[i][j] = dp[i][j-1] + dp[i-1][pre[j]]
^^^^^^^^^^^^^^^ -> 这项代表真的切 j 的方法总数
其中 pre[j] 指的是离 j 最近但距离 >= minLength 的 index
复杂度是算好 pre 的 O(n^2) 加上更新 dp 的 O(nk)
总共 O(n^2 + nk)
这次排 536 名，不知道会不会扣分