Home > Old Blog Posts > USACO 1.4.2 The Clocks

USACO 1.4.2 The Clocks


注意到操作的顺序不影响结果

注意到每种操作4次后恢复原状

由4^9=262144,这道题用dfs就能过

另外还有数学方法:

先预存一张表,a[i][j]表示只把第i个钟转90度而其它钟不变所需第j种方法的次数,这个表由搜索预处理制得,如下:
int a[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} };

最后每种操作得到一个值mod4即为答案,这种方法的速度和代码量都很诱人。

代码:

/*
ID: dementr1
PROG: clocks
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“clocks.in”);
ofstream fout(“clocks.out”);
int a[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} };
int main()
{
int ans[9]={},i,j,t[9];
for(i=0;i<9;i++)
{
fin>>t[i];
for(j=0;j<9;j++) ans[j]=(ans[j]+(4-t[i]/3)*a[i][j])%4;
}
bool flag=false;
for(i=0;i<9;i++)
{
for(j=0;j<ans[i];j++)
{
if(flag) fout<<” “;
else flag=true;
fout<<i+1;
}
}
fout<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: