2017-10-23 & 2017-10-24 集训总结

2017-10-23
①考试
今天的题，从难度来看除了第二题的后面50分可能有点超纲以外，其它的分从难度来说至少能拿90%。但问题很严重：我丢了至少一半的分。

T1 正解很好想，于是我就愉快地去打组合数，结果爆炸了10分，原因是出现了 C(n, m), n < m 的情况。出现这个错误一是因为我没有考虑到这种情况，二是我的组合数没有打特判。为了避免再次出现这种错误，以后打组合数都要加上特判了。反正都是O(1)的算法。

T2 只打了30分暴力。另外20%的暴力我去想斜率优化去了，但是发现因为符号问题无法换成斜率式我就走了；考虑到100%的情况可能要开100个 DQ，而我连特殊情况都没有想出来，于是我就走了。。。其实另外那20%是用一个很傻的贪心做的，而正解也的确要用 10 * 10 的数量级的单调队列，所以我觉得这20分其实挺遗憾的。

T3 最爆炸的一道题。我本来还在开心说自己 KMP 没有打错，结果后面递推的时候错了5个地方。。。

然后就活生生地少了80分。

总的来说，从能力上来看 300 分的题我应该至少能拿 230，很遗憾第三题爆炸了。

2017-10-24
①考试
T2 原题，然而大家还是打挂了。还好我记得检查了无解的情况。（好吧，大家打挂的原因可能是对他们来说不是原题）

T1 用暴力一维 RMQ 骗了 60 分，虽然我知道有嵌套数据结构这种专门搞这个问题的利器，但是我不会。。。所以这道题的收获还是挺大的。学习了新的 二维 RMQ 以及二维 BIT，二维线段树也即将收入囊中了。
值得一提的是这题 a < 3000，于是可以 short 卡空间而不是用题解上说的另类 RMQ（用正方形代替长方形，最多走 8 次）。更值得一提的是卢兄的寻址优化：这告诉了我们倍增数组的 log 部一定要放在前面，就像这样：
f[10][10][805][805]
而不是：
f[805][805][10][10]
总得来说 T1 的收获挺大的。

T3 也是一道收获比较大的题，至少思维锻炼得可以。可惜，我暴力的 50 分又打挂了，又只剩 30 分了，原因竟是局部变量未初始化。我的天，这种问题竟然还在犯，简直爆炸。。。我也不知道说什么。。。
这道题的暴力正解跟我稍有不同，也是影响我打不出正解的原因。我是直接动态维护距离和，而正解是把距离和差分了，并且发现差分后的距离和是单调递增的，由此可以用线段树加二分各种乱搞。。。反正我的9K线段树终究是过了，只不过很艰辛。这个问题，我还没有找到很好的解决方案。

Day 1: 120(230) 吃土
Day 2: 190(240) 继续吃

改题：
Day 1: 250 吃土
Day 2: 300 不吃了