[编辑] 分析

可以用bfs，dfs，枚举，数学方法解

[编辑] 位运算加速

说说位运算加速吧，不仅编程复杂度低，效率也高。注意到时钟只有四种状态，12点，3点，6点，9点。令它们为0，1，2，3（这样的定义好处很大）。

这样，它们对应的二进制数为：000，001，010，011。即，我们用三个位来记录一个时钟的状态（为什么不用两位？请思考）。

要tick一个时钟的时候，就给该位加上一，再用按位与的方法去除高位的1。

令最高的三位为时钟A，最低的三位为时钟I，那么：

数“57521883”用于清除每个时钟状态最高位的一（按位与）。

const long move[9] = {18911232, 19136512, 2363904, 16810048, 2134536, 262657, 36936, 73, 4617}

move[i]表示题述中的第i+1种方法

令f[q]为原状态，比如用题述中的第k种方法，那么可以写成 f[q + 1] = (f[q] + move[k - 1]) & 57521883;

当9个时钟都回归12点的时候，巧的是状态f=0。这样，判断每个状态f是否为0，就知道是否求出可行解。

[编辑] 方法1：枚举

因为每种变换方法可以使用0~3次，并且每种变换方法在前与在后是等效的。所以，利用递归，按题中顺序枚举所有可能的解，并且每次记录下途径，那么第一种解就是我们要求的答案，输出即可。并且此方法简单易懂，复杂度很低。在usaco上测试最大的才用了0.097秒。主要程序步骤：

const

 a:array[1..9,0..9] of byte=((4,1,2,4,5,0,0,0,0,0),
                             (3,1,2,3,0,0,0,0,0,0),
                             (4,2,3,5,6,0,0,0,0,0),
                             (3,1,4,7,0,0,0,0,0,0),
                             (5,2,4,5,6,8,0,0,0,0),
                             (3,3,6,9,0,0,0,0,0,0),
                             (4,4,5,7,8,0,0,0,0,0),
                             (3,7,8,9,0,0,0,0,0,0),
                             (4,5,6,8,9,0,0,0,0,0));

记录每种方法改变钟表的情况，a[i,0]表示需要改变的钟表的个数，其后a[i,0]个表示要改变的具体钟表的序号；

... ...

procedure try(n:integer;g,b:pp); var i,j,k:integer; begin

 if n=10 then 检验是否为可行解；
 for k:=0 to 3 do
   begin
     b[n]:=k;
     for i:=1 to a[n,0] do inc(g[a[n,i]],k);//改变钟表；
     try(n+1,g,b);
     for i:=1 to a[n,0] do dec(g[a[n,i]],k);//变回原状态；
   end;

end;

... ... //感觉是不是少了点什么啊？

begin

 读入数据，把3，6，9，12变成1 2 3 4；
 try;

end.

[编辑] 方法2：DFS

显而易见地，方案的顺序并不重要。而每种方案最多只能选择3次，如果4次相当于没有选择。这样，总的搜索量只有(4^9=262144)，用DFS搜索所有状态，选择其中一个最小的输出即可。

可以采用位运算加速

[编辑] 方法3：BFS

用BFS完全可以完美解决本题，虽然有些划不来（毕竟枚举都可以过），但思想是可以值得借鉴的。 1.判重，把3,6,9,12分别对应于1,2,3,0，这样一个状态就对应一个9位4进制数，hash数组就开到4^9左右 2.剪枝(谁说BFS不能剪枝)，其实同DFS的剪枝，按非递减顺序扩展，每个操作最多做3次 3.空间,如果开longint可能会MLE，于是改成byte，成功！如此一来，BFS可以应对所有数据，最大的也只要花了0.119s 详细见pascal代码

因为已知初末状态，还可以考虑用双向广搜优化，最大时间0.054s。

[编辑] 方法4：数学方法

假设时钟abcdefghi中除了a都到了某一状态，现在有一系列转换可以使a转90度而其它钟不变，进行这一系列的转换，虽然行动次数多了，但钟没有变，已知没有可以直接转a的转换方法，所以其它的钟都是转了360*n度的(0<=n且n为整数)就是自己独自转了4*n次(0<=n且n为整数)，既然是4的倍数，那么就可以mod 4(and 3来的更快些)来抵消掉这些操作而钟的位置没变。这样就得出一个结论了，用枚举或bfs得出的最优解，它的解的前一个步骤为之一个状态.用刚才的理论，对于每个没到12点的钟作只让它转的一次的一系列操作，这样达到了全为12的一种状态，然后将每种操作mod 4，用枚举或bfs得出的最优解的前一个步骤时所做的步骤+最优解的最后一个步骤，这样继续向前推，就可以得到从初始状态开始，直接执行对于每个没到12点的钟作只让它转的一次的一系列操作，然后最后结果每种操作mod 4，就是枚举或bfs得出的最优解。

[编辑] 方法5：传说中的“解方程法”

和方法4差不多，原理便是对应每一种地图状态，都会有唯一的最优解（因为顺序的问题已经被题目本身排除了），所以对应每一个方法都可以列出九元一次式，然后根据输入数据用高斯的消元法解之然后取最优解即可。复杂度只是O(1)。九元一次式中移动方法1需要执行12+b[1]-2*b[2]+b[3]-2*b[4]-2*b[5]+3*b[6]+b[7]+3*b[8]-4*b[9]次，请自行推出移动方法2-9

12:42 2010年8月17日 (CST)再议吧，貌似列出方程之后等号后面是a[i]+4*n而不是a[i];--Comzyh 12:42 2010年8月17日 (CST)