2020.11.24 考试题解
搜索专题
T1黑白棋游戏
寻找最少步数，一看就知道是用广搜。 （虽然我考场上用的时深搜 迭代加深）
每次只能与上下左右的交换，如果直接暴力枚举，肯定超时，考虑优化。
<1> 如果有一个点和我们要交换的点颜色一样，就没必要换了。
<2> 我们可以用状压，将每次的判断从\(O(16)\)变为\(O(1)\)。
有这些就可以了，要想更进一步，可以用双向搜索（不会，之后有空再补）。
#include<bits/stdc .h>using namespace std;#define il inline#define vocaloid(v) (v>='0'&&v<='9')template <typename T>il void read(T &x){x=0;char v=getchar();while(!vocaloid(v)) v=getchar();while(vocaloid(v)) {x=(x<<1) (x<<3) v-'0';v=getchar();}}int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};int a[5][5],b[5][5],vis[(1<<16)-1],fa[(1<<16)-1];int res[100039][4];int Beg,End,IA;struct Ans{int x,y,xx,yy,fa;}ans[100039];queue<int>q;il void init()//读入{char c;for(int i=1;i<=4;i )for(int j=1;j<=4;j ){cin>>c;a[i][j]=c-'0';}for(int i=1;i<=4;i )for(int j=1;j<=4;j ){cin>>c;b[i][j]=c-'0';}}il int GetDeci(int x[5][5])//转成压缩的状态{int comb=0,IA=0;for(int i=4;i>=1;i--)for(int j=4;j>=1;j--){comb =x[i][j]*pow(2,IA);IA ;}return comb;}il void change(int x,int a[5][5])//根据状态转回棋盘{while(x){for(int i=4;i>=1;i--)for(int j=4;j>=1;j--){a[i][j]=x%2;x/=2;}}}il bool check(int x,int y,int xx,int yy){if(xx<1||xx>4||yy<1||yy>4||a[x][y]==a[xx][yy]) return 0;else return 1;}il void bfs(){q.push(Beg);vis[Beg]=1;while(!q.empty()){int x=q.front();q.pop();change(x,a);for(int i=1;i<=4;i )for(int j=1;j<=4;j ){int x=i,y=j;for(int k=0;k<=3;k ){int xx=x dx[k],yy=y dy[k];int flag=0;if(check(x,y,xx,yy)){flag=1;int now_Deci=GetDeci(a);swap(a[x][y],a[xx][yy]);int Deci=GetDeci(a);if(!vis[Deci]){vis[Deci]=1;ans[Deci]=(Ans){x,y,xx,yy,now_Deci};fa[Deci]=now_Deci;q.push(Deci);}if(Deci==End) return ;}if(flag)swap(a[x][y],a[xx][yy]);}}}}int main(){freopen("game.in","r",stdin);freopen("game.out","w",stdout);init();Beg=GetDeci(a),End=GetDeci(b);bfs();fa[Beg]=0;while(fa[End]){IA ;res[IA][0]=ans[End].x,res[IA][1]=ans[End].y,res[IA][2]=ans[End].xx,res[IA][3]=ans[End].yy;End=fa[End];}printf("%d\n",IA);for(int i=IA;i>=1;i--)printf("%d%d%d%d\n",res[i][0],res[i][1],res[i][2],res[i][3]);return 0;}T2乌龟棋
对于这道题，我们可以打出一个非常暴力的暴力，时间复杂度大概为\(O(m^m)\)，代码如下：
il void dfs(int pos,int sum){if(pos==n) {ans=max(ans,sum);return ;}for(int i=1;i<=m;i ){if(!vis[i]){vis[i]=1;dfs(pos card[i],sum a[pos card[i]]);vis[i]=0;}}}肯定超时，所以我们需要优化。
我们注意到题目中说只有\(1,2,3,4\)四种卡牌，且每张不超过\(50\)张。所以我们可以开一个四位数组\(f_{i,j,p,q}\)，表示使用了\(1\)卡牌\(i\)张，\(2\)卡牌\(j\)张，\(3\)卡牌\(p\)张，\(4\)卡牌\(q\)张时获得的最大分数。
我们不必关心这契卡牌是以怎样的顺序使用的，反正最后都会走到同一个位置，所以我们可以用记忆化搜索或动规，转移方程为：
\[f_{i,j,p,q}=\max{(f_{i-1,j,p,q},f_{i,j-1,p,q},f_{i,j,p-1,q},f_{i,j,p,q-1})} a_{now}\]
\[now=1 1\times i 2\times j 3\times p 4\times q\]
接下来就可以直接\(dp\)了，时间复杂度最大为\(O(50^4)\)。
代码如下：
#include<bits/stdc .h>using namespace std;#define il inline#define vocaloid(v) (v>='0'&&v<='9')template <typename T>il void read(T &x){x=0;char v=getchar();while(!vocaloid(v)) v=getchar();while(vocaloid(v)) {x=(x<<1) (x<<3) v-'0';v=getchar();}}int n,m,f[59][59][59][59];int a[399],g[7];il int dfs(int i,int j,int p,int q)//记忆化搜索{if(f[i][j][p][q]) return f[i][j][p][q];if(i==g[1]&&j==g[2]&&p==g[3]&&q==g[4]) return 0;int x=1 1*i 2*j 3*p 4*q;int Max=0;if(i<g[1]) Max=max(Max,dfs(i 1,j,p,q) a[x 1]);if(j<g[2]) Max=max(Max,dfs(i,j 1,p,q) a[x 2]);if(p<g[3]) Max=max(Max,dfs(i,j,p 1,q) a[x 3]);if(q<g[4]) Max=max(Max,dfs(i,j,p,q 1) a[x 4]);return f[i][j][p][q]=Max;}int main(){freopen("tortoise.in","r",stdin);freopen("tortoise.out","w",stdout);read(n),read(m);int ser;for(int i=1;i<=n;i )read(a[i]);for(int i=1;i<=m;i )read(ser),g[ser] ;/*f[0][0][0][0]=a[1];//动态规划for(int i=0;i<=g[1];i )for(int j=0;j<=g[2];j )for(int p=0;p<=g[3];p )for(int q=0;q<=g[4];q ){if(i==0&&j==0&&p==0&&q==0) continue ;int Max=0,x=1 1*i 2*j 3*p 4*q;if(i>0) Max=max(Max,f[i-1][j][p][q] a[x]);if(j>0) Max=max(Max,f[i][j-1][p][q] a[x]);if(p>0) Max=max(Max,f[i][j][p-1][q] a[x]); if(q>0) Max=max(Max,f[i][j][p][q-1] a[x]);f[i][j][p][q]=max(Max,f[i][j][p][q]);}printf("%d\n",f[g[1]][g[2]][g[3]][g[4]]);*/printf("%d\n",dfs(0,0,0,0) a[1]);return 0;} 赞 (0)