USACO Section 1.4

怎么说这些个题，看的头晕。学长说这是两百年前的题目了。这一单元学到了哈希查找的效率。

Clocks: 自己开始便是想到BFS，结果BFS一做时间不佳，空间更加不佳。不过很蛮的BFS。加上了位运算的加速和哈希表记录转态。12，3，6，9这中状态我用0，1，2，3分别表示，每个数3位，所以9个数可以用27位的数了表示，加上哈希判重。这道题还是枚举的好把0ms能AC。具体0ms在nocow上有详细的分析。

代码：

/*
ID: duanjia2
PROG: clocks
LANG: C++
*/

#include<iostream>
#include<string.h>
#include<fstream>
#include<vector>
using namespace std;
int move[10] = {0,18911232,19136512,2363904,16810048,2134536,262657,36936,73,4617};//每种动作加上一个1.
vector<int> hash[10000]; //哈希判重
const int ppt=57521883;
int que[300000],path[300000],pre[300000]; //这种BFS很蓝菲空间。
int first,rear;
ifstream fin("clocks.in");
ofstream fout("clocks.out");
bool cmp(int a)
{
     int r=a%10000,len,i;
     len=hash[r].size();
     for( i=0;i<len;i++)
          if( a==hash[r][i])
              return false;
     hash[r].push_back(a);
     return true;
}
void BFS(int a)
{
     int temp,i,front;
     memset(pre,-1,sizeof(pre));
     first=rear=0;  
     for( i=0;i<10000; i++)
          hash[i].clear();
          
     que[rear++]=a;
     hash[a%10000].push_back(a);
     
     while( first!=rear){
            front=que[first];
            for( i=1;i<=9;i++){
                 temp=(front+move[i]) & ppt; //3+1会变成4所以做与操作变成0
                 if( cmp(temp)){ 
                     pre[rear]=first;
                     path[rear]=i;
                     que[rear++]=temp;
                     if(temp==0) return ;
                 }  
            }
            first++;    
     }         
}
void Print(int i)
{  
     if(i==0) return;
     Print(pre[i]);
     if(pre[i]) fout<<' ';
     fout<<path[i];
   
}
int main()
{
    
    int s,j,a;
    s=0;
    for( i=0;i<9;i++){
         fin>>a;
         s=s*8+a/3%4;
    }
    BFS(s);
    Print(rear-1); //递归路径输出
    fout<<endl;
    return 0;
}

代码：

/*
USER: jianmei duan [duanjia2]
TASK: ariprog
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs,4392 KB]
   Test 2: TEST OK [0.011 secs,4392 KB]
   Test 3: TEST OK [0.011 secs,4392 KB]
   Test 4: TEST OK [0.011 secs,4392 KB]
   Test 5: TEST OK [0.011 secs,4392 KB]
   Test 6: TEST OK [0.022 secs,4392 KB]
   Test 7: TEST OK [0.097 secs,4392 KB]
   Test 8: TEST OK [0.173 secs,4392 KB]
   Test 9: TEST OK [0.119 secs,4392 KB]

All tests OK.
*/
#include<iostream>
#include<algorithm>
#include<fstream>
#include<string.h>
using namespace std;
bool sqf[200000];
int sq[255],num[200000],cnt;
struct node
{
       int s,d;
} ans[10001];
bool cmp(node a,node b)
{
     return (a.d<b.d||a.d==b.d&&a.s<b.s); 
}
int main()
{
    ifstream fin("ariprog.in");
    ofstream fout("ariprog.out");
    int i,n,d,m,k; 
    fin>>n>>m;
    for( i=0;i<=m;i++)
         sq[i]=i*i;
    memset(sqf,false,sizeof(sqf)); 
    for( i=0;i<=m;i++)  //先把所有的p^2+q^2的数枚举
     for( j=0;j<=i;j++)
          sqf[sq[i]+sq[j]]=true; 
    j=0;
   for( i=0;i<=130000;i++)   
        if(sqf[i]) num[j++]=i;
   sort(num,num+j); //把所有的数排序

   cnt=0;
   for( i=j-1;i>=n-1;i--){
    for( j=i-1;j>=0; j--){
         d=num[i]-num[j];
         if(num[i]-(n-1)*d<num[0]) break; //如果不能组成n长度的等差直接跳出。
         for( k=1;k<n;k++)
              if(!sqf[num[i]-k*d])
                  break;
        if( k==n){ 
            ans[cnt].s=num[i]-(n-1)*d;
            ans[cnt++].d=d;
        }
    }
   }
    if(cnt==0) fout<<"NONE"<<endl; 
    else{
   sort(ans,ans+cnt,cmp);
  
   for( i=0;i<cnt;i++)
        fout<<ans[i].s<<' '<<ans[i].d<<endl;
   }
   return 0;
}

代码：

/*
ID: duanjia2
PROG: milk3
LANG: C++
*/

#include<iostream>
#include<algorithm>
#include<string.h>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;
bool vis[21][21][21];
int ans[21],f[21];
struct node
{
       int a,b,c;
       node(int aa,int bb,int cc):a(aa),b(bb),c(cc){}
       node(){}
};
int va,vb,vc,p;
queue<node> que;
void Push(int a,int b,int c)
{
     if(!vis[a][b][c]){
         vis[a][b][c]=true;
         que.push(node(a,c));
     }
}
void BFS()
{
     while(!que.empty()) que.pop();
     memset(vis,sizeof(vis));
     memset(f,sizeof(f)); 
     memset(ans,sizeof(ans));
     int a,c,r;
     que.push(node(0,vc));
     vis[0][0][vc]=true;
     while( !que.empty()){
            node first=que.front();
            que.pop();
            a=first.a,b=first.b,c=first.c;
            if( a==0&&!f[c]){
                f[c]=1;
                ans[p++]=c;
            }
            if( a&&b!=vb){ //a->b
                if(a+b>=vb) Push(a+b-vb,c);
                else Push(0,a+b,c);
            }
            if( a&&c!=vc){ //a->c
                if(a+c>=vc) Push(a+c-vc,vc);
                else Push(0,a+c);
            }
            if( b&&a!=va){ //b->a
                if(a+b>=va) Push(va,a+b-va,c);
                else Push(a+b,c);
            }
            if( b&&c!=vc){ //b->c
                if(b+c>=vc) Push(a,b+c-vc,vc);
                else Push(a,b+c);
            }
            if( c&&a!=va){ //c->a
                 if(a+c>=va) Push(va,a+c-va);
                 else Push(a+c,0);
            }
            if( c&&b!=vb){ //c->b
                if(b+c>=vb) Push(a,b+c-vb);
                else Push(a,b+c,0);
            } 
     }
}
int main()
{
    ifstream fin("milk3.in");
    ofstream fout("milk3.out");
    fin>>va>>vb>>vc;
    p=0;
    BFS();
    sort(ans,ans+p);
    for(int i=0;i<p-1;i++)
      fout<<ans[i]<<' ';
    fout<<ans[p-1]<<endl;
   // system("pause");
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!