pku1165 The Primes (枚举加剪枝)

题目:

题目大意是说用数字填充5*5的矩阵，使得每行每列以及对角线的数字和相等，等于一个给定的数，并且每行每列的数字串形成的5位数为素数。听从周SIR的方案，用了一个比较笨的方式，对每个格子上的数从0到9开始枚举，中间加些枚举，具体实现方式如下分析(摘自discuss):

注意到：最后一行和最后一列的数都是奇数，第一行和第一列中不能含有0。

先用筛选法把5位的素数找出来，并按首个数字分别存到9（1－－9）个槽里。
按这样的策略搜索：

先枚举最后一列，这里的约束较多（第个数都是奇数）。
然后枚举第一列，这个约束还是不错的（不能含有0，第一个数字己确定）。
你可能觉得已经不错了，每一行都有两个约束了。
但是两个对角线却提供了更多的方便。
枚举第一个对角线，再枚举第二个对角线。

现在应该到搜索每一行了。(我实现的方式与下面说的有点不同，我是从第一行开始，按下面的效率应该更高)
容易看到，第二行和第四行的约束条件较多（有四个），先选定这两行，
再枚举第三行，这有三个约束条件。
然后是第一行。

最后一行就不用枚举了，可以算出来的。
之后再检查一遍是否满足这种要求。

最好就不要存储整型的数了，上面的素数都转换为字符串存好，这可以省掉中间乘法和除法的时间。

 

再有就是由于串中间有可能就有为0的字符，这使得一些串函数会失效，于是自己写了个丑陋的cmp,cpy,以及冒泡....

my code:

 

#include"stdio.h"
#include"math.h"
char x[27];
int sum,t,f[5],len;
int p[100000];
char ans[100][27];
void mcpy(char *a,char *b)//拷贝
{
  int i;
  for(i=1;i<=25;i++)a[i]=b[i];
}
int mcmp(char *a,char *b)//比较
{
  int i;
  for(i=1;i<26;i++)
    if(a[i]>b[i])return 1;
    else if(a[i]<b[i])return -1;
  return 0;
}
void msort()//冒泡排序
{
  int i,j;char temp[27];
  for(i=0;i<len-1;i++)
  {
    for(j=0;j<len-i-1;j++)
    {
      if(mcmp(ans[j],ans[j+1])>0)
      {
        mcpy(temp,ans[j]);
        mcpy(ans[j],ans[j+1]);
        mcpy(ans[j+1],temp);
      }
    }
  }
}
void show()//输出结果
{
  int i,j;
  for(i=0;i<len;i++)
  {
    for(j=1;j<=25;j++)
    {
      printf("%d",ans[i][j]);
      if(j%5==0) printf("\n");
    }
    printf("\n");
  }
}
void sieve(int M)//筛法求素数，p[i]=1,表示为i为素数；反之亦然。
{
    int i,M2,k,i2;
    M2=(int)pow(M,0.5)+3;
    for(i=0;i<=M;i+=2)p[i]=0;
        for(i=1;i<=M;i+=2)p[i]=1;
    p[2]=1;p[1]=0;
    for(i=3;i<=M2;i+=2)
    {
        if(p[i]==1)
        {
            i2=i+i; k=i2+i;
            while(k<=M)
            {p[k]=0;k+=i2;}
        }
    }
}

/*

x[1...25]位置如下

 1  2  3  4  5 d

 6  7  8  9 10 c

11 12 13 14 15 b

16 71 81 19 20 a

21 22 23 24 25 n

 i  j  k  m  n 

*/
int main()
{
  int i,j,k,m,n,a,b,c,d,bottom;x[0]=1;
  f[0]=1;f[1]=10;f[2]=100;f[3]=1000;f[4]=10000;//十进制权值
  sieve(100000);//10万以内的素数判定
  scanf("%d%d",&sum,&t);
  x[1]=t;len=0;

  /*开始犯傻，最后一行和最后一列的数如上图用字母表示。。到后来发现好像字母不够用，于是改成用x[i]表示，开始是猪脑啊。。*/

/*i,j,k,m,n分别表示x[21]...x[25]*/
  for(i=1;i<=9;i+=2)//i表示的其实是x[21]
  {
    if(i>sum)break;
    if(i+36<sum)continue;
    if(i==5)continue;
    for(j=1;j<=9;j+=2)
    {
      if(i+j+27<sum)continue;
      if(i+j>sum)break;
      if(j==5)continue;
      for(k=1;k<=9;k+=2)
      {
        if(i+j+k>sum)break;
        if(k==5)continue;
        if(i+j+k+18<sum)continue;
        for(m=1;m<=9;m+=2)
        {
          if(i+j+k+m>sum)break;
          if(m==5)continue;
          n=sum-m-i-j-k;
         if(n>9||n<1)continue;
          if(n==5)continue;
          bottom=n*f[0]+m*f[1]+k*f[2]+j*f[3]+i*f[4];
          if(n!=1&&n!=3&&n!=7&&n!=9)continue;
          if(p[bottom]==0)continue;
          x[21]=i;x[22]=j;x[23]=k;x[24]=m;x[25]=n;
          for(a=1;a<=9;a+=2)
          {
             if(a+n+27<sum)continue;
              if(a+n>sum)break;
              if(a==5)continue;
              for(b=1;b<=9;b+=2)
              {
                 if(a+b+n+18<sum)continue;
                 if(a+b+n>sum)break;
                  if(b==5)continue;
                 for(c=1;c<=9;c+=2)
                 {
                     if(a+b+c+n>sum)break;
                      if(c==5)continue;
                      d=sum-a-b-c-n;
                      if(d==5)continue;
                      if(d!=1&&d!=3&&d!=7&&d!=9)continue;
                      bottom=d*f[4]+c*f[3]+b*f[2]+a*f[1]+n*f[0];
                      if(p[bottom]==0)continue;
                      x[5]=d;x[10]=c;x[15]=b;x[20]=a;
                      for(x[7]=0;x[7]<=9;x[7]++)
                     {
                         if(x[1]+x[7]+27<sum)continue;
                         if(x[1]+x[7]>sum)break;
                          for(x[13]=0;x[13]<=9;x[13]++)
                         {
                             x[19]=sum-x[1]-x[7]-x[13]-x[25];if(x[19]<0||x[19]>9)continue;
                             bottom=x[25]*f[0]+x[19]*f[1]+x[13]*f[2]+x[7]*f[3]+x[1]*f[4];
                             if(p[bottom]==0)continue;
                             for(x[17]=0;x[17]<=9;x[17]++)
                             {
                                 if(x[17]+9<sum-x[21]-x[17]-x[5])continue;
                                 x[9]=sum-x[21]-x[17]-x[13]-x[5];if(x[9]<0||x[9]>9)continue;
                                 if(x[21]+x[17]+x[13]+x[9]+x[5]!=sum)continue;
                                 bottom=x[5]*f[0]+x[9]*f[1]+x[13]*f[2]+x[17]*f[3]+x[21]*f[4];
                                 if(p[bottom]==0)continue;
                                 for(x[2]=1;x[2]<=9;x[2]++)
                                 {
                                     if(x[1]+x[2]+x[5]+18<sum)continue;
                                     for(x[3]=1;x[3]<=9;x[3]++)
                                     {
                                         if(x[1]+x[2]+x[3]+x[5]+9<sum)continue;
                                         x[4]=sum-x[1]-x[2]-x[3]-x[5];if(x[4]<=0||x[4]>9)continue;
                                         bottom=x[5]*f[0]+x[4]*f[1]+x[3]*f[2]+x[2]*f[3]+x[1]*f[4];
                                         if(p[bottom]==0)continue;
                                         for(x[8]=0;x[8]<=9;x[8]++)
                                         {
                                             x[6]=sum-x[7]-x[8]-x[9]-x[10];if(x[6]<=0||x[6]>9)continue;
                                             bottom=x[10]*f[0]+x[9]*f[1]+x[8]*f[2]+x[7]*f[3]+x[6]*f[4];
                                             if(p[bottom]==0)continue;
                                             for(x[11]=1;x[11]<=9;x[11]++)
                                             {
                                                 x[12]=sum-x[2]-x[7]-x[17]-x[22];if(x[12]<0||x[12]>9)continue;
                                                 x[14]=sum-x[11]-x[12]-x[13]-x[15];if(x[14]<0||x[14]>9)continue;
                                                 if(x[14]+x[4]+x[9]+x[19]+x[24]!=sum)continue;
                                                 bottom=x[22]*f[0]+x[17]*f[1]+x[12]*f[2]+x[7]*f[3]+x[2]*f[4];
                                                 if(p[bottom]==0)continue;
                                                 bottom=x[15]*f[0]+x[14]*f[1]+x[13]*f[2]+x[12]*f[3]+x[11]*f[4];
                                                 if(p[bottom]==0)continue;
                                                 x[16]=sum-x[1]-x[6]-x[11]-x[21];if(x[16]<=0||x[16]>9)continue;
                                                 bottom=x[21]*f[0]+x[16]*f[1]+x[11]*f[2]+x[6]*f[3]+x[1]*f[4];
                                                 if(p[bottom]==0)continue;
                                                 x[18]=sum-x[16]-x[17]-x[19]-x[20];if(x[18]<0||x[18]>9)continue;
                                                 if(x[3]+x[8]+x[13]+x[18]+x[23]!=sum)continue;
                                                 bottom=x[20]*f[0]+x[19]*f[1]+x[18]*f[2]+x[17]*f[3]+x[16]*f[4];
                                                 if(p[bottom]==0)continue;
                                                 bottom=x[23]*f[0]+x[18]*f[1]+x[13]*f[2]+x[8]*f[3]+x[3]*f[4];
                                                 if(p[bottom]==0)continue;
                                                 bottom=x[24]*f[0]+x[19]*f[1]+x[14]*f[2]+x[9]*f[3]+x[4]*f[4];
                                                 if(p[bottom]==0)continue;
                                                 x[26]='\0';
                                                 mcpy(ans[len++],x);
                                             }
                                         }
                                     }
                                 }
                             }
                         }
                     }
                 }
             }
         }
        }
     }
    }
  }
  msort();
  show();
  return 0;
}

这题算法没啥多说的，恶搞而已，诡异的是上面的代码，用C交就过WA，用G++交就0MS AC。。