loli的搜索测试-我真不知道是第多少次了

　　搜索测试

　　又到了....并不激动人心的搜索测试时间。

　　今天和以前还是有一点不一样的，新高二的学长们也参加了（也就是说我们又要被吊打了）

　　话不多说，看题：

　　fz：填一个5*5的质数方阵，要求每行，每列，两个对角线上的数从左往右连起来都是质数，且每个质数都没有前导零，且每个质数的每位相加之和是一个给定的数，且左上角的数字给定，输出左右方案，没有就输出NONE。

　　是一个看起来非常可做，实际上非常不可做的题目，我写了1.5h之后样例竟然还要跑15s，是的你没有看错，就是十五秒，于是我弃疗了。我的思路是，首先制作一个合法的质数表，搜出第一行，再根据第一行（也就是每一列已经有了第一个数）来搜出五个竖列，第一行和第一列的数字都不能带0，之后每搜一个就判一判合法性。听起来已经挺优化的了，然而光荣爆零。最高分也只有40分，还是一个高二的学长写的。std是一个5kb的pascal文件，完全没有去读他的欲望，于是这个题就先咕咕咕了，贴一份我的0分代码吧。　

 # include <cstdio>

 # include <iostream>

 # define R register int

 using namespace std;

 const int maxn=;

 bool pri[];

 int ans=,cnt,s,beg,firs,t[],P[maxn];

 int div (int x)

 {

     int S=;

     while (x)

     {

         S+=x%;

         x/=;

     }

     return S;

 }

 int sw (int x,int i)

 {

     if(i==) return x/;

     if(i==) return x/%;

     if(i==) return x/%;

     if(i==) return x/%;

     return x%;

 }

 void print()

 {

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

     {

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

             printf("%d",sw(t[j],i));

         printf("\n");

     }

     printf("\n");

 }

 bool check()

 {

     int a=;

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

     {

         a=;

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

             a=a*+sw(t[j],i);

         if(pri[a]==false) return false;

     }

     a=;

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

         a=a*+sw(t[i],i);

     if(pri[a]==false) return false;

     a=;

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

         a=a*+sw(t[i],-i+);

     if(pri[a]==false) return false;

     return true;

 }

 void dfs (int x)

 {

     int a,f;

     if(x==)

     {

         if(check()) ans++,print();

         return ;

     }

     if(x==)

     {

         for (R i=;i<=cnt;++i)

         {

             if(P[i]/!=sw(P[i],x)) continue;

             if(sw(P[i],)==||sw(P[i],)==||sw(P[i],)==||sw(P[i],)==||sw(P[i],)==) continue;

             t[]=P[i];

             dfs();

         }

     }

     else

     {

         for (R i=;i<=cnt;++i)

         {

             if(P[i]/!=sw(firs,x)) continue;

             t[x]=P[i];

             f=;

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

             {

                 a=;

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

                     a+=sw(t[k],j);

                 if(a>s) f=;

             }

             if(f) continue;

             dfs(x+);

         }

     }

 }

 int main()

 {

     freopen("fz.in","r",stdin);

     freopen("fz.out","w",stdout);

     scanf("%d%d",&s,&beg);

     for (R i=;i<=maxn;++i)

     {

         if(pri[i]) continue;

         for (R j=;j*i<=maxn;++j)

         pri[i*j]=true;

     }

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

         pri[i]=false;

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

     {

         pri[i]^=;

         if(pri[i]&&div(i)!=s) pri[i]=false;

     }

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

         if(pri[i]) P[++cnt]=i;

     for (R i=;i<=cnt;++i)

     {

         if(P[i]/!=beg) continue;

         if(sw(P[i],)==||sw(P[i],)==||sw(P[i],)==||sw(P[i],)==||sw(P[i],)==) continue;

         firs=P[i];

         dfs();

     }

     if(ans==) printf("NONE");

     fclose(stdin);

     fclose(stdout);

     return ;

 }

　　gift：很像背包，但是数据范围极大只能搜索的背包题，似乎要用$meet$ $in$ $the$ $middle$来做,但是爆搜可以得到$70$.

　　square：poj上一个挺经典的题目，就是问一些火柴棍删掉多少条才能破坏所有的正方形。不知道为什么大家都没有写这个题，咕咕咕？

巴特西

loli的搜索测试-我真不知道是第多少次了

最新文章

热门文章