相关讲解可在USACO上看原文，也可以搜索nocow找到翻译的！ (nocow上有些微翻译是有问题的，如果想看nocow翻译的建议也对着英文看)

以下记录以下 自己之前未掌握的一些要点,以及按自己的括号表述的形式来记录。

USACO Section 5.3 启发式搜索

启发式搜索的主要思想是通过评价一个状态有"多好"来改进对于解的搜索.

0<= 可行的估价函数 <= 实际代价

1. 启发式剪枝: 若搜到最小值，已经搜索到的最优值为C，当前的代价为A(从起始状态到这里的实际代价)，启发的期望剩余代价为B（从当前点到目标的估价），如果A+B>C也就是期望总代价比已经搜索的还大，那么剪枝，注意到上面有提到：估价函数是小于等于实际代价，也就意味实际代价>=A+B>C,所以可以剪枝

2. Best-First Search最佳优先: 深搜 中，在子节点访问顺序部分做估价处理，调整搜索顺序，再结合上面的剪枝

3. A* 可以和第二条相对，看做广搜中加入了顺序估价。

关于估价函数

如果为0，可以看做毫无优化的默认算法。

如果为实际代价，那么就直接可以最快向目标前进。

Milk Measuring - milk4

题意

从P个数中选 取任意个数，使得它们的整数倍数的和=Q

如P: 3,3,5,7

Q:16

16=3*2+5*1

目标，1选的数的个数尽量小，2在个数尽量小的时候，字典序最小

1<=Q<=200000

1<=P<=100

1<=每个数<=10000

输出选择的方案

通过不了的题解

emmmm 我为什么一看就是个sort(从大到小)+dp[当前第几个数][和的值]= {最小选取的个数,最后选择的index,选择的个数,倒数第一次选择的index}

空间O(Q*P),时间O(Q*P) 能得到最小的个和方案,

dp时 优先个数(目标要求个数)，其次上一次的index(因为sort过 且目标要求字典序)，个数用来反向输出方案

#include 
    
     #define rep(i,a,n) for (int i=a;i
     
      =a;i--)using namespace std;const string filename = "milk4";void usefile(){  freopen((filename+".in").c_str(),"r",stdin);  freopen((filename+".out").c_str(),"w",stdout);}tuple
      
       dp[110][20010]; // {usecnt+1,lastuseidx,lastusecnt,preidx};int val[110];int Q;int P;int main(){  usefile();  cin>>Q;  cin>>P;  rep(i,0,P){    scanf("%d",val+i);  }  sort(val,val+P,greater
       
        ());  rep(p,0,P){    dp[p][0] = {1,-1,0,-1};  }  rep(p,0,P){    if(p>0){      rep(q,0,Q+1){        dp[p][q]=dp[p-1][q];      }    }    rep(q,0,Q){      auto & item = dp[p][q];      if(get<0>(item) > 0){        if(q+val[p] > Q)break;        auto & pre = dp[p][q+val[p]];        tuple
        
          now = {          get<0>(item)+ (p !=get<1>(item)),          p,          (p!=get<1>(item))?1:get<2>(item)+1,          (p!=get<1>(item))?get<1>(item):get<3>(item)        };        if(get<0>(pre) == 0 || get<0>(pre) >= get<0>(now)){          pre = now;        }      }    }  }  // rep(p,0,P){  //   cout<<"P:"<
         
<
          
           (dp[p][q]),get<1>(dp[p][q]),get<2>(dp[p][q]),get<3>(dp[p][q])); // } // cout<
           
            (ans)-1); int qq = Q; while(1){ printf(" %d",val[get<1>(ans)]); qq-= get<2>(ans) * val[get<1>(ans)]; if(get<3>(ans) == -1){ break; } ans = dp[get<3>(ans)][qq]; } printf("\n"); return 0;}
           
          
        
       
      
     
    

然而不幸的是超空间限制了

Execution error: Your program (milk4') exited with signal #11 (segmentation violation [maybe caused by accessing memory out of bounds, array indexing out of bounds, using a bad pointer (failed open(), failed malloc), or going over the maximum specified memory limit]). The program ran for 0.000 CPU seconds before the signal. It used 31552 KB of memory. `

优化可以优化掉p，在实现记录的时候用指针的方式，没有尝试能不能改过

可通过的解

IDDFS 迭代加深搜索，使用场景，在低的层级找到解就是最优/目标解。

和广搜的区别是，广搜过程中会用内存记录，而迭代加深每次都是深搜，但是逐次增加深度。

可行性：每次加深深度，新的状态和上一层的状态是数量级差异，所以其实只和最后成功搜索到的层数的数量级相关。

综上，IDDFS有着接近广搜的性能，有着接近深搜的空间消耗。

实现pass如下

#include 
    
     #define rep(i,a,n) for (int i=a;i
     
      =a;i--)using namespace std;const string filename = "milk4";void usefile(){  freopen((filename+".in").c_str(),"r",stdin);  freopen((filename+".out").c_str(),"w",stdout);}int vis[20010];int ans[110];int val[20010];int Q;int P;int dep;bool check(){  rep(i,1,Q+1){    vis[i]=0;  }  rep(i,0,dep){    rep(j,0,Q+1-ans[i]){      if(vis[j]){        vis[j+ans[i]]=true;      }    }  }  if(vis[Q]){    return true;  }  return false;}bool dfs(int idx,int cnt){  ans[cnt] = val[idx];  if(cnt+1 == dep){    return check();  }  rep(j,idx+1,P+2+cnt-dep){    if(dfs(j,cnt+1)){      return true;    }  }  return false;}void output(){  printf("%d",dep);  rep(i,0,dep){    printf(" %d",ans[i]);  }  printf("\n");}int main(){  usefile();  cin>>Q;  cin>>P;  rep(i,0,P){    scanf("%d",val+i);  }  sort(val,val+P);  vis[0]=1;  for(dep=1;dep<=P;dep++){    rep(i,0,P+1-dep){      if(dfs(i,0)){        output();        return 0;      }    }  }  return 0;}
     
    

Window Area - window

题意

在电脑上窗口的操作,5种

• 新建窗口(标识符，x1,y1,x2,y2)
• 置顶t(标识符)
• 置底b(标识符)
• 删除d(标识符)
• 输出窗体可见百分比s(I) ,询问数<=500

窗体个数上限(2*26+10=62)

坐标范围[1->32767]

题解

那么显然 横纵坐标只有((2×62)^2)个，离线+离散+没了？

#include 
    
     #define rep(i,a,n) for (int i=a;i
     
      =a;i--)typedef long long ll;using namespace std;const string filename = "window";void usefile(){  freopen((filename+".in").c_str(),"r",stdin);  freopen((filename+".out").c_str(),"w",stdout);}list
      
       Is[240][240]; // 大小猜的vector
       
        x;vector
        
         y;vector
         
          
            >q;int itr = 0;vector
           
            
              >xys;tuple
             
               xyxy[123];void rm(int ix,int iy,char I){ for (list
              
               ::iterator it=Is[ix][iy].begin(); it!=Is[ix][iy].end(); ++it){ if(*it == I){ Is[ix][iy].erase(it); return ; } }}void top(int ix,int iy,char I){ rm(ix,iy,I); Is[ix][iy].push_front(I);}void bot(int ix,int iy,char I){ rm(ix,iy,I); Is[ix][iy].push_back(I);}int main(){ usefile(); char op; while(~scanf("%c",&op)){ if(op!='w' && op!='t' && op!='b' && op!='d' && op!='s')continue; if(op == 'w'){ char I; int x1,y1; int x2,y2; scanf("(%c,%d,%d,%d,%d)",&I,&x1,&y1,&x2,&y2); if(x1> x2){ swap(x1,x2); } if(y1>y2){ swap(y1,y2); } x.push_back(x1); x.push_back(x2); y.push_back(y1); y.push_back(y2); q.push_back({op,I}); xys.push_back({x1,y1,x2,y2}); }else{ char I; scanf("(%c)",&I); q.push_back({op,I}); } } sort(x.begin(),x.end()); sort(y.begin(),y.end()); for(auto item:q){ int op = get<0>(item); int I = get<1>(item); if(op == 'w'){ xyxy[I] = xys[itr++]; } int x1idx=lower_bound(x.begin(),x.end(),get<0>(xyxy[I]))-x.begin(); int y1idx=lower_bound(y.begin(),y.end(),get<1>(xyxy[I]))-y.begin(); int x2idx=lower_bound(x.begin(),x.end(),get<2>(xyxy[I]))-x.begin(); int y2idx=lower_bound(y.begin(),y.end(),get<3>(xyxy[I]))-y.begin(); switch(op){ case 'w': { rep(ix,x1idx,x2idx){ rep(iy,y1idx,y2idx){ Is[ix][iy].push_front(I); } } break; } case 't': { rep(ix,x1idx,x2idx){ rep(iy,y1idx,y2idx){ top(ix,iy,I); } } break; } case 'b': { rep(ix,x1idx,x2idx){ rep(iy,y1idx,y2idx){ bot(ix,iy,I); } } break; } case 'd': { rep(ix,x1idx,x2idx){ rep(iy,y1idx,y2idx){ rm(ix,iy,I); } } break; } case 's': { ll sshow = 0; rep(ix,x1idx,x2idx){ rep(iy,y1idx,y2idx){ sshow+= ((*Is[ix][iy].begin() == I)?(x[ix+1]-x[ix])*ll(y[iy+1]-y[iy]):0); } } ll scnt = (x[x2idx]-x[x1idx])*ll(y[y2idx]-y[y1idx]); printf("%.3lf\n",sshow*100/double(scnt)); break; } } } return 0;}
              
             
            
           
          
         
        
       
      
     
    

emmmmmm 在第11个点的时候 出现了唯一标识复用的情况，也就是说 先创建 再删除 再创建，所以期望的边数也就不只 (26*2+10)*2，我这里尝试的是开到240*240才能过

所以基本上是 离散化 O(长乘宽(分化的区块个数)*62(每次操作代价)*(t+b+r操作个数)+长乘宽(分化区块个数)*1(操作代价)*(w+s操作个数))

以上代码还可以优化的地方:

1. 通过预处理 真实值到离散值，让每个这样的计算只发生一次。

2. 再建立一个表来优化top,bot,rm到接近O1每次，额外的指针访问时间，缺点是1增加空间，2本身数据不大的情况，枚举查找的效率是不差的

然后有一些博文有 两个矩形之间处理的优化，也就是 不分成9块，而是分成最多5块，类似旋图，然后平时只记录相对的层数(z-index)，然后在查询的时候，才自值开始向上查找。

Network of Schools - schlnet

题意

有向图,(N<=100)个节点

1. 求最少选取多少个点，通过这些点能够沿着有向边到达所有的点
2. 求最少加多少边，让真个图变成全连通

题解

emmmm一眼

1. 直接求强连通，然后缩点，然后按照出度排序，从0开始删，直到为最后只剩独立点，进行统计？
2. 把这些缩点后的 max(出度为0的点,入度为0的点)

强连通直接tarjan

#include 
    
     #define rep(i,a,n) for (int i=a;i
     
      =a;i--)using namespace std;const string filename = "schlnet";void usefile(){  freopen((filename+".in").c_str(),"r",stdin);  freopen((filename+".out").c_str(),"w",stdout);}int n;vector
      
       p2[110];const int N=100;int id = 0;bool vis[N+10];int low[N+10];int dfn[N+10];vector
       
        stk;bool instk[N+10];int incnt[N+10];int outcnt[N+10];void scc(int idx){  // cout<<"scc"<
        
         <
         
          low } } if(low[idx] == dfn[idx]){ // cout<<"zip:"<
          
           <
           
             %d\n",i,item); incnt[item]++; outcnt[i]++; } } } int in0cnt=0,out0cnt=0; rep(i,1,n+1){ if(dfn[i] == i){ in0cnt+=incnt[i] == 0; out0cnt+=outcnt[i] == 0; } } printf("%d\n",in0cnt); // single check int pcnt = 0; rep(i,1,n+1){ pcnt+=dfn[i]==i; } if(pcnt == 1){ printf("0\n"); }else{ printf("%d\n",max(in0cnt,out0cnt)); } return 0;}
           
          
         
        
       
      
     
    

Big Barn - bigbrn

题意

NxN(N<=1000)矩阵A点上值有0或1

1的个数<=10000

求最大的全0正方形(不能斜着)

输出边长即可

题解

这感觉二分答案？因为二分的话如果大的可行，那么小的必定可行

又必定正方形的左侧和上侧都有点（边界看做全是点）

假设存在一个最优解左侧没有相邻点，则可以向左平移直到有点，对上侧同理。

emm 这样想下去，暂时没想到一个时间复杂度内能完成的解法，再看又像是二维线段树,跟着2维线段树的思路联想到前缀和的类似的矩阵处理

假设当前测试的长度为len

那么用B[i][j]表示 A[i->i+len-1][j]为1的个数

C[i][j]表示A[i->i+len-1][j->j+len-1]为1的个数,即是C[i][j->j+len-1]

根据前缀和类似的算法，A->B可以在O(N^2)完成B->C也同理,综上O(N^2*log(N))

然而很不幸的是 usaco给的空间是真的有限，就算换成 new 也会在第11个点挂掉,所以bit压位,然而事后发现，可以不用存储C，直接判断C的值就好了，从空间O(3N^2)变为O(2N^2)就能过

#include 
    
     #define rep(i,a,n) for (int i=a;i
     
      =a;i--)using namespace std;const string filename = "bigbrn";void usefile(){  freopen((filename+".in").c_str(),"r",stdin);  freopen((filename+".out").c_str(),"w",stdout);}int n,t;// bitset<8> A[1010][130];// [1010][1010]; // N*N// bitset<8> B[1010][130];// [1010][1010]; // (N+1-len)*N// //bitset<8> C[1010][130];// [1010][1010]; // (N+1-len)*(N+1-len)// 如果注释掉下面两行用 上面bitset的A和B也能过int A[1010][1010];int B[1010][1010];void setv(bitset<8> *arr,int idx,int v){  arr[idx/8].set(idx%8,bool(v));}int getv(bitset<8> *arr,int idx){  return arr[idx/8][idx%8];}void setv(int *arr,int idx,int v){  arr[idx]=v;}int getv(int *arr,int idx){  return arr[idx];}bool ok(int len){  if(len == 0)return true;  // A->B  rep(j,0,n){    int cnt = 0;    rep(i,0,len){      cnt+=getv(A[i],j);    }    setv(B[0],j,cnt);    rep(i,1,n+1-len){      cnt+=getv(A[i+len-1],j)-getv(A[i-1],j);      setv(B[i],j,cnt);    }  }  // B->C  rep(i,0,n+1-len){    int cnt= 0;    rep(j,0,len)      cnt+=getv(B[i],j);    if(cnt == 0)return true;    rep(j,1,n+1-len){      cnt+=getv(B[i],j+len-1)-getv(B[i],j-1);      if(cnt == 0)return true;    }  }  return false;}bool all1(){  rep(i,0,n){    rep(j,0,n){      if(A[i][j] == 0){        return false;      }    }  }  return true;}int main(){  usefile();  cin>>n>>t;  rep(i,0,t){    int x,y;    scanf("%d %d",&x,&y);    setv(A[x-1],y-1,1);  }  int lenl=0,lenr=n+1;  while(lenl+1
     
    

总结

emmmmm所以这些题目和标题的启发式搜索的关系是?