编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

就9重for循环的改进版!!!!!!!!!!!!

编译通过...

├ 测试数据 01：答案正确... 72ms

├ 测试数据 02：答案正确... 72ms

├ 测试数据 03：答案正确... 56ms

├ 测试数据 04：答案正确... 56ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 56ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：592ms

汗~~~~~~~~~~~~~~~就9重for循环。。。。。。。

关键是每种操作只能做取0-3次,多做只会重复,剩下的就是硬搜了

这个题,不懂的可以参见MAIGO的USACO题解2_3,写得比较清楚,还能得到一些启示.(晕,刚才把maigo的程序看懂,原来并不是每个maigo的程序都那么好懂的...)

Accepted 有效得分：100 有效耗时：2529ms

编译通过...

├ 测试数据 01：答案正确... 228ms

├ 测试数据 02：答案正确... 166ms

├ 测试数据 03：答案正确... 150ms

├ 测试数据 04：答案正确... 197ms

├ 测试数据 05：答案正确... 572ms

├ 测试数据 06：答案正确... 806ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 275ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2513ms

为什么我的bfs这么慢呢？哇哇~~~~~哭~~

穷举，哎要初始化的东西太多，要特别小心

From Vivian Snow

北京2008的挂钟 国际信息学奥林匹克竞赛 (IOI) 竞赛原题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

枚举OK

主体思路是搜索

每个clock组可以用一个18位二进制数代替。用一个int即可表示状态变量

而由于操作满足交换律和结合律，所以只需记录每种操作进行了几次（而且次数保证

哎 还是大牛编的复杂度低啊。。。

我用宽搜的

编译通过...

├ 测试数据 01：答案正确... 72ms

├ 测试数据 02：答案正确... 41ms

├ 测试数据 03：答案正确... 25ms

├ 测试数据 04：答案正确... 56ms

├ 测试数据 05：答案正确... 244ms

├ 测试数据 06：答案正确... 338ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：873ms

比较慢

不知道 双向搜索 会不会快点

枚举哈哈，USACO上的题目

有种优化可以加快速度的...

就是压缩状态存储：用两个二进制位表示一个钟的状态

对钟进行操作和判断就转变成了一个简单的位操作

不过似乎这个数据...没有必要

此题用枚举法编程最为方便.具体过程可见黑书的枚举法一节或奥赛兵法等书

很明显，此题为广度优先搜索题，且需要记录搜索转移状态。因为总状态数为4^9=262144，所以我们可以采用哈希表映射进行搜索判重。这样当最坏的情况下仍然需要2s种才能出结果。所以我们仔细分析题目，发现进行操作的顺序可以调换，所以可以采用广度升序优先搜索算法进行剪枝。同时，如果一个操作做了4次，那么指针指向原来的方向，也就是说不如不做这4个操作，亦可以进行剪枝。这样，在最坏情况下，程序也只要0.4s出解。

简单搜索，深搜宽搜均可

宽搜：

搜索时只要按照方案从小到大的顺序扩展节点就行。

一直扩展直到找到一组解，该方案一定是最优的，输出。

深搜：

好像不太好，要把所有情况都找一遍。

但是放心，不会超时（0.3s）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

struct item{
int t[10];
bool empty(){
for(int i=1;i<=9;i++)
if(t[i])return false;
return true;
}
};

struct Queue{
int t[40],top;
Queue(){
memset(t,0,sizeof(t));top=0;
}
void push(int x){t[++top]=x;}
void output(){
for(int i=1;i<=top;i++)
printf("%d ",t[i]);
}
};

bool operator<(Queue A,Queue B){
if(A.top!=B.top)return A.top<B.top;
int i;for(i=1;i<=min(A.top,B.top);i++){
if(A.t[i]!=B.t[i])
return A.t[i]<B.t[i];
}
return A.t[i]<B.t[i];
}

item operator+(item A,item B){
for(int i=1;i<=9;i++)
A.t[i]=(A.t[i]+B.t[i])%4;
return A;
}
item operator*(item A,int time){
for(int i=1;i<=9;i++)
A.t[i]=(A.t[i]*time)%4;
return A;
}

Queue ans;
item ope[12];
int cnt[10];bool suc=0;
void DFS(int step){
if(step>9){
item now=ope[0];
for(int i=1;i<=9;i++)
now=now+(ope[i]*cnt[i]);
if(now.empty()){
if(ans.top==0)
for(int i=1;i<=9;i++){
for(int j=1;j<=cnt[i];j++)
ans.push(i);
}
else{
Queue n;n=Queue();
for(int i=1;i<=9;i++){
for(int j=1;j<=cnt[i];j++)
n.push(i);
}
if(n<ans)ans=n;
}
}
return;
}
for(int i=0;i<4;i++){
cnt[step]=i;
DFS(step+1);
}
}
int main(){
for(int i=1;i<=9;i++)
scanf("%d",&ope[0].t[i]);
ope[1]=(item){0,1,1,0,1,1,0,0,0,0};//ABDE
ope[2]=(item){0,1,1,1,0,0,0,0,0,0};//ABC

ope[3]=(item){0,0,1,1,0,1,1,0,0,0};//BCEF
ope[4]=(item){0,1,0,0,1,0,0,1,0,0};//ADG

ope[5]=(item){0,0,1,0,1,1,1,0,1,0};//BDEFH
ope[6]=(item){0,0,0,1,0,0,1,0,0,1};//CFI

ope[7]=(item){0,0,0,0,1,1,0,1,1,0};//DEGH
ope[8]=(item){0,0,0,0,0,0,0,1,1,1};//GHI

ope[9]=(item){0,0,0,0,0,1,1,0,1,1};//EFHI
DFS(1);
ans.output();
return 0;
}

import java.util.Scanner;

public class Main {

int[][] target = {{0},{1,2,4,5,0},{1,2,3,0},{2,3,5,6,0},{1,4,7,0},{2,4,5,6,8,0},{3,6,9,0},{4,5,7,8,0},{7,8,9,0},{5,6,8,9,0}};
int[] output = new int[10];
int[] record = new int[10];
boolean flag = false;
public void dfs(int deep) {
if(deep == 10) {
flag = check();
return ;
}

for(int i =0; i<=3; i++) {
change(deep,i);
record[deep] = i ;
dfs(deep+1);
if(!flag) {
change(deep ,-i);
}
else {
return;
}
}
}
public boolean check() {
for(int i =1; i<=9; i++) {
if(output[i]!=0) {
return false;
}
}
return true;
}
public void change(int deep, int i ) {
if(i !=0) {
int j=0;
while(target[deep][j]!=0)
{
output[target[deep][j]] +=4;//不够减
output[target[deep][j]] += i;
output[target[deep][j]] %= 4;
j++;
}

}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int i=1;
Main problem = new Main();
while(i<=9) {
problem.output[i] = sc.nextInt();
problem.record[i] = 0;
i++;
}
problem.dfs(1);

for(i=1; i<=9; i++) {
while(problem.record[i]>0) {
System.out.print(i+" ");
problem.record[i]--;
}
}
}

}

我感觉我的深搜可以的哦 思路很清晰。时间200ms吧，比较慢，毕竟java

一直MLE查不出问题，到最后发现自己居然把bool数组给忘了，服了……
多亏vijos的数据比较弱，这题要是放到HDU或者POJ上暴力BFS估计是做出不来的，肯定要用状压或者打表之类的技巧，不过我太菜鸡写不出来……

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;

bool flag[4][4][4][4][4][4][4][4][4];
struct cl
{
    int s[9];
    int ans[30];
    int step;
    int num;
    cl():step(0),num(0)
    {

    }
};
char op[9][6]={"0134","012","1245","036","13457",
               "258","3467","678","4578"};
queue<cl> q;

int BFS()
{
    cl tmp;
    while(q.empty()==false)
    {
        tmp=q.front();
        q.pop();
        for(int i=0;i<9;i++)
        {
            cl ast;
            for(int j=0;j<9;j++)
                ast.s[j]=tmp.s[j];
            for(int j=0;op[i][j]!='\0';j++)
            {
                if(tmp.s[op[i][j]-'0']==3)
                    ast.s[op[i][j]-'0']=0;
                else
                    ast.s[op[i][j]-'0']=tmp.s[op[i][j]-'0']+1;
            }
            if(flag[ast.s[0]][ast.s[1]][ast.s[2]][ast.s[3]][ast.s[4]][ast.s[5]][ast.s[6]][ast.s[7]][ast.s[8]]==false)
            {
                flag[ast.s[0]][ast.s[1]][ast.s[2]][ast.s[3]][ast.s[4]][ast.s[5]][ast.s[6]][ast.s[7]][ast.s[8]]=true;
                ast.step=tmp.step+1;
                for(int j=0;j<tmp.step;j++)
                    ast.ans[j]=tmp.ans[j];
                ast.ans[tmp.step]=i;
                for(int j=0;j<9;j++)
                    ast.num+=ast.s[j];
                if(ast.num==0)
                {
                    for(int j=0;j<ast.step;j++)
                        cout<<ast.ans[j]+1<<' ';
                    cout<<endl;
                    return 1;
                }
                q.push(ast);
            }
        }
    }
    return -1;
}

int main()
{
    cl ori;
    for(int i=0;i<9;i++)
        cin>>ori.s[i];
    memset(flag,false,sizeof(flag));
    flag[ori.s[0]][ori.s[1]][ori.s[2]][ori.s[3]][ori.s[4]][ori.s[5]][ori.s[6]][ori.s[7]][ori.s[8]]=true;
    q.push(ori);
    BFS();
    return 0;
}

Accepted

状态 耗时 内存占用

#1 Accepted 151ms 368.0 KiB
#2 Accepted 123ms 364.0 KiB
#3 Accepted 137ms 360.0 KiB
#4 Accepted 147ms 348.0 KiB
#5 Accepted 146ms 356.0 KiB
#6 Accepted 151ms 384.0 KiB
#7 Accepted 127ms 368.0 KiB
#8 Accepted 145ms 360.0 KiB
#9 Accepted 78ms 376.0 KiB
#10 Accepted 109ms 364.0 KiB
代码

想看么？不可能的

emmmmmm

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
class point
{
public:
point() :hash(0) {};
point(int *k);//构造函数
point inc(int *k);// 变形用
int hashf(); // 哈希函数
int hash; // 哈希值
point( const point& k); //复制构造函数
point& operator = ( const point& k);//等于号赋值
bool suc();//搜索结束
void out()
{
for( int i=0;i<9;i++) cout<<a[i]<<" "; cout<<endl;
}
private:
int a[9];
} ;
point::point(int *k)
{
if(!k) return;
for(int i=0; i<9; i++) a[i]=k[i];
hash=this->hashf();
}
point point::inc(int *k)
{
point ans;
for(int i=0; i<9; i++) ans.a[i]=(a[i]+k[i])%4;
ans.hash=ans.hashf();
return ans;
}
int point::hashf()
{
int ans=a[0];
for(int i=1; i<9; i++) ans=ans*4+a[i];
return ans;
}
point::point(const point& k)
{
for(int i=0;i<9;i++) a[i]=k.a[i];
hash=k.hash;
}
point& point::operator =(const point& k)
{
for(int i=0;i<9;i++) a[i]=k.a[i];
hash=k.hash;
return *this;
}
bool point::suc()
{
for(int i=0;i<9;i++) if(a[i]) return false;
return true;
}
queue<point> q;
int list[9][9]={
{1,1,0,1,1,0,0,0,0},
{1,1,1,0,0,0,0,0,0},
{0,1,1,0,1,1,0,0,0},
{1,0,0,1,0,0,1,0,0},

{0,1,0,1,1,1,0,1,0},
{0,0,1,0,0,1,0,0,1},
{0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,1,1,0,1,1}
};
bool flag[2621440];
int link[2000000],kind[2000000];
void print(int k);
int main()
{
int a[9],cont=0,tail=1;

for(int i=0;i<9;i++) cin>>a[i];
point k( (int *) &a );
q.push( k );
//int *x=list[1];
//for(int i=0;i<9;i++) cout<<x[i]<<" "; cout<<endl;
while(!q.empty())
{

cont++;
point s=q.front() ; q.pop() ;
//s.out();
if(s.suc()) { print(cont); break;}
for(int i=0;i<9;i++)
{
point tmp=s.inc( list[i]);
if( flag[tmp.hash] ) continue;
else { tail++;
q.push(tmp);
link[tail]=cont;
kind[tail]=i;
flag[tmp.hash]=true;

}
}
}
return 0;
}
void print(int k)
{
if( k!=1 ) print(link[k]);
else return;
cout<<kind[k]+1<<" ";
return;
}