Process

今天真的是炸掉了，第二题本来打出正解，没开long long,最后20分钟一直在调，没调出来，但是没交暴力，结果只有5分，第三题20分暴力忘记删调试信息，爆零。这两题是真的不应该失误的，如果这两题能拿到该有的分的话就能进rank20了。倒是第一题还比较稳，打的一维RMQ，不出意外地拿了60分。

Score

60 + 5 + 0 = 65

Problems

phalanx [DONE]

正解是二维RMQ，但是要进行空间优化，定义 f[i][j][k]表示以(i,j)为左上角,大小为 2^k 的正方形方阵的最大(最小)值是多少。 对于每个询问,最多 8 个正方形即可覆盖。 但是由于矩阵内的值<=3000且数据随机，其实记一个整个矩阵的Max和Min，跑暴力的时候判断如果当前答案等于Max或Min直接跳出，这样也能卡成满分。。。

photo [DONE]

我们可以建出一个图，然后跑树形Dp 定义 f[i]表示第 i 棵子树的方案数是多少。 转移时,相当于有很多的儿子 s , s ... s (设每个儿子的子树大小为 size),相当于对于一个序列中,先选 1 个位置给 s ,再在余下的位置中,选 2 个位置给 s ...,相当于一些组合数的乘积再乘以每个儿子内部的方案数。 组合数预处理出来，然后注意判无解情况即可。

position [TODO]

还没改

Learn

  1. 以后组合数和快速幂取模一定要记得开long long