IDA*：非常好用的搜索，可以解决很多深度浅，但是规模大的搜索问题。
估价函数设计思路：观察一步最多能向答案靠近多少。
埃及分数
题目大意：
给出一个分数，由分子a 和分母b 构成，现在要你分解成一系列互不相同的单位分数（形如：1/a，即分子为1），要求：分解成的单位分数数量越少越好，如果数量一样，最小的那个单位分数越大越好。
如：
19/45 = 1/3 + 1/12 + 1/180;
19/45 = 1/5 + 1/6 + 1/18;
以上两种分解方法都要3个单位分数，但下面一个的最小单位分数1/18比上一个1/180大，所以第二个更优。
题解：
dfs直接搜爆炸，因为深度无限。
bfs爆炸，空间不行。
所以，采用有深度限制的，并且不耗费空间的迭代加深搜索。
深度即分数的个数。
配合一下A*思想。
剪枝：
1.每次一步到达小于剩余分数的最小分母。
return b/a+1
2.如果当前可以选择的分数（已经是最大的）*剩下的步数<剩下的分数，return （A*思想）
3.如果只剩最后一步，直接判断能否取到。
对于不能取的处理，开一个数组记录。>1000都可以取的。
分数运算，手推式子。注意约分
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000+5; ll a,b; int k,T; bool fl; ll ans[N]; ll mem[N]; bool no[N]; int dp; ll getfirst(ll a,ll b){ return b/a+1; } bool cmp1(ll s1,ll m1,ll s2,ll m2){//s1/m1 > s2/m2 ? return (ll)s1*m2>(ll)m1*s2; } bool cmp2(ll s1,ll m1,ll s2,ll m2){//s1/m1 >= s2/m2 ? return (ll)s1*m2>=(ll)m1*s2; } ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; } void sub(ll &s1,ll &m1,ll s2,ll m2){ s1=s1*m2-s2*m1; m1=m1*m2; ll g=gcd(s1,m1); s1/=g; m1/=g; } bool better(){ for(int i=dp;i>=dp;i--){ if(mem[i]!=ans[i]){ //cout<<mem[i]<<" "<<ans[i]<<endl; return (ans[i]==0)||(mem[i]<ans[i]); } } return false; } void dfs(int now,ll lim,ll rs,ll rm){ //if(dp<4) cout<<now<<" "<<lim<<" "<<rs<<" "<<rm<<endl; if(now==dp){ if(rs==1){ if(rm<lim) return; //if(rm<=1000&&no[rm]) return; fl=true; //cout<<" ok "<<endl; mem[dp]=rm; if(better()){ ///cout<<"better "<<endl; for(int i=1;i<=dp;i++){ //cout<<mem[i]<<" "; ans[i]=mem[i]; }//cout<<endl; } mem[dp]=0; } return; } lim=max(lim,getfirst(rs,rm)); for(int i=lim;;i++){ if(cmp1(rs,rm,(dp-now+1),i)) return; if(cmp2(rs,rm,1,i)){ ll hs=rs,hm=rm; sub(hs,hm,1,i); mem[now]=i; dfs(now+1,i+1,hs,hm); mem[now]=0; } } } int main(){ scanf("%lld%lld",&a,&b); int t; for(int i=1;i<=k;i++){ scanf("%d",&t); no[t]=1; } fl=false; while(!fl){ dp++; //if(dp<4) cout<<dp<<endl; dfs(1,2,(ll)a,(ll)b); } for(int i=1;i<=dp;i++){ printf("%lld ",ans[i]); } return 0; }
The Rotation Game
每次8种选择吃不消。
迭代加深直接做。
A*估价：中间8个数，最多的那一个一次转动最多多一个。如果中间的8个最多的那一个和8的差距比剩余步数多，return
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=9; int mp[N][N]; int st[N][N]; char sta[10005],top; char ans[10005],sum; int dp,num; bool fl; int cnt[4]; int fan[9]={0,6,5,8,7,2,1,4,3}; int fin(){ cnt[1]=cnt[2]=cnt[3]=0; for(int i=3;i<=5;i++) for(int j=3;j<=5;j++) cnt[mp[i][j]]++; if(cnt[1]==8) return 1; if(cnt[2]==8) return 2; if(cnt[3]==8) return 3; } int che(){ cnt[1]=cnt[2]=cnt[3]=0; for(int i=3;i<=5;i++){ for(int j=3;j<=5;j++){ cnt[mp[i][j]]++; } } int big=max(cnt[1],max(cnt[2],cnt[3])); return 8-big; } void mvh(int d){ if(d==3){ int tmp=mp[3][7]; for(int i=7;i>=2;i--) mp[3][i]=mp[3][i-1]; mp[3][1]=tmp; } else if(d==4){ int tmp=mp[5][7]; for(int i=7;i>=2;i--) mp[5][i]=mp[5][i-1]; mp[5][1]=tmp; } else if(d==7){ int tmp=mp[5][1]; for(int i=1;i<=6;i++) mp[5][i]=mp[5][i+1]; mp[5][7]=tmp; } else{ int tmp=mp[3][1]; for(int i=1;i<=6;i++) mp[3][i]=mp[3][i+1]; mp[3][7]=tmp; } } void mvz(int d){ if(d==1){ int tmp=mp[1][3]; for(int i=1;i<=6;i++) mp[i][3]=mp[i+1][3]; mp[7][3]=tmp; } else if(d==2){ int tmp=mp[1][5]; for(int i=1;i<=6;i++) mp[i][5]=mp[i+1][5]; mp[7][5]=tmp; } else if(d==5){ int tmp=mp[7][5]; for(int i=7;i>=2;i--) mp[i][5]=mp[i-1][5]; mp[1][5]=tmp; } else{ int tmp=mp[7][3]; for(int i=7;i>=2;i--) mp[i][3]=mp[i-1][3]; mp[1][3]=tmp; } } bool cmp(){ for(int i=1;i<=dp;i++){ if(sta[i]<ans[i]) return true; if(sta[i]>ans[i]) return false; } return false; } void dfs(int now,int las){ if(che()>dp-now+1) return; if(now==dp+1){ if(che()==0){ if(!fl){ memcpy(ans,sta,sizeof sta); num=fin(); } else if(cmp()){ memcpy(ans,sta,sizeof sta); num=fin(); } fl=true; } return; } for(int i=1;i<=8;i++){ if(i==fan[las]) continue; if((i-1)%4>1) mvh(i); else mvz(i); sta[++top]=i-1+'A'; dfs(now+1,i); sta[top--]=' '; if((fan[i]-1)%4>1) mvh(fan[i]); else mvz(fan[i]); } } void clear(){ dp=0; fl=false; } int main(){ while(1){ clear(); scanf("%d",&st[1][3]); //cout<<"aa "<<endl; if(st[1][3]==0) break; scanf("%d",&st[1][5]); scanf("%d%d",&st[2][3],&st[2][5]); for(int i=1;i<=7;i++) scanf("%d",&st[3][i]); scanf("%d%d",&st[4][3],&st[4][5]); for(int i=1;i<=7;i++) scanf("%d",&st[5][i]); scanf("%d%d",&st[6][3],&st[6][5]); scanf("%d%d",&st[7][3],&st[7][5]); memcpy(mp,st,sizeof st); if(che()==0){ printf("No moves needed "); printf("%d ",fin()); continue; } fl=false; while(!fl){ dp++; memcpy(mp,st,sizeof st); dfs(1,0); } printf("%s ",ans+1); printf("%d ",num); } return 0; }
骑士精神
也许可以折半爆搜。
但是显然不够漂亮。
明显“超15步-1”，就迭代加深了。
估价函数：每次，骑士最多归位一个。如果算上最后一步的空格，可能归位2个。
所以，当前和终止的差距-1大于剩余步数的话，一定不行。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=6; int T; char st[6][6]; int dp; bool fl; int nd[6][6]={ {0,0,0,0,0,0}, {0,1,1,1,1,1}, {0,0,1,1,1,1}, {0,0,0,2,1,1}, {0,0,0,0,0,1}, {0,0,0,0,0,0} }; int mp[6][6]; int mv[8][2]={{-1,+2},{-1,-2},{-2,+1},{-2,-1},{+1,+2},{+1,-2},{+2,-1},{+2,+1}}; int che(int re){ int dif=0; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ dif+=(mp[i][j]!=nd[i][j]); } } if(dif==0) return 2; return dp-re+1>=dif-1; } void dfs(int now,int x,int y){ if(!che(now)) return; if(fl) return; if(now==dp+1){ if(che(now)==2) { fl=true;return; } } for(int i=0;i<8;i++){ int dx=x+mv[i][0],dy=y+mv[i][1]; if(dx<1||dx>5) continue; if(dy<1||dy>5) continue; swap(mp[x][y],mp[dx][dy]); dfs(now+1,dx,dy); swap(mp[x][y],mp[dx][dy]); } } void clear(){ fl=false;dp=0; } int main(){ scanf("%d",&T); while(T--){ clear(); int sx,sy; for(int i=1;i<=5;i++){ scanf("%s",st[i]+1); for(int j=1;j<=5;j++){ if(isdigit(st[i][j]))mp[i][j]=st[i][j]-'0'; else { mp[i][j]=2;sx=i,sy=j; } } } fl=false; for(dp=0;dp<=15;dp++){ dfs(1,sx,sy); if(fl) break; } if(fl) printf("%d ",dp); else printf("-1 "); } return 0; }