退役前竟然又见一次栋栋

好像太水了... 补几句吧
第一题 Codeforces 174C
第二题 dp优化不多说 说线段树超纲的目测和去年一样继续打脸?
第三题 这题思路还是挺自然的...想不到更好的做法就可以开始码了 拼手感...

稍微说一下第三题
假设要移动的棋子走过的路径上的格子依次是a1,a2, .. , an (a1和an就是起点和终点)
那么首先要把空位(把它当做一个特殊的棋子来看待会比较自然)挪到a2 然后让它和目标棋互换 这时目标棋到了a2 下一步想走到a3的话 空位就必须先到a3去 依此类推
注意一下这个过程
首先 空位挪到a2 这个挪是有限制的 那就是不能经过a1
然后 空位从a1挪到a3 也是有限制 即不能经过a2 后面的从a2到a4之类的也都一样

这样有限制的移动要求似乎很难处理
但是观察一下发现后一类移动要求满足：
有一个格子不能走；要进行的移动的起点和终点都在那个格子旁边
显然可以全部处理出来 存好

突然也感觉挺悲伤的

orz

T2数据随机= =感觉可以不用线段树

接下来的事情就比较简单了...
我们一步一步的往前推
每走完一步(即目标棋和空位进行交换后)的状态由目标棋的位置P以及空位的位置A确定
状态很多? 当然不是 因为空位在目标棋旁边
状态的拓展就只需要枚举下一步走的方向 假设走到了B 那么空位"从A走到B不能经过P"的有限制移动之前已经预处理完了 直接查 得到走了多少步
从起始状态出发不断拓展出其他的状态 注意一个状态可以有多种方法走到 不能简单的一个状态只被拓展出来一次 而可能需要反复更新 因此从这个意义上来说是个最短路模型
我想不到别的做法.. 有更好的做法的神犇请尽情吐槽我的智商..

第二道贪心O(n)
不知能过否..？

稍微得太长了
应该这样
考虑特殊格子保持不动的那些连续的操作，是先把空位移到特殊格子边上，然后每次空位从特殊格子的某侧跑到某个令一侧然后拉一把。然后就差不多了。