7.6模拟赛总结

咕咕咕咕咕

我以为会过一车人

我因为人均170+

我有点意外

时间安排

7.30-9.00

看了看题 感觉T1显然状压 T2差不多会50 T3只会n^2 想了半天T2有什么别的做法 感觉都单调性 但是没有抓住这个想法

先打了T2暴力

9.00-10.00

感觉不太行 又想了一会T3 也没啥想法

然后打了T3的暴力

10.00-10.40

打了T1的暴力 想了一会 觉得T1的第二档是不是有什么神秘做法（因为是图） 感觉有点树形dp那味 但是不是很会

10.40-12.00

重新回想T1 反应过来可以分块掏决策单调性

然后努力回想怎么维护区间逆序数 这里我犯了一个错误 因为之前听了noi那个题 就觉得区间逆序数很复杂（实际上赛场推出来了） 推出来之后还觉得有点不明所以 （其实是因为noi那个题既有区间也有值域限制）

最后时间不够了（剩了20分钟 ） 就检查一下交题了

题目分析

T1

$f[S,op1,pos,op2]$ 当前走过的点的状态为$S$ 是否在终点的状态为$op1$ 在点$pos$ 上 上一条走过的边的状态是$op2$

转移分情况考虑

1. 正常模拟转移

2. $op1=0$ 的时候走到了一个标记点：可以考虑转成$op1=1$ 加上贡献

3. $op1=1$ 枚举一个没走过的标记点作为新起点 同时向$op2=1/0$ 转移

貌似我更擅长做状压dp一点

T2

$f[i]$ 表示最后一段分到$i$ 的最小代价

可以注意到 代价就是区间逆序对 再考虑每填入一个数 前面不同位置 从小到大 增加的值是不增的 形如 $5554444321111...$（值改变的位置就是出现了一个比它大的数）

然后可以$n^2$ 做

基于这个性质 可以证明决策单调性

所以有了$nlogn\sqrt{n}$ 的决策单调性套分块做法

upd

正解是cdq套分治决策单调性+类似莫队方法 维护两个指针 暴力跳区间逆序对

之所以需要cdq套一下 是因为分治决策单调性需要内容之间没有依赖 而这个有依赖 所以通过cdq分治搞出前面的dp值

T3

这个是真不会 只想了n^2或者撒点