# 207 条题解

• @ 2017-10-25 19:12:50

不明白为什么大家都在广搜..其实这题可以DFS啊..

因为同一种操作做四次等于没做，所以每种操作最多做三次。

分别枚举9种操作的操作次数就好了啊..

``````#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[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;
}
``````
• @ 2018-05-20 20:23:54

太强了

• @ 2020-11-26 11:14:21
``````#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
const int o[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}
};
int clk[9],act,ans[9];
int chk(int *sta)
{
int flag=1;
for (int i=0;i<9&&flag;i++)
flag&=(sta[i]==0);
return flag;
}
void dfs(int pos,int *sta,int *cnt,int oct)
{
if (chk(sta)&&oct<act)
{
act=oct,memcpy(ans,cnt,sizeof(ans));
return;
}
for (int i=3;i>=0&&pos<9&&oct<act;i--)
{
cnt[pos]=i;
for (int j=0;j<9;j++)
sta[j]=(sta[j]+o[pos][j]*i)%4;
dfs(pos+1,sta,cnt,oct+i);
for (int j=0;j<9;j++)
sta[j]=((sta[j]-o[pos][j]*cnt[pos])%4+4)%4;
cnt[pos]=0;
}
}

void main()
{
for (int i=0;i<9;i++)
scanf("%d",&clk[i]);
act=oo_max;
int bg[9];
memset(bg,0,sizeof(bg));
dfs(0,clk,bg,0);
for (int i=0;i<9;i++)
for (int j=1;j<=ans[i];j++)
printf("%d ",i+1);
}
}

int main()
{
dts::main();
}
``````
• @ 2018-05-15 16:15:58

练DFS上手题，详见代码。

``````#include<bits/stdc++.h>
using namespace std ;
//Vijos P1016

const int way[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}} ;//9种方式改变不同的钟，1代表加3点，0代表不变
bool judge ;//判断是否调整完成
int x[9] , ans[9] ;
void dfs(int num)
{
if (num == 9)//9种方式全部搜完
{
for (int i = 0 ; i < 9 ; i ++)
{
if (x[i] % 4 != 0)//有不是12点的钟
return ;
}
judge = true ;//全部调整完成
return ;
}
for (int i = 0 ; i <= 3 ; i ++)
{
ans[num] = i ;//第（i+1）钟方式的数量
for (int j = 0 ; j < 9 ; j ++)
{
x[j] += way[num][j] * i ;//改变
}
dfs(num + 1) ;//深搜
if (judge)//此时已经调整完成，而调整方式有且只有一种，因此可以输出答案
return ;
for (int j = 0 ; j < 9 ; j ++)
{
x[j] -= way[num][j] * i ;//回溯
}
}
}
int main()
{
for (int i = 0 ; i < 9 ; i ++)
{
cin >> x[i] ;
}
dfs(0) ;
for (int i = 0 ; i < 9 ; i ++)
{
for (int j = 0 ; j < ans[i] ; j ++)
{
cout << i + 1 << ' ' ;
}
}
cout << endl ;
}
``````
• @ 2017-05-07 12:50:19

直接暴力bfs搜索就好了
其实还有枚举的办法
很经典的题目
记得那本《算法竞赛宝典》上有仔细讲
因为不太难
直接上bfs的代码啦~

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int Rank[1000000];
int c[1000000];
bool s[4][4][4][4][4][4][4][4][4];
int da[9][9] = {
{0, 1, 3, 4, -1 },
{0, 1, 2, -1 },
{1, 2, 4, 5, -1 },
{0, 3, 6, -1 },
{1,3,4,5,7,-1},
{2,5,8,-1},
{3,4,6,7,-1},
{6,7,8,-1},
{4,5,7,8,-1}
};

void Out(int x)
{
if(x>1)
{
Out(Rank[x]);
cout<<c[x]<<" ";
}
}

{
memcpy(&l,&p,sizeof(p));
for(int i=0;da[x][i]!=-1;i++)
{
l[da[x][i]]++;
l[da[x][i]]%=4;
}
}

{
if(s[po[0]][po[1]][po[2]][po[3]][po[4]][po[5]]
[po[6]][po[7]][po[8]]==0)
return 1;
else
return 0;
}

{
s[po[0]][po[1]][po[2]][po[3]][po[4]][po[5]]
[po[6]][po[7]][po[8]]=1;
}

void bfs()
{
tail++;
check1(start);
{
for(int i=0;i<=8;i++)
{
change(p,i);
if(check(l))
{
memcpy(&q[tail],&l,sizeof(l));
c[tail]=i+1;
check1(l);
if(memcmp(goal,l,sizeof(l))==0)
{
Out(tail);
return;
}
tail++;
}
}
}
}

int main()
{
for(int i=0;i<=8;i++)
{
int x;
cin>>x;
start[i]=(x/3)%4;
}
bfs();
return 0;
}
``````
• @ 2016-10-28 21:24:03
``````#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
using namespace std;
const int L=1<<18;        //18位二进制串压状态
queue<int>Q;
int c[9];
bool vis[L];
struct last{
int lst;
int opt;
};
last b[L];
int getst()
{
int ret=0;
for (int s=0;s<9;s++) ret|=c[s]<<(s<<1);
return ret;
}
int rot(int k,int wis)
{
k=(~(0x3<<(wis<<1))&k)|((((k&(0x3<<(wis<<1)))>>(wis<<1))+1)%4)<<(wis<<1);
return k;              //位运算拨钟
}
int r[9][5]={
{0,1,3,4,-1},
{0,1,2,-1,-1},
{1,2,4,5,-1},
{0,3,6,-1,-1},
{1,3,4,5,7},
{2,5,8,-1,-1},
{3,4,6,7,-1},
{6,7,8,-1,-1},
{4,5,7,8,-1}
};
void bfs(int x)
{
Q.push(x);
vis[x]=1;
b[x].lst=-1;
b[x].opt=-1;
while (!Q.empty())
{
int k=Q.front();
Q.pop();
if (!k) return;
for (int s=0;s<9;s++)
{
int kk=k;
for (int t=0;t<5;t++)
if (r[s][t]!=-1)
kk=rot(kk,r[s][t]);
if (!vis[kk])
{
vis[kk]=1;
Q.push(kk);
b[kk].lst=k;
b[kk].opt=s+1;
}
}
}
}
int path[L],count=0;
void back(int x)
{
path[count++]=b[x].opt;
if (b[x].lst!=-1) back(b[x].lst);
}
int main()
{
memset(vis,0,sizeof(vis));
memset(b,0,sizeof(b));
for (int s=0;s<9;s++) scanf("%d",&c[s]);
int q=getst();
bfs(q);
back(0);
for (int s=count-2;s>=0;s--) printf("%d ",path[s]);
}
``````
• @ 2016-08-16 20:25:14
``````#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
bool flag[4][4][4][4][4][4][4][4][4];
int op[10][10] = {{0},{1,2,4,5},{1,2,3},{2,3,5,6},{1,4,7},{2,4,5,6,8},
{3,6,9},{4,5,7,8},{7,8,9},{5,6,8,9}};

int st[10];
struct node
{
int state[10],step,ans[200];
friend bool operator < (struct node a,struct node b)
{
return a.step > b.step;
}
}s,now;

void bfs()
{
priority_queue<node> Q;
memset(flag,0,sizeof(flag));
memcpy(s.state,st,sizeof(st));
s.step = 0;
flag[st[1]][st[2]][st[3]][st[4]][st[5]][st[6]][st[7]][st[8]][st[9]] = 1;
Q.push(s);
while(!Q.empty())
{
now = Q.top();
Q.pop();
for(int i = 1;i <= 9;i ++)
{
s = now;
for(int j = 0;op[i][j];j ++)
{
s.state[op[i][j]] ++;
if(s.state[op[i][j]] >= 4)
s.state[op[i][j]] -= 4;
}
if(!flag[s.state[1]][s.state[2]][s.state[3]][s.state[4]][s.state[5]][s.state[6]][s.state[7]][s.state[8]][s.state[9]])
{
s.ans[++s.step] = i;
flag[s.state[1]][s.state[2]][s.state[3]][s.state[4]][s.state[5]][s.state[6]][s.state[7]][s.state[8]][s.state[9]] = 1;
Q.push(s);
}
if(!s.state[1] && !s.state[2] && !s.state[3] && !s.state[4] && !s.state[5]
&& !s.state[6] && !s.state[7] && !s.state[8] && !s.state[9])
{
sort(s.ans+1,s.ans + s.step+1);
for(int j = 1;j <= s.step;j ++)
printf("%d ",s.ans[j]);
exit(0);
}
}
}
}

int main()
{
for (int i=1;i<=9;i++) scanf("%d",&st[i]);
bfs();
return 0;
}
``````

楼下真6

• @ 2016-07-11 15:15:16

测试数据 #0: Accepted, time = 62 ms, mem = 15152 KiB, score = 10

测试数据 #1: Accepted, time = 31 ms, mem = 15148 KiB, score = 10

测试数据 #2: Accepted, time = 46 ms, mem = 15152 KiB, score = 10

测试数据 #3: Accepted, time = 46 ms, mem = 15148 KiB, score = 10

测试数据 #4: Accepted, time = 93 ms, mem = 15148 KiB, score = 10

测试数据 #5: Accepted, time = 125 ms, mem = 15148 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 15148 KiB, score = 10

测试数据 #7: Accepted, time = 62 ms, mem = 15148 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 15148 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 15152 KiB, score = 10

Accepted, time = 511 ms, mem = 15152 KiB, score = 100
呵呵，猥琐的时间

• @ 2016-07-17 13:57:14

你。。。

• @ 2016-07-17 14:02:55

i

• @ 2016-07-17 14:03:31

i1

• @ 2016-07-11 15:14:22

const dd:array[1..9,1..9] of integer=
((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));
var i,j,l,h:longint;
a:array[0..300001,0..10] of longint;
o:array[0..300001] of longint;
flag:array[0..3,0..3,0..3,0..3,0..3,0..3,0..3,0..3,0..3] of boolean;
procedure tof;
var t:longint;
begin
for j:=1 to 9 do
if a[h,j]<>0 then exit;
t:=h;
for j:=o[0] downto 1 do write(o[j],' ');
halt;
end;
begin
l:=1;
h:=1;
while l<=h do
begin
for i:=1 to 9 do
begin
a[0]:=a[l];
for j:=1 to 9 do
a[0,j]:=(a[0,j])mod 3;
if not flag[a[0,1],a[0,2],a[0,3],a[0,4],a[0,5],a[0,6],a[0,7],a[0,8]] then
begin
inc(h);
a[h]:=a[0];
flag[a[0,1],a[0,2],a[0,3],a[0,4],a[0,5],a[0,6],a[0,7],a[0,8],a[0,9]]:=true;
a[h,0]:=l;
a[h,10]:=i;
tof;
end;
end; inc(l);
end;

end.
深搜要栈溢出！
记住用“堆空间”——宽搜！
注意扩展数量!

• @ 2016-07-17 14:09:46

错了，说代码是要高亮语法，例：（1014我的代码）
program s;
var a:array[1..1000] of record x,y:int64; end;
var b,c:longint;
procedure d(e,f:longint);
var g,h,i,j:longint;
begin
g:=e;
h:=f;
i:=a[(g+h) div 2].x;
repeat
while a[g].x<i do
g:=g+1;
while a[h].x>i do
h:=h-1;
if g<=h then begin
j:=a[g].x;
a[g].x:=a[h].x;
a[h].x:=j;
j:=a[g].y;
a[g].y:=a[h].y;
a[h].y:=j;
g:=g+1;
h:=h-1;
end;
until g>h;
if g<f then d(g,f);
if e<h then d(e,h);
end;
var k,l:array[0..1000,0..1000] of extended;
var m,n:extended;
var o,p:longint;
var q,r:int64;
begin
for c:=1 to b do
if b>0 then d(1,b);
for c:=1 to b-1 do
for o:=c+1 to b do
begin
if a[c].x>a[o].x then q:=a[c].x-a[o].x
else q:=a[o].x-a[c].x;
if a[c].y>a[o].y then r:=a[c].y-a[o].y
else r:=a[o].y-a[c].y;
l[c,o]:=sqrt(q*q+r*r);
end;
for c:=1 to b do
for o:=1 to b do
k[c,o]:=1e24;
if b>=2 then k[2,1]:=l[1,2]
else begin
writeln('0.00');
exit;
end;
for c:=3 to b do
for o:=1 to c-1 do
if o<c-1 then k[c,o]:=k[c-1,o]+l[c-1,c]
else for p:=1 to o-1 do
begin
n:=k[o,p]+l[p,c];
if n<k[c,o] then k[c,o]:=n;
end;
writeln(k[b,b-1]+l[b-1,b]:0:2);
end.

• @ 2016-07-17 14:10:26

不对，是这样：
```Pascal program s; var a:array[1..1000] of record x,y:int64; end; var b,c:longint; procedure d(e,f:longint); var g,h,i,j:longint; begin g:=e; h:=f; i:=a[(g+h) div 2].x; repeat while a[g].x<i do g:=g+1; while a[h].x>i do h:=h-1; if g<=h then begin j:=a[g].x; a[g].x:=a[h].x; a[h].x:=j; j:=a[g].y; a[g].y:=a[h].y; a[h].y:=j; g:=g+1; h:=h-1; end; until g>h; if g<f then d(g,f); if e<h then d(e,h); end; var k,l:array[0..1000,0..1000] of extended; var m,n:extended; var o,p:longint; var q,r:int64; begin readln(b); for c:=1 to b do readln(a[c].x,a[c].y); if b>0 then d(1,b); for c:=1 to b-1 do for o:=c+1 to b do begin if a[c].x>a[o].x then q:=a[c].x-a[o].x else q:=a[o].x-a[c].x; if a[c].y>a[o].y then r:=a[c].y-a[o].y else r:=a[o].y-a[c].y; l[c,o]:=sqrt(q*q+r*r); end; for c:=1 to b do for o:=1 to b do k[c,o]:=1e24; if b>=2 then k[2,1]:=l[1,2] else begin writeln('0.00'); exit; end; for c:=3 to b do for o:=1 to c-1 do if o<c-1 then k[c,o]:=k[c-1,o]+l[c-1,c] else for p:=1 to o-1 do begin n:=k[o,p]+l[p,c]; if n<k[c,o] then k[c,o]:=n; end; writeln(k[b,b-1]+l[b-1,b]:0:2); end. ```

• @ 2016-07-17 14:12:45

代码错了，编译不通过，漏了a[0,9]，应该是not flag[a[0,1],a[0,2],a[0,3],a[0,4],a[0,5],a[0,6],a[0,7],a[0,8],a[0,9]]

• @ 2016-05-18 13:22:09

位运算+暴力搜索
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
const int N = 9,M = 3,Z = 28;
int TG[M][M],G[M][M],m = Z;
int P[N] = {432,448,216,292,186,73,54,7,27};
unsigned long long int A = 0,B;
int MP[N];
{
for(int i = 0;i < M;i++)
for(int j = 0;j < M;j++)
{
scanf("%d",&TG[i][j]);
G[i][j] = TG[i][j];
}
}
bool is_ok()
{
for(int i = 0;i < M;i++)
for(int j = 0;j < M;j++)
if(G[i][j] % (M + 1)) return false;
return true;
}
int times(unsigned long long int X,int i)
{
return (((X >> ((N << 1) - (i << 1)) - 1) & 1) << 1) + ((X >> (N << 1) - (i << 1) - 2) & 1);
}
void move()
{
for(int i = 0;i < N;i++)
for(int j = 0;j < times(A,i);j++)
for(int k = 0;k < N;k++)
if((P[i] >> (N - k - 1)) & 1) G[k / M][k % M]++;
}
void write()
{
for(int i = 0;i < N;i++)
for(int j = 0;j < times(B,i);j++) printf("%d ",i + 1);
}
void dfs()
{
while(1)
{
A++;
if(A > (1 << ((N << 1) + 1))) break;
int t = 0;
for(int i = 0;i < N;i++) t += times(A,i);
if(t < m)
{
move();
if(is_ok())
{
m = t;
B = A;
}
}
for(int i = 0;i < M;i++)
for(int j = 0;j < M;j++)
G[i][j] = TG[i][j];
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
dfs();
write();
printf("\n");
//printf("Time : %.3f\n",(double)clock() / CLOCKS_PER_SEC);
return 0;
}

• @ 2015-12-29 17:52:38

//暴搜
const a:array[1..9,0..9] of integer=((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));
var b,c,ans:array[0..46] of integer;
i,j,k:integer;

procedure bc;
var s,i,j,u:integer;
begin
s:=0;
u:=0;
for i:=1 to 9 do
inc(s,c[i]);
if s<ans[0] then
for i:=1 to 9 do
ans[i]:=c[i];
if s<ans[0] then ans[0]:=s;
end;

procedure pd;
var i:integer;
begin
for i:=1 to 9 do
if b[i]<>12 then exit;
bc;
end;

procedure xz(x:integer);
var i:integer;
begin
for i:=1 to a[x,0] do
begin
inc(b[a[x,i]],3);
if b[a[x,i]]>12 then dec(b[a[x,i]],12);
end;
end;

procedure ymz(k:integer);
var i:integer;
begin
if k>9 then pd else
begin
ymz(k+1);
for i:=1 to 3 do
begin
xz(k);
inc(c[k]);
ymz(k+1);
end;
xz(k);
c[k]:=0;
end;
end;

begin
ans[0]:=27;
for i:=1 to 9 do
ymz(1);
for i:=1 to 9 do
if ans[i]<>0 then
for j:=1 to ans[i] do
write(i,' ');
end.

• @ 2015-12-04 20:31:28

program abcdefg;
var
i1,i2,i3,i4,i5,i6,i7,i8,i9,c,i:longint;
j1,j2,j3,j4,j5,j6,j7,j8,j9:longint;
a,aa:array[1..9]of longint;
begin
for i:=1 to 3 do
for i:=4 to 6 do
for i:=7 to 9 do
for j1:=0 to 3 do
for j2:=0 to 3 do
for j3:=0 to 3 do
for j4:=0 to 3 do
for j5:=0 to 3 do
for j6:=0 to 3 do
for j7:=0 to 3 do
for j8:=0 to 3 do
for j9:=0 to 3 do
begin
for i:=1 to 9 do a[i]:=aa[i];
a[1]:=(a[1]+j1+j2+j4) mod 4;
a[2]:=(a[2]+j1+j2+j3+j5) mod 4;
a[3]:=(a[3]+j3 3 2+j3+j6) mod 4;
a[4]:=(a[4]+j1+j4+j5+j7) mod 4;
a[5]:=(a[5]+j1+j3+j5+j7+j9) mod 4;
a[6]:=(a[6]+j3+j5+j6+j9) mod 4;
a[7]:=(a[7]+j4+j7+j8) mod 4;
a[8]:=(a[8]+j5+j7+j8+j9) mod 4;
a[9]:=(a[9]+j6+j8+j9) mod 4;
if (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9])=0 then
begin
for i:=1 to j1 do
write(1,' ');
for i:=1 to j2 do
write(2,' ');
for i:=1 to j3 do
write(3,' ');
for i:=1 to j4 do
write(4,' ');
for i:=1 to j5 do
write(5,' ');
for i:=1 to j6 do
write(6,' ');
for i:=1 to j7 do
write(7,' ');
for i:=1 to j8 do
write(8,' ');
for i:=1 to j9 do
write(9,' ');
end;
end;
end.

• @ 2015-11-01 11:40:04

为什么全是暴力算法
这题应该用 位运算压缩状态+记忆化BFS 才对
因为只有9个钟，每个钟只有0～3四种状态，故可用18为的二进制来表示所有钟的状态。（每两位存一个钟）目标状态为全0。
移动时，把被操作钟的那两位从状态里提出来，+1，去掉进位，再压回状态中。
程序中 & 3 就是拿来去掉进位用的，因为3的二进制为00000011。
由于要输出路径，所以记录一下状态的转移即可，递归输出。

//vijos p1016
#include <stdio.h>

#define END -1
#define STATUS 0
#define STEP 1

short moves[9][6] = {
{0, 1, 3, 4, END},
{0, 1, 2, END},
{1, 2, 4, 5, END},
{0, 3, 6, END},
{1, 3, 4, 5, 7, END},
{2, 5, 8, END},
{3, 4, 6, 7, END},
{6, 7, 8, END},
{4, 5, 7, 8, END},
};

short searched[1<<20];
int queue[1<<20][2];
int prevStatus[1<<20];
int prevMove[1<<20];

void print(int status){
if(prevStatus[status] == END)
return;
print(prevStatus[status]);
printf("%d ", prevMove[status]+1);
}
if(!searched[status]){
searched[status] = 1;
queue[tail][STATUS] = status;
queue[tail][STEP] = step;
tail++;
return 1;
}
return 0;
}
void bfs(int initStatus){
int status, step, i, j, k, tmp;
if(status == 0)
break;
for(i=0; i<9; i++){
tmp = status;
for(j=0; moves[i][j]!=END; j++){
tmp &= ((1<<18)-1) ^ (3 << (2*(8-moves[i][j])));
k = (status >> (2*(8-moves[i][j]))) & 3;
tmp |= ((k+1) & 3) << (2*(8-moves[i][j]));
}
prevStatus[tmp] = status;
prevMove[tmp] = i;
}
}
}
print(0);
}
int main(){
int i, k, tmp, status;
status = 0;
for(i=0; i<3; i++){
for(k=0; k<3; k++){
status <<= 2;
scanf("%d", &tmp);
status |= tmp;
}
}
for(i=0; i<(1<<20); i++){
searched[i] = 0;
prevStatus[i] = prevMove[i] = END;
}
bfs(status);
printf("\n");
return 0;
}

• @ 2016-07-06 16:40:56

你倒是讲讲 位运算 原理啊。BFS是人都会啊。

• @ 2015-08-10 09:54:04

#include<cstdio>
#include<cstring>
using namespace std;
void turn(int x,int y)
{
map[x]=(map[x]+y)%4;
}
bool check()
{
for(int i=1;i<=9;i++)
{
if(map[i]>0)return 0;
}return 1;
}
void search(int x,int cnt)
{
if(cnt>=ans)return;
if(x==10)
{
if(!check())return;
ans=cnt;
}
else
{
for(int i=3;i>=0;i--)
{
if(x==1 || x==2 || x==4)turn(1,i);
if(x==1 || x==2 || x==3 || x==5)turn(2,i);
if(x==2 || x==3 || x==6)turn(3,i);
if(x==1 || x==4 || x==5 || x==7)turn(4,i);
if(x==1 || x==3 || x==5 || x==7 || x==9)turn(5,i);
if(x==3 || x==5 || x==6 || x==9)turn(6,i);
if(x==4 || x==7 || x==8 )turn(7,i);
if(x==5 || x==7 || x==8 || x==9)turn(8,i);
if(x==6 || x==8 || x==9 )turn(9,i);
for(int j=cnt+1;j<=cnt+i;j++)tmp[j]=x;

search(x+1,cnt+i);

if(x==1 || x==2 || x==4)turn(1,4-i);
if(x==1 || x==2 || x==3 || x==5)turn(2,4-i);
if(x==2 || x==3 || x==6)turn(3,4-i);
if(x==1 || x==4 || x==5 || x==7)turn(4,4-i);
if(x==1 || x==3 || x==5 || x==7 || x==9)turn(5,4-i);
if(x==3 || x==5 || x==6 || x==9)turn(6,4-i);
if(x==4 || x==7 || x==8 )turn(7,4-i);
if(x==5 || x==7 || x==8 || x==9)turn(8,4-i);
if(x==6 || x==8 || x==9 )turn(9,4-i);
for(int j=cnt+1;j<=cnt+i;j++)tmp[j]=0;
}
}
}
int main()
{
int n,i,m,j;
for(i=1;i<=9;i++)scanf("%d",&map[i]);
ans=99999999;
search(1,0);
printf("\n");
return 0;
}

• @ 2015-08-04 16:48:28

暴力搜索就能过的嘛~ 现代计算机果然性能强劲!

``````#include <iostream>

const size_t NUMBER_OF_CLOCKS           = 9;
const size_t NUMBER_OF_OPERATIONS       = 9;
/**
* 最大操作次数.
* 由于操作4次会回到原点, 没有必要继续搜索.
*/
const size_t MAX_NUMBER_OF_OPERATIONS   = 4;

/**
* 获取当前对各个时钟操作的次数.
* @return 对各个时钟操作的次数
*/
int getOperationTimes(int* operations) {
int operationTimes = 0;

for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) {
operationTimes += operations[i];
}
return operationTimes;
}

/**
* 获取最优的调整方案
* @param  clocks - 当前每个时钟的时间([0, 4)的整数)
* @param  bestOperations - 对各个时钟最佳操作的次数
* @return 每个操作进行次数的数组
*/
void getBestSolution(int* clocks, int* bestOperations) {
/**
* 存储时钟的初始状态.
* 用于回溯, 在搜索失败后的rollback.
*/
int mirrorClocks[NUMBER_OF_CLOCKS] = {0};

/**
* 存储对时钟的操作.
*/
int operations[NUMBER_OF_OPERATIONS][NUMBER_OF_CLOCKS] = {
{ 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 }
};

/**
* 存储当前对各时钟操作的计数.
* 记录对每个时钟操作的次数.
*/
int currentOperations[NUMBER_OF_CLOCKS] = {0};

for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) {
mirrorClocks[i] = clocks[i];
}

for ( currentOperations[0] = 0 ; currentOperations[0] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[0] ) {
for ( currentOperations[1] = 0 ; currentOperations[1] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[1] ) {
for ( currentOperations[2] = 0 ; currentOperations[2] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[2] ) {
for ( currentOperations[3] = 0 ; currentOperations[3] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[3] ) {
for ( currentOperations[4] = 0 ; currentOperations[4] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[4] ) {
for ( currentOperations[5] = 0 ; currentOperations[5] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[5] ) {
for ( currentOperations[6] = 0 ; currentOperations[6] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[6] ) {
for ( currentOperations[7] = 0 ; currentOperations[7] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[7] ) {
for ( currentOperations[8] = 0 ; currentOperations[8] < MAX_NUMBER_OF_OPERATIONS; ++ currentOperations[8] ) {
// Rollback
for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) {
clocks[i] = mirrorClocks[i];
}

bool isSuccessful = true;
for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) {
for ( size_t j = 0; j < NUMBER_OF_OPERATIONS; ++ j ) {
clocks[i] += currentOperations[j] * operations[j][i];
}
clocks[i] %= 4;

if ( clocks[i] != 0 ) {
isSuccessful = false;
break;
}
}

if ( !isSuccessful ) {
continue;
}
// Save the solution
int currentOperationTimes = getOperationTimes(currentOperations);
int bestOperationTimes = getOperationTimes(bestOperations);
if ( currentOperationTimes < bestOperationTimes ) {
for ( size_t i = 0; i < NUMBER_OF_OPERATIONS; ++ i ) {
bestOperations[i] = currentOperations[i];
}
}
}
}
}
}
}
}
}
}
}
}

int main() {
/**
* 存储时钟当前的状态.
* 在搜索时不断改变.
*/
int clocks[NUMBER_OF_CLOCKS] = {0};

/**
* 存储当前对各时钟操作计数的最优解.
*/
int bestOperations[NUMBER_OF_OPERATIONS] = { 10, 10, 10, 10, 10, 10, 10, 10, 10 };

for ( size_t i = 0; i < NUMBER_OF_CLOCKS; ++ i ) {
std::cin >> clocks[i];
}

getBestSolution(clocks, bestOperations);

for ( size_t i = 0; i < NUMBER_OF_OPERATIONS; ++ i ) {
for ( int j = 0; j < bestOperations[i]; ++ j ) {
std::cout << ( i + 1 ) << " ";
}
}
std::cout << std::endl;
return 0;
}
``````
• @ 2015-07-22 13:51:28

var
aa,a:array[1..9]of integer;
i1,i2,i3,i4,i5,i6,i7,i8,i9:integer;
i,j:integer;
begin
fillchar(b,sizeof(b),0);
for i:=1 to 9 do
for i1:=0 to 3 do
for i2:=0 to 3 do
for i3:=0 to 3 do
for i4:=0 to 3 do
for i5:=0 to 3 do
for i6:=0 to 3 do
for i7:=0 to 3 do
for i8:=0 to 3 do
for i9:= 0 to 3 do
begin
for i:=1 to 9 do
aa[i]:=a[i];
aa[1]:=(aa[1]+i1+i2+i4) mod 4;
aa[2]:=(aa[2]+i1+i2+i3+i5) mod 4;
aa[3]:=(aa[3]+i2+i3+i6) mod 4;
aa[4]:=(aa[4]+i1+i4+i5+i7) mod 4;
aa[5]:=(aa[5]+i1+i3+i5+i7+i9) mod 4;
aa[6]:=(aa[6]+i3+i5+i6+i9) mod 4;
aa[7]:=(aa[7]+i4+i7+i8) mod 4;
aa[8]:=(aa[8]+i5+i7+i8+i9) mod 4;
aa[9]:=(aa[9]+i6+i8+i9) mod 4;
if (aa[1]+aa[2]+aa[3]+aa[4]+aa[5]+aa[6]+aa[7]+aa[8]+aa[9]=0) then
begin
for j:=1 to i1 do
write(1,' ');
for j:=1 to i2 do
write(2,' ');
for j:=1 to i3 do
write(3,' ');
for j:=1 to i4 do
write(4,' ');
for j:=1 to i5 do
write(5,' ');
for j:=1 to i6 do
write(6,' ');
for j:=1 to i7 do
write(7,' ');
for j:=1 to i8 do
write(8,' ');
for j:=1 to i9 do
write(9,' ');
writeln;
halt;
end;
end;
end.

• @ 2015-03-26 12:35:11

###75ms
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<time.h>
#include<stdlib.h>
using namespace std;

int a[9][9] = {
{0, 1, 3, 4, -1 },
{0, 1, 2, -1 },
{1, 2, 4, 5, -1 },
{0, 3, 6, -1 },
{1,3,4,5,7,-1},
{2,5,8,-1},
{3,4,6,7,-1},
{6,7,8,-1},
{4,5,7,8,-1}
};
int c[9];
int o[9];
int mi;
int ans[9];
bool ok(){
int i;
for (i = 0; i < 9; i++)if (c[i])return false;
return true;
}
void change(int op){
int i;
for (i = 0; a[op][i]!=-1; i++){
c[a[op][i]]++;
c[a[op][i]] %= 4;
}
}

void go(int op, int now){

if (ok()){
mi = now;
memcpy(ans, o, sizeof(o));
return;
}
if (op==9||now>=mi)return;
int i;
for (i = 0; i < 4; i++,change(op)){
o[op] = i;
go(op + 1, now + i);
}
o[op] = 0;
}
int main(){

int i;
for (i = 0; i < 9; i++)cin >> c[i];
mi = 27;
go(0, 0);
for (i = 0; i < 9; i++){
while (ans[i]--)
cout << i + 1 << " ";
}
return 0;
}

• @ 2015-03-26 08:59:41

高斯消元是错误的,这道题没法用高斯消元做,Ax=B,可是B向量有很多种,弄不好x就会变成浮点数.

• @ 2014-11-29 09:54:53

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;
int a[10],b[10][10]={{0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,1,1,0,1,1,0,0,0},
{0,1,0,0,1,0,0,1,0,0},
{0,0,1,0,1,1,1,0,1,0},
{0,0,0,1,0,0,1,0,0,1},
{0,0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
void find()
{
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool flag=true;
for (int i=1; i<=9; i++) a[i]=d[i];
for (int i=1; i<=9; i++)
{
for (int j=1; j<=9; j++) a[i]+=c[j]*b[j][i];
a[i]%=4;
if (a[i]!=0) {flag=false; break;}
}
if (flag)
{
int ss=0;
for (int i=1; i<=9; i++) ss+=c[i];
if (ss<m) ss=m;
for(int i=1; i<=9; i++) e[i]=c[i];
}
}
}
int main()
{
for(int i=1; i<=9; i++)
{
cin>>a[i];
d[i]=a[i];
}
find();
bool flag=false;
for(int i=1;i<=9;i++)
for(int j=1; j<=e[i]; j++)
{
if(flag) cout<<" "; else flag=true;
cout<<i;
}
return 0;
}

• @ 2014-08-08 17:34:13

#include<iostream>
using namespace std;
int a[10],b[10][10]={{0},{0,1,1,0,1,1,0,0,0,0},{0,1,1,1,0,0,0,0,0,0},{0,0,1,1,0,1,1,0,0,0},{0,1,0,0,1,0,0,1,0,0},{0,0,1,0,1,1,1,0,1,0},{0,0,0,1,0,0,1,0,0,1},{0,0,0,0,1,1,0,1,1,0},{0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
main()
{
for(int i=1;i<=9;i++)
{
cin>>a[i];
d[i]=a[i];
}
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool bo=1;
for(int i=1;i<=9;i++)
a[i]=d[i];
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
a[i]+=c[j]*b[j][i];
a[i]%=4;
if(a[i]!=0)
{
bo=0;
break;
}
}
if(bo)
{
int ss=0;
for(int i=1;i<=9;i++)
ss+=c[i];
if(ss<m)
ss=m;
for(int i=1;i<=9;i++)
e[i]=c[i];
}
}
bool bo=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=e[i];j++)
{
if(bo)
cout<<" ";
else
bo=1;
cout<<i;
}
}

• @ 2014-08-08 17:29:52

#include<iostream>
#include<cstring>
using namespace std;
int a[10],b[10][10]={{0},{0,1,1,0,1,1,0,0,0,0},{0,1,1,1,0,0,0,0,0,0},{0,0,1,1,0,1,1,0,0,0},{0,1,0,0,1,0,0,1,0,0},{0,0,1,0,1,1,1,0,1,0},{0,0,0,1,0,0,1,0,0,1},{0,0,0,0,1,1,0,1,1,0},{0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,1,1,0,1,1}},s=0,m=1000000,c[10],d[10],e[10];
main()
{
for(int i=1;i<=9;i++)
{
cin>>a[i];
d[i]=a[i];
}
for(c[1]=0;c[1]<=3;c[1]++)
for(c[2]=0;c[2]<=3;c[2]++)
for(c[3]=0;c[3]<=3;c[3]++)
for(c[4]=0;c[4]<=3;c[4]++)
for(c[5]=0;c[5]<=3;c[5]++)
for(c[6]=0;c[6]<=3;c[6]++)
for(c[7]=0;c[7]<=3;c[7]++)
for(c[8]=0;c[8]<=3;c[8]++)
for(c[9]=0;c[9]<=3;c[9]++)
{
bool bo=1;
for(int i=1;i<=9;i++)
a[i]=d[i];
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
a[i]+=c[j]*b[j][i];
a[i]%=4;
if(a[i]!=0)
{
bo=0;
break;
}
}
if(bo)
{
int ss=0;
for(int i=1;i<=9;i++)
ss+=c[i];
if(ss<m)
ss=m;
for(int i=1;i<=9;i++)
e[i]=c[i];
}
}
bool bo=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=e[i];j++)
{
if(bo)
cout<<" ";
else
bo=1;
cout<<i;
}
}

ID
1016

5

4782

1601

33%

15