USACO/shuttle

来自NOCOW

< USACO

跳转到：导航, 搜索

[编辑] 问题分析

[编辑] 构造法

根据答案寻找规律（可以证明正确性）:

3

3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

2 1 -2 -2 -1 2 2 2 -1 -2 -2 1 2 -1

4

4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

5

5 7 8 6 4 3 5 7 9 10 8 6 4 2 1 3 5 7 9 11 10 8 6 4 2 3 5 7 9 8 6 4 5 7 6

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

6

6 8 9 7 5 4 6 8 10 11 9 7 5 3 2 4 6 8 10 12 13 11 9 7 5 3 1 2 4 6 8 10 12 11 9 7 5 3 4 6 8 10 9 7 5 6 8 7

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 1 -2 -2 -2 -2 -2 -2 1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

[编辑] 数据分析

Usaco在这题上并没有指明不可以用分析法，而且dfs肯定TLE，所以我们取巧。

先观察样例数据，如果把还没移动的那一步也算上，那么空格的位置为

4 3 5 6 4 2 1 3 5 7 6 4 2 3 5 4 (n=3,样例)

5 4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5 (n=4)

我们凭借极其敏锐的眼光发现这组序列为

４35 642 1357 642 35 4 (n=3,样例)

5 46 753 2468 97531 2468 753 46 5 (n=4)

即长度为1,2,3,4,...,n,n+1,n,...,4,3,2,1这样的2n+1组等差序列

我们讨论第1~n+1组序列，这些序列满足

　　*公差的绝对值为2

　　*奇数组为降序列，偶数组为升序列

　　*对于第i组(1<=i<=n+1),若为奇数组则首项为n+i，偶数组则首项为n-i+2

对于第n+2~2n+1组，可以由对称性求出。

输出时从第二组开始即可。

把规律总结成这样后，代码应该很好写了吧

这个太叉叉了，敢问楼上大牛，你是怎么发现这样的规律的

蒟蒻表示这太拽了

[编辑] 其实这道题用搜索也能过，详见代码（最后一个）

写了个暴力双向广搜。头都大了。太鄙视我自己了。。。

路人丁表示未发现本题双向广搜代码= = 只发现广搜能过。。

如果双向宽搜不加优化，可以过到层数为80这样，很明显，不能全过。一个宽搜只加一个W只往后移，B只往前移的优化，就可以全过了，0.1s以内。效率也还可以，最可贵的是：写法简单。

[编辑] 搜索也可以

其实搜索也很快的。。我的就是全0.000 用0、1、2表示状态例如输入为3的时候初始状态就是： 1110222 1、可以证明，移动步数最少时，1一定往右移，2一定往左移 2、进一步观察发现，若空格附近状态为 101时，则1不能往左移，否则下一步会出现1中所述的情况，除非在现有空位右边已经全部为1，同理 202情况相同加入上述两个条件之后就能0.000 ac掉了

[编辑] DFS也能过

设 p 为空格的位置，搜的时候 p-2, p-1, p+1, p+2 枚举这4个。

减枝：设初始时左B右W，以空格左侧为例，从 p-1 向 0 遍历，若发现 WW 组合，且向再左还有 B，则可以回退了；右侧同理。因为规则里说“You may not back up”，也就是不能回退，若有WW组合，则会把左边的B塞死。

可以全部 0.000s 过。

[编辑] IDA*奇怪地过了

没有加奇怪的剪枝（其实是自己没想到qwq），只是乱改了下h函数就过了（改过的h函数好像不太对……总之过了）

[编辑] 递推

观察到可根据空格左右2格内状态判断下一次该移动哪个（因有最小解限制，故移法唯一）跑起来很快，不过写起来没有前面几位大神的方便。