首页 > 代码库 > POJ 1166 The Clocks （爆搜 || 高斯消元）
POJ 1166 The Clocks （爆搜 || 高斯消元）
题目链接
题意：
输入提供9个钟表的位置（钟表的位置只能是0点、3点、6点、9点，分别用0、1、2、3）表示。而题目又提供了9的步骤表示可以用来调正钟的位置，例如1 ABDE表示此步可以在第一、二、四、五个钟调正，如原来是0点，那么调正后为3点。问经过那些步骤可以导致9个钟的位置都在0点。
分析：
这个本来是一个高斯消元的题目，但是 听说周期4不是素数， 求解过程中不能进行取余。因为取余可能导致解集变大。
不过也有用高斯消元做的，下面是用高斯消元的分析
”
Discuss也有人讨论了，4不是质数，求解过程中不能模4，不一定有解的问题。按照我的理解，题目既然说了有唯一解，就不用考虑这个问题了。
另外，寻找当前列的对应行时不能选绝对值最大的，会WA。具体原因不详
“
这个题也可以用逆矩阵做，下面有代码，代码来自：http://blog.csdn.net/sf____/article/details/9863927
爆搜的特点：
操作对环境的改变是无序的，每个操作都会影响到周围的状态。
同时每一种操作都有周期性限制，也即最多需要几次操作，多于这个次数产生循环。
这里，有4种循环的状态，因此每个移动操作顶多使用3次。
爆搜代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #define LL __int64 8 const int maxn = 70+10; 9 const int INF = 1<<28;10 using namespace std;11 12 int main()13 {14 int x,a[10],i[10],j[10];15 for(x=1; x<=9; x++)16 scanf("%d",&a[x]);17 for(i[1]=0; i[1]<=3; i[1]++)18 for(i[2]=0; i[2]<=3; i[2]++)19 for(i[3]=0; i[3]<=3; i[3]++)20 for(i[4]=0; i[4]<=3; i[4]++)21 for(i[5]=0; i[5]<=3; i[5]++)22 for(i[6]=0; i[6]<=3; i[6]++)23 for(i[7]=0; i[7]<=3; i[7]++)24 for(i[8]=0; i[8]<=3; i[8]++)25 for(i[9]=0; i[9]<=3; i[9]++)26 {27 j[1]=(a[1]+i[1]+i[2]+i[4])%4;28 j[2]=(a[2]+i[1]+i[2]+i[3]+i[5])%4;29 j[3]=(a[3]+i[2]+i[3]+i[6])%4;30 j[4]=(a[4]+i[1]+i[4]+i[5]+i[7])%4;31 j[5]=(a[5]+i[1]+i[3]+i[5]+i[7]+i[9])%4;32 j[6]=(a[6]+i[3]+i[5]+i[6]+i[9])%4;33 j[7]=(a[7]+i[4]+i[7]+i[8])%4;34 j[8]=(a[8]+i[5]+i[7]+i[8]+i[9])%4;35 j[9]=(a[9]+i[6]+i[8]+i[9])%4;36 if(j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9]==0)37 {38 for(x=0; x<i[1]; x++) printf("1 ");39 for(x=0; x<i[2]; x++) printf("2 ");40 for(x=0; x<i[3]; x++) printf("3 ");41 for(x=0; x<i[4]; x++) printf("4 ");42 for(x=0; x<i[5]; x++) printf("5 ");43 for(x=0; x<i[6]; x++) printf("6 ");44 for(x=0; x<i[7]; x++) printf("7 ");45 for(x=0; x<i[8]; x++) printf("8 ");46 for(x=0; x<i[9]; x++) printf("9 ");47 cout<<endl;48 }49 }50 return 0;51 }
1 // 逆矩阵 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 int a[9][9]={ 7 {3,2,3,2,2,1,3,1,0,}, 8 {3,3,3,3,3,3,2,0,2,}, 9 {3,2,3,1,2,2,0,1,3,},10 {3,3,2,3,3,0,3,3,2,},11 {3,2,3,2,1,2,3,2,3,},12 {2,3,3,0,3,3,2,3,3,},13 {3,1,0,2,2,1,3,2,3,},14 {2,0,2,3,3,3,3,3,3,},15 {0,1,3,1,2,2,3,2,3,}};16 17 int x[9];18 int res[9];19 20 int main()21 {22 for(int i=0;i<9;i++)23 {24 scanf("%d",x+i);25 x[i]=(4-x[i])%4;26 }27 28 for(int i=0;i<9;i++)29 for(int j=0;j<9;j++)30 res[i]+=a[i][j]*x[j];31 32 for(int i=0;i<9;i++) while(res[i]%4 && res[i]--)33 printf("%d ",i+1);34 puts("");35 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。