时间安排
7:35-8:20
直接开 T1，发现不会做。
8:20-8:40
把 T2 T3 T4 都看了，T2 和 T1 一样是我必不可能会的人类智慧题，T3 看上去就很劝退，T4 是我喜欢的树上问题，直接倒序开题。
8:40 - 10:20
想了 T4，得到了一个 \(O(n^2)\) 的暴力，高达 40 分，直接开写。写完之后过不了第二个样例，发现假了，改一句话就能变成对的，但是时间复杂度会变成 20 分的 \(O(n^3)\)。很喜欢一句话 :20 分狗都不写。然后想了一会怎么 \(O(n^2)\)，没有思路，还是改成 \(O(n^3)\) 了。然后想了想链的部分分，这不前几天讲的倍增优化 DP 的原题？5 min 写完。
10:20-11:00
T3 10 分直接上组合数，然后发现 \(n,m \leq 8\) 可以爆搜，用我的组合数算了一下，发现 \(n,m=8\) 的时候有 8e8 种状态？？？还是写了爆搜，想着应该可以剪枝，但是直接爆搜跑 \(n,m=8\) 飞快，瞪了一会发现是组合数写错了，实际上只有 3000 的状态。
11:00-11:15
写了 T2 的爆搜。
11:15-11:20
T1 写了最弱智的 10 分。
11:20-11:50
想 T3 的特殊性质。造了几组小数据，发现只有一个箱子的情况就是没有箱子的情况减掉一个组合数，最后几 min 极限写完。
总结反思
- 打了接近 30 场模拟赛，第一次 T1 T2 同时保龄，都是弱智错误，如果最后能留出时间检查的话会多 40 分。
- 作为没智商的选手，智商题做不了一点。
题解
A.数组
观察发现进行一次操作后改变的是差分数组的顺序。
B.排列的 LIS
通过答案的上下界构造。
C.推箱子
考虑 DP。直接做很棘手，于是设两个状态，\(f_{i,j}\) 表示之前一直往下，下一步开始往右走的方案数，\(g_{i,j}\) 表示表示之前一直往右，下一步开始往下走的方案数。然后直接转移是 \(O(n^3)\)，因为只有区间加，使用差分优化做到 \(O(n^2)\)。
D.地铁
链的情况就是简单倍增优化 DP，考虑在树上怎么做。可以发现一条路径可以在 LCA 处拆成两部分，对于这两部分到达 LCA 前的路径可以当做链来做，然后只需判断是否存在一条路径能横跨 LCA，转化为二维数点问题使用树状数组或主席树维护。
标签：11,10,20,23,T2,29,40,T3 From： https://www.cnblogs.com/cannotdp/p/17796969.html