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.****.net/sf____/article/details/9863927

爆搜的特点：

操作对环境的改变是无序的，每个操作都会影响到周围的状态。
同时每一种操作都有周期性限制，也即最多需要几次操作，多于这个次数产生循环。

这里，有4种循环的状态，因此每个移动操作顶多使用3次。

爆搜代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #define LL __int64

 const int maxn = +;

 const int INF = <<;

 using namespace std;

 int main()

 {

       int x,a[],i[],j[];

       for(x=; x<=; x++)

       scanf("%d",&a[x]);

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       for(i[]=; i[]<=; i[]++)

       {

             j[]=(a[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[]+i[])%;

             j[]=(a[]+i[]+i[]+i[])%;

             if(j[]+j[]+j[]+j[]+j[]+j[]+j[]+j[]+j[]==)

             {

                     for(x=; x<i[]; x++) printf("1 ");

                     for(x=; x<i[]; x++) printf("2 ");

                     for(x=; x<i[]; x++) printf("3 ");

                     for(x=; x<i[]; x++) printf("4 ");

                     for(x=; x<i[]; x++) printf("5 ");

                     for(x=; x<i[]; x++) printf("6 ");

                     for(x=; x<i[]; x++) printf("7 ");

                     for(x=; x<i[]; x++) printf("8 ");

                     for(x=; x<i[]; x++) printf("9 ");

                     cout<<endl;

             }

       }

     return ;

 }

 // 逆矩阵

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int a[][]={

 {,,,,,,,,,},

 {,,,,,,,,,},

 {,,,,,,,,,},

 {,,,,,,,,,},

 {,,,,,,,,,},

 {,,,,,,,,,},

 {,,,,,,,,,},

 {,,,,,,,,,},

 {,,,,,,,,,}};

 int x[];

 int res[];

 int main()

 {

     for(int i=;i<;i++)

     {

         scanf("%d",x+i);

         x[i]=(-x[i])%;

     }

     for(int i=;i<;i++)

         for(int j=;j<;j++)

             res[i]+=a[i][j]*x[j];

     for(int i=;i<;i++) while(res[i]% && res[i]--)

         printf("%d ",i+);

     puts("");

 }

秒客网

POJ 1166 The Clocks （爆搜 || 高斯消元）

相关文章