2/17考试总结

时间安排

7:40–7:50 读题，T1 貌似是签到，T2,T4 DP,T3看起来很不可做。
7:50–8:00 T1,差分一下然后模拟就行了。
8:00–10:20 T2,注意到值域很小，可以考虑状压，想到一个状压状态数较少的 dp ，然后挂得彻底。发现有一些情况没考虑到，那就不得不增加状态维度，可这样的话状态数就非常大。想了好久没有想到什么更小的表示，于是就硬着头皮写了。可以拿到 70 分左右。
10:20–12:00 T4,考虑怎么 dp ，为了不重，那么就要尽可能少的操作，问题在于对于一个状态我压根不知道最少的操作是什么。分讨一下发现情况非常复杂，不知道怎么 dp 。写了个dfs 暴力。

回顾反思

T2:
基本思路和正解差不多，不过赛时做法复杂度较劣，主要有两点。
一是 dp 转移设计上，题目要求划分为若干个子段，于是我每次都要枚举最后一段的左端点。但实际上一段的信息非常好维护，于是可以考虑直接在 dp 状态里加入当前未结束的段的信息，对于一个新元素考虑是另起一段还是加入当前段就行了。
二是状压状态数上，直接暴力枚举状压的状态复杂度很大，但是显然很不满，通过 bfs 处理出有用的状态，发现只有 100 多个非常少，于是复杂度就对了。
对于这种一段的信息非常简单的可以考虑在 dp 时直接维护当前未结束段的信息。
状压的状态数很大时，一定要想想是不是每个状态都真的有用，去 bfs/dfs 一下会发现有用的状态往往很少。
T3:
貌似很高深。
T4:
比赛的时候压根不知道从何下手设计 dp 。是否必要操作，操作的先后没法确定等一系列问题。
由于本题操作的一些优秀性质，发现对于一个结束态，有些区间如果要操作必然是最后几次操作，将其去掉后剩下的也能如此划分。于是划分出若干个块，每个块若要操作与相邻的块有一定依赖关系，于是就有了操作的先后关系，枚举相邻的几个块是否操作了，根据分讨依赖关系就可以得到当前块操作是否是必要的。
已知操作后的最终序列，考虑将操作序列映射到原序列。比如本题可以先把对应操作区间划分出来，讨论区间之间的依赖关系。