2.9.2 1117. 单词接龙
代码：
#include<bits/stdc++.h> using namespace std; const int N=50; string str[N],start; int n; bool st[N]; int ans; bool judge(string s) { for(int i=0;i<2*n;i++) { int _min=min(s.length(),str[i].length()); for(int len=1;len<_min;len++) { if(s.substr(s.length()-len)==str[i].substr(0,len)&&st[i]==false) { return true; } } } return false; } void dfs(string s) { if(judge(s)) { string tmp=""; for(int i=0;i<2*n;i++) { int _min=min(s.length(),str[i].length()); for(int len=1;len<_min;len++) { if(s.substr(s.length()-len)==str[i].substr(0,len)&&st[i]==false) { st[i]=true; tmp=s+str[i].substr(len); dfs(tmp); st[i]=false; } } } } else { ans=max(ans,(int)s.length()); return; } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>str[i]; for(int i=n;i<2*n;i++) str[i]=str[i-n]; cin>>start; string s="#"+start; dfs(s); cout<<ans-1<<endl; return 0; }
2.9.3 1118. 分成互质组
代码：
#include<bits/stdc++.h> using namespace std; const int N=11; int n; int p[N]; int group[N][N]; bool st[N]; int ans=N; //g：第几组；gc：当前组内下标是什么； //tc：当前组中共有多少元素；start：当前组可以从哪个下标开始搜 int gcd(int a,int b) { return b?gcd(b,a%b):a; } bool check(int group[],int gc,int i) { for(int j=0;j<gc;j++) { if(gcd(p[group[j]],p[i])>1) return false; } return true; } void dfs(int g,int gc,int tc,int start) { if(g>=ans) return; if(tc==n) ans=g; bool flag=true; for(int i=start;i<n;i++) { if(!st[i]&&check(group[g],gc,i)) { st[i]=true; group[g][gc]=i; dfs(g,gc+1,tc+1,i+1); st[i]=false; flag=false; } } if(flag) dfs(g+1,0,tc,0); } int main() { cin>>n; for(int i=0;i<n;i++) cin>>p[i]; dfs(1,0,0,0); cout<<ans; return 0; }
2.10 DFS之剪枝与优化
2.10.1 165. 小猫爬山
代码：
#include<bits/stdc++.h> using namespace std; const int N=25; int n,w; int cat[N]; int sum[N]; bool st[N]; int ans=N; bool cmp(int a,int b) { return a>b; } void dfs(int u,int k) { if(k>=ans) return; if(u==n) { ans=k; return; } for(int i=0;i<k;i++) { if(cat[u]+sum[i]<=w) { sum[i]+=cat[u]; dfs(u+1,k); sum[i]-=cat[u]; } } sum[k]=cat[u]; dfs(u+1,k+1); sum[k]=0; } int main() { cin>>n>>w; for(int i=0;i<n;i++) cin>>cat[i]; sort(cat,cat+n,cmp); dfs(0,0); cout<<ans; return 0; }
2.10.2 166. 数独
代码：
#include<bits/stdc++.h> using namespace std; const int N=9; char str[100]; int ones[1<<N],mp[1<<N]; int row[N],col[N],cell[3][3]; inline int lowbit(int x) { return x&-x; } void init() { for(int i=0;i<N;i++) { row[i]=(1<<N)-1; col[i]=(1<<N)-1; } for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { cell[i][j]=(1<<N)-1; } } } inline int get(int x,int y) { return row[x]&col[y]&cell[x/3][y/3]; } bool bfs(int cnt) { if(cnt==0) return true; int x,y,minv=10; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(str[i*N+j]=='.') { int t=ones[get(i,j)]; if(t<minv) { x=i,y=j,minv=t; } } } } int t=get(x,y); for(;t!=0;t-=lowbit(t)) { int n=mp[lowbit(t)]; row[x]-=1<<n; col[y]-=1<<n; cell[x/3][y/3]-=1<<n; str[x*N+y]='1'+n; if(bfs(cnt-1)) return true; row[x]+=1<<n; col[y]+=1<<n; cell[x/3][y/3]+=1<<n; str[x*N+y]='.'; } return false; } int main() { for(int i=0;i<N;i++) mp[1<<i]=i; for(int i=0;i<(1<<N);i++) { int s=0; for(int j=i;j;j-=lowbit(j)) s++; ones[i]=s; } while(true) { init(); cin>>str; if(str[0]=='e') break; int cnt=0; for(int i=0,k=0;i<N;i++) { for(int j=0;j<N;j++,k++) { if(str[k]!='.') { int t=str[k]-'1'; row[i]-=1<<t; col[j]-=1<<t; cell[i/3][j/3]-=1<<t; } else cnt++; } } bfs(cnt); cout<<str<<endl; } return 0; }
2.10.3 167. 木棒
代码：
#include<bits/stdc++.h> using namespace std; const int N=70; int sticks[N]; bool st[N]; int n; int sum,length; bool dfs(int u,int cur,int start) { if(u*length==sum) return true; if(cur==length) return dfs(u+1,0,0); for(int i=start;i<n;i++) { int l=sticks[i]; if(st[i]||cur+l>length) continue; st[i]=true; if(dfs(u,cur+l,i+1)) return true; st[i]=false; if(!cur||cur+l==length) return false; int j=i; while(j<n&&sticks[j]==sticks[i]) j++; i=j-1; } return false; } int main() { while(true) { fill(st,st+N,false); sum=0,length=0; cin>>n; if(n==0) break; for(int i=0;i<n;i++) { cin>>sticks[i]; sum+=sticks[i]; length=max(length,sticks[i]); } sort(sticks,sticks+n); reverse(sticks,sticks+n); while(length<=sum) { if(sum%length==0&&dfs(0,0,0)) { cout<<length<<endl; break; } length++; } } return 0; }
2.10.4 168. 生日蛋糕
代码：
#include<bits/stdc++.h> using namespace std; const int N=25,INF=1e9; int n,m; int minv[N],mins[N]; int R[N],H[N]; int ans=INF; void dfs(int u,int v,int s) { if(v+minv[u]>n) return; if(s+mins[u]>=ans) return; if(s+2*(n-v)/R[u+1]>=ans) return; if(!u) { if(v==n) ans=s; return; } for(int r=min(R[u+1]-1,(int)sqrt(n-v));r>=u;r--) { for(int h=min(H[u+1]-1,(n-v)/r/r);h>=u;h--) { int t=0; if(u==m) t=r*r; R[u]=r,H[u]=h; dfs(u-1,v+r*r*h,s+2*r*h+t); } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { minv[i]=minv[i-1]+i*i*i; mins[i]=mins[i-1]+2*i*i; } R[m+1]=H[m+1]=INF; dfs(m,0,0); if(ans==INF) cout<<0<<endl; else cout<<ans<<endl; return 0; }
2.11 迭代加深
2.11.1 170. 加成序列
代码：
#include<bits/stdc++.h> using namespace std; const int N=110; int n; int path[N]; bool dfs(int u,int depth) { if(u==depth) return path[u-1]==n; bool st[N]={false}; for(int i=u-1;i>=0;i--) { for(int j=i;j>=0;j--) { int s=path[i]+path[j]; if(s>path[u-1]&&s<=n&&!st[s]) { st[s]=true; path[u]=s; if(dfs(u+1,depth)) return true; } } } return false; } int main() { while(true) { cin>>n; if(n==0) break; int depth=1; path[0]=1; while(!dfs(1,depth)) depth++; for(int i=0;i<depth;i++) { cout<<path[i]<<" "; } cout<<endl; } return 0; }
2.12 双向DFS
2.12.1 171. 送礼物
代码：
#include<bits/stdc++.h> using namespace std; const int N=50; typedef long long LL; int n,m,k; int g[N]; int weights[1<<24],cnt; int ans; void dfs_1(int u,int s) { if(u==k) { weights[cnt++]=s; return; } if((LL)s+g[u]<=m) dfs_1(u+1,s+g[u]); dfs_1(u+1,s); } void dfs_2(int u,int s) { if(u==n) { int l=0,r=cnt-1; while(l<r) { int mid=l+r+1>>1; if((LL)weights[mid]+s<=m) l=mid; else r=mid-1; } if(weights[r]+s<=m) ans=max(ans,weights[r]+s); return; } if((LL)s+g[u]<=m) dfs_2(u+1,s+g[u]); dfs_2(u+1,s); } int main() { cin>>m>>n; for(int i=0;i<n;i++) cin>>g[i]; sort(g,g+n); reverse(g,g+n); k=n/2+2; dfs_1(0,0); sort(weights,weights+cnt); cnt=unique(weights,weights+cnt)-weights; dfs_2(k,0); cout<<ans; return 0; }
2.13 IDA*
2.13.1 180. 排书
代码：
#include<bits/stdc++.h> using namespace std; const int N=15; int n; int q[N]; int w[5][N]; int f() { int tot=0; for(int i=0;i+1<n;i++) { if(q[i+1]!=q[i]+1) tot++; } return (tot+2)/3; } bool check() { for(int i=0;i<n;i++) { if(q[i]!=i+1) return false; } return true; } bool dfs(int depth,int max_depth) { if(depth+f()>max_depth) return false; if(check()) return true; for(int len=1;len<=n;len++) { for(int l=0;l+len-1<n;l++) { int r=l+len-1; for(int k=r+1;k<n;k++) { memcpy(w[depth],q,sizeof q); int x,y; for(x=r+1,y=l;x<=k;x++,y++) { q[y]=w[depth][x]; } for(x=l;x<=r;x++,y++) { q[y]=w[depth][x]; } if(dfs(depth+1,max_depth)) return true; memcpy(q,w[depth],sizeof q); } } } return false; } int main() { int T; cin>>T; while(T--) { cin>>n; for(int i=0;i<n;i++) cin>>q[i]; int depth=0; while(depth<5&&!dfs(0,depth)) depth++; if(depth>=5) cout<<"5 or more"<<endl; else cout<<depth<<endl; } return 0; }
2.13.2 181. 回转游戏
代码：
#include<bits/stdc++.h> using namespace std; const int N=24; int op[8][7]={ {0,2,6,11,15,20,22}, {1,3,8,12,17,21,23}, {10,9,8,7,6,5,4}, {19,18,17,16,15,14,13}, {23,21,17,12,8,3,1}, {22,20,15,11,6,2,0}, {13,14,15,16,17,18,19}, {4,5,6,7,8,9,10} }; int oppsite[8]={5,4,7,6,1,0,3,2}; int center[8]={6,7,8,11,12,15,16,17}; int q[N]; int path[100]; int sum[4]; int f() { fill(sum,sum+4,0); for(int i=0;i<8;i++) sum[q[center[i]]]++; int k=0; for(int i=1;i<=3;i++) { k=max(k,sum[i]); } return 8-k; } void operate(int x) { int t=q[op[x][0]]; for(int i=1;i<7;i++) { q[op[x][i-1]]=q[op[x][i]]; } q[op[x][6]]=t; } bool dfs(int depth,int max_depth,int last) { if(depth+f()>max_depth) return false; if(f()==0) return true; for(int i=0;i<8;i++) { if(oppsite[i]==last) continue; operate(i); path[depth]=i; if(dfs(depth+1,max_depth,i)) return true; operate(oppsite[i]); } return false; } int main() { while(scanf("%d",&q[0]),q[0]) { for(int i=1;i<N;i++) { scanf("%d",&q[i]); } int depth=0; while(!dfs(0,depth,-1)) depth++; if(!depth) puts("No moves needed"); else { for(int i=0;i<depth;i++) { printf("%c",path[i]+'A'); } puts(""); } printf("%d\n",q[6]); } return 0; }
