极力推荐USACOclocksIOI竞赛题详细解答文档格式.docx
《极力推荐USACOclocksIOI竞赛题详细解答文档格式.docx》由会员分享，可在线阅读，更多相关《极力推荐USACOclocksIOI竞赛题详细解答文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
BDEFH
6
CFI
7
DEGH
8
GHI
9
EFHI
Example
99129121291212121212121212
6665->
9998->
9994->
12999->
121212
6366669991299121212
[但这可能不是正确的方法，请看下面]
PROGRAMNAME:
clocks
INPUTFORMAT
第1-3行:
三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。
数字的含意和上面第一个例子一样。
SAMPLEINPUT（fileclocks.in）
9912
666
636
OUTPUTFORMAT
单独的一行包括一个用空格分开的将所有指针指向12:
00的最短移动顺序的列表。
如果有多种方案，输出那种使的连接起来数字最小的方案。
（举例来说5246<
9311）。
SAMPLEOUTPUT（fileclocks.out）
4589
USACO/clocks
目录
[隐藏]
1分析
1.1位运算加速
1.2方法1：
枚举
1.3方法2：
DFS
1.4方法3：
BFS
1.5方法4：
数学方法
1.6方法5：
传说中的“解方程法”
1.7方法6：
直接输出法
2参考代码
[编辑]分析
可以用bfs，dfs，枚举，数学方法解
[编辑]位运算加速
说说位运算加速吧，不仅编程复杂度低，效率也高。
注意到时钟只有四种状态，12点，3点，6点，9点。
令它们为0，1，2，3（这样的定义好处很大）。
这样，它们对应的二进制数为：
000，001，010，011。
即，我们用三个位来记录一个时钟的状态（为什么不用两位？
请思考）。
要tick一个时钟的时候，就给该位加上一，再用按位与的方法去除高位的1。
令最高的三位为时钟A，最低的三位为时钟I，那么：
数“57521883”（==11011011011011011011011011）用于清除每个时钟状态最高位的一（按位与）。
constlongmove[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]ofbyte=（（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]个表示要改变的具体钟表的序号；
......proceduretry（n:
integer;
g,b:
pp）;
vari,j,k:
begin
ifn=10then检验是否为可行解；
fork:
=0to3do
begin
b[n]:
=k;
fori:
=1toa[n,0]doinc（g[a[n,i]],k）;
//改变钟表；
try（n+1,g,b）;
=1toa[n,0]dodec（g[a[n,i]],k）;
//变回原状态；
end;
end;
......begin
读入数据，把3，6，9，12变成1234；
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代码
[编辑]方法4：
数学方法
假设时钟abcdefghi中除了a都到了某一状态，现在有一系列转换可以使a转90度而其它钟不变，进行这一系列的转换，虽然行动次数多了，但钟没有变，已知没有可以直接转a的转换方法，所以其它的钟都是转了360*n度的（0<
=n且n为整数）就是自己独自转了4*n次（0<
=n且n为整数），既然是4的倍数，那么就可以mod4（and3来的更快些）来抵消掉这些操作而钟的位置没变。
这样就得出一个结论了，用枚举或bfs得出的最优解，它的解的前一个步骤为之一个状态.用刚才的理论，对于每个没到12点的钟作只让它转的一次的一系列操作，这样达到了全为12的一种状态，然后将每种操作mod4，用枚举或bfs得出的最优解的前一个步骤时所做的步骤+最优解的最后一个步骤，这样继续向前推，就可以得到从初始状态开始，直接执行对于每个没到12点的钟作只让它转的一次的一系列操作，然后最后结果每种操作mod4，就是枚举或bfs得出的最优解。
[编辑]方法5：
传说中的“解方程法”
和方法4差不多，原理便是对应每一种地图状态，都会有唯一的最优解（因为顺序的问题已经被题目本身排除了），所以对应每一个方法都可以列出九元一次式，然后根据输入数据用伟大的高斯同学的消元法解之然后取最优解即可。
复杂度只是O
（1）。
[编辑]方法6：
直接输出法
先编程求出只旋转其中一个钟的操作序列然后将这个结果作为const存储随后，将每个钟所需要的操作叠加起来，最后分别mod4（cfk:
这不就是方法4吗=_=||……）
[编辑]参考代码
c
#include<
stdio.h>
stdlib.h>
string.h>
assert.h>
ctype.h>
#defineINF60000/*biggerthanlongestpossiblepath*/
char*movestr[]={"
abde"
"
abc"
bcef"
adg"
bdefh"
cfi"
degh"
"
ghi"
efhi"
};
intmovedist[9][9];
intclock[9];
intbestmove[9];
intnbestmove;
/*translatemovestringsintoarray"
movedist"
ofwhichclockschangeoneachmove*/
void
mkmove（void）
{
inti;
char*p;
for（i=0;
i<
9;
i++）
for（p=movestr[i];
*p;
p++）
movedist[i][*p-'
a'
]=3;
}
/*applysomenumberofeachmovefromkto9*/
/*movecontainsthenumberoftimeseachmoveisapplied*/
solve（int*move,intk）
inti,j,n,rep;
if（k==9）{
for（j=0;
j<
j++）
if（clock[j]%12
!
=0）
return;
/*wehaveasuccessfulsequenceofmoves*/
n=0;
n+=move[j];
if（nbestmove==0||n<
nbestmove）{
nbestmove=n;
bestmove[j]=move[j];
}
return;
/*
*theforloopcountsdownsowe
*generatesmallernumbersfirstby
*tryingmoreofsmallnumbered
*movesbeforewetrylessofthem.
*/
for（rep=3;
rep>
=0;
rep--）{
/*applymovekreptimes*/
rep;
clock[j]+=movedist[k][j];
move[k]=rep;
solve（move,k+1）;
/*undomove*/
clock[j]-=movedist[k][j];
main（void）
FILE*fin,*fout;
inti,j,move[9];
char*sep;
fin=fopen（"
clocks.in"
r"
）;
fout=fopen（"
clocks.out"
w"
assert（fin
=NULL&
&
fout
=NULL）;
mkmove（）;
fscanf（fin,"
%d"
&
clock[i]）;
solve（move,0）;
sep="
"
;
i++）{
bestmove[i];
j++）{
fprintf（fout,"
%s%d"
sep,i+1）;
\n"
exit（0）;
inta[9][9]={{3,3,3,3,3,2,3,2,0},
{2,3,2,3,2,3,1,0,1},
{3,3,3,2,3,3,0,2,3},
{2,3,1,3,2,0,2,3,1},
{2,3,2,3,1,3,2,3,2},
{1,3,2,0,2,3,1,3,2},
{3,2,0,3,3,2,3,3,3},
{1,0,1,3,2,3,2,3,2},
{0,2,3,2,3,3,3,3,3}};
intv[9];
intmain（）{
inti,j,k;
freopen（"
"
stdin）;
for（i=0;
scanf（"
&
k）;
v[j]=（v[j]+（4-k/3）*a[i][j]）%4;
fclose（stdin）;
k=0;
stdout）;
for（j=0;
v[i];
if（!
k）{printf（"
i+1）;
k=1;
elseprintf（"
%d"
printf（"
fclose（stdout）;
return0;
pascal
C++
来自"
升级会员 