行业知识
郑州大学2024年寒假训练 Day4：DFS & 图DFS （A-J）
���搜！让人又爱又恨的爆搜它来了！爆搜和大模拟是敲起来最掉头发的题了吧。
（）DFS（Deep First Search）也就是深度优先搜索，它是一种搜索方式。不过爆搜题基本上都是使用DFS的方式来搜索的，所以DFS基本上就被打上了爆搜的标签。图DFS顾名思义就是在图上进行深度优先搜索。
和BFS（Breath First Search）也就是广度优先搜索的不同之处在于，BFS在面对一个状态或者说局面的时候，是先把它所有的下一个状态都列出来，然后再按顺序一个一个看，一层一层搜索。DFS是随便找一个直接向下走，直到走到边界才回来。所以BFS可以找到深度最浅的边界（也就是最短路），而DFS则是一个一个寻找。在边界普遍很深的时候，BFS必须把所有情况都搜索到，还需要存储每一个搜索路径，而DFS可以通过提前判断这个搜索路径是否合理从而提前跳出不合理的搜索路径，同时只需要存储一个搜索路径即可。
（）由于DFS是一个一个来到达边界的，到达边界时它的搜索路径就是一个问题可行的解。因为大部分搜索都只找到一个可行的或者最优的就行了，所以搜索策略也很有讲究，好的搜索策略（或者说 剪枝策略）能更快找到可行解。其实人解决问题时大多数时候也相当于深度优先搜索，而且是有着相当优秀剪枝策略的深度优先搜索。比如做题时你觉得好像做过，就会模仿上次的做法，化简式子时优先向着一些公式的方向化简等等。
剪枝方法一般有以下几种：
- 优化搜索顺序
- 排除等效冗余
- 可行性剪枝
- 最优性剪枝
- 记忆化搜索
除开这些剪枝方式，还有一些高明的搜索方法，比如迭代加深搜索（先约定最大搜索深度，然后对这个深度以内进行搜索），启发式搜索（优先选择更有可能到达可行或最优解的方向搜索），双向DFS（从搜索的起点和终点分别搜索，有点像我们做数学题时分别从条件正推和从答案逆推，只要中间有交集就可以证明了）等等。
剪枝爆搜有很多经典题目，剪一天，剪到哭，比如：拼木棍，生日蛋糕，16*16数独，八皇后
A
洛谷 P1036 [NOIP2002 普及组] 选数
思路：
由于每个数都给出了编号，第 i i i 个位置上是 x i x_i xi，所以显然对一对相同的数，位置不同的组合也算不同的。而两个组合中编号对应相同的话就是相同的组合了。
由于题目是要统计，所以一定需要把所有可能的情况都搜索到，所以用不到剪枝策略。不过为了防止重复搜索相同情况，需要排除等效冗余，具体来说，我们从前向后枚举每个位置，不走回头路，这样选一遍下来，选中位置的编号是递增的，这样就保证了不会搜索到相同的组合了。
不过搜索到达边界后需要判断素数，直接暴力开方枚举因数的话时间复杂度大概是 O ( C n k ∗ t ) O(C_n^k*\sqrt{t}) O(Cnk∗t ) ， C n k C_n^k Cnk 最坏情况下是 3 ∗ 1 0 7 3*10^7 3∗107 的， t \sqrt t t 最坏情况下是 1 0 4 10^4 104，估计会超时。所以需要用素数筛预先筛出 1 0 8 10^8 108 以内的所有素数，之后根据标记数组判断一个数是不是素数就行了。
code：
（保险，prime数组开的 1 0 7 10^7 107 大小， n n n 以内素数的个数大概有 n l n n \dfrac n {ln\, n} lnnn 个）
#include #include using namespace std;const int maxn=1e7+5;bool vis[maxn*10];int prime[maxn],cnt;void Eular(int n){vis[1]=true;for(int i=2;iif(!vis[i])prime[++cnt]=i;for(int j=1,p=prime[1];i*pvis[i*p]=true;if(i%p==0)break;}}}int n,k,a[maxn],ans;void dfs(int x,int num,int tot){if(num==k){if(!vis[tot])ans++;return;}if(xn)return;dfs(x+1,num+1,tot+a[x]);dfs(x+1,num,tot);}int main(){Eular(1e8);cinn>>k;for(int i=1;i>a[i];dfs(1,0,0);cout//尝试第line行 if(linen){++cnt;if(cntfor(int i=1;iif(col[i] || dia1[line+i] || dia2[n+line-i])continue;col[i]=dia1[line+i]=dia2[n+line-i]=true;a[line]=i;dfs(line+1);col[i]=dia1[line+i]=dia2[n+line-i]=false;}}int main(){cinn;dfs(1);printf("%d",cnt);return 0;}//检查局面是否成立 int x=a[1]*100+a[2]*10+a[3],y=a[4]*100+a[5]*10+a[6],z=a[7]*100+a[8]*10+a[9];return (x*3==z*1 && x*2==y*1);}void print(){for(int i=1;iprintf("%d",a[i]);if(i%3==0)printf(" ");}puts("");}void dfs(int x){//尝试放第x个位置 if(xn){if(check())print();return;}for(int i=1;iif(!vis[i]){a[x]=i;vis[i]=true;dfs(x+1);vis[i]=false;}}}int main(){n=9;dfs(1);return 0;} //尝试放第x个位置 if(xn){for(int i=1;iif(!vis[i]){a[x]=i;vis[i]=true;dfs(x+1);vis[i]=false;}}}int main(){cinn;dfs(1);return 0;} //检查局面是否成立 int x=a[1]*100+a[2]*10+a[3],y=a[4]*100+a[5]*10+a[6],z=a[7]*100+a[8]*10+a[9];return (x*C==z*A && x*B==y*A);}void print(){for(int i=1;iprintf("%d",a[i]);if(i%3==0)printf(" ");}puts("");}void dfs(int x){//尝试放第x个位置 if(xn){if(check()){print();flag=true;}return;}for(int i=1;iif(!vis[i]){a[x]=i;vis[i]=true;dfs(x+1);vis[i]=false;}}}int main(){n=9;cinA>B>>C;dfs(1);if(!flag)printf("No!!!");return 0;} F
洛谷 P1120 小木棍
思路：
拼木棍！260ms加上n=65的极限数据造就了这么一个剪枝大题。需要考虑到很多剪枝策略才能把时间降到260ms以内。
在写剪枝之前最好先把普通的爆搜版本写出来，不然爆搜和一些剪枝策略同时写很有可能写出bug，然后调到怀疑人生。
因为拼出来的木棍需要用上所有的小木棍，所以拼出来的总长度就是小木棍长度之和 t o t tot tot，至少可以拼出一个长木棍。因为拼出来的每个木棍的长度是一样的，所以拼出来的木棍的长度应该是总长度的约数，而要找最小长度，可以先把所有所有约数处理出来并排序然后从小到大枚举并检查是否可行。
普通的爆搜策略比较好想，假如现在要求每个木棍的长度为 l e n len len，有两种搜索方法，一种是枚举小木棒，然后尝试拼到第 x x x 个木棒上，一种是枚举木棒，尝试拼入第 x x x 个小木棒。由于后者容易考虑到更多重复情况，不好优化，所以选择前者来搜索。
假设现在在拼第 x x x 个木棒，剩下 r e s t rest rest 长度要拼，那么枚举可行的没有被选上的木棒拼入，向下搜索。直到搜索到要拼第 t o t / l e n + 1 tot/len+1 tot/len+1 根木棍说明已经拼好了 t o t / l e n tot/len tot/len 根木棍，这时说明这个长度有解。直接输出并退出程序。所以一个简单的爆搜就写好了。
#include #include #include using namespace std;const int maxn=105;const int maxm=5005;int n,a[maxn],tot;int Length[maxm],counter;int len;bool vis[maxn];void add(int x,int rest){//尝试拼第x根木棍 一根木棍长为len if(!rest){add(x+1,len);return;}if(x*len>tot){printf("%d",len);exit(0);}for(int i=1;iif(!vis[i] && a[i]vis[i]=true;add(x,rest-a[i]);vis[i]=false;}}}int main(){cinn;for(int i=1;i>a[i],tot+=a[i];sort(a+1,a+n+1,greater());for(int i=1;i*iLength[++counter]=i;if(i*i!=tot)Length[++counter]=tot/i;}sort(Length+1,Length+counter+1);for(int i=1;ilen=Length[i];//可能的长度add(1,len);}return 0;}//尝试拼第x根木棍 上一个木棍编号 剩余没拼长度 if(rest==0){add(x+1,0,len);return;}if(x*len==tot){//剪枝5printf("%d",len);exit(0);}//lower_bound(a+lst+1,a+n+1,rest,[](int element, int value)-bool{return element value;})-a//从[lst+1,n+1)区间二分查找第一个小于等于rest的元素for(int i=lower_bound(a+lst+1,a+n+1,rest,[](int element, int value)->bool{return element > value;})-a //剪枝2：前面的木棒已经尝试拼接过了，从lst后面直接开始 ;i//剪枝3：同种长度不成功,从nxt开始 if(!vis[i]){vis[i]=true;add(x,i,rest-a[i]);vis[i]=false;if(rest==len)return;//剪枝6：a[i]作为第一根拼的木棒还会失败，之后就不可能成功 if(a[i]==rest)return;//剪枝7：长度正好为rest的木棍失败，之后一定不可能成功 }}}int main(){cin>n;for(int i=1;i>a[i],tot+=a[i];sort(a+1,a+n+1,greater());//剪枝1for(int i=n,lst=n+1;i>=1;i--){if(a[i]!=a[i+1])lst=i+1;nxt[i]=lst;//直接指向下一个不同长度的木棍，跳过中间相同长度的木棍}for(int i=1;i*iLength[++counter]=i;if(i*i!=tot)Length[++counter]=tot/i;}sort(Length+1,Length+counter+1);//剪枝4：从最长的小木棍开始枚举长度for(int i=lower_bound(Length+1,Length+counter+1,a[1])-Length;ilen=Length[i];//可能的长度add(1,0,len);}return 0;}g[u].push_back(v);g[v].push_back(u);}void dfs(int u,int rt){printf("%d ",u);for(auto v:g[u]){if(v==rt)continue;dfs(v,u);printf("%d ",u);}return;}int main(){cinn;for(int i=1,u,v;icin>u>>v;add(u,v);}for(int i=1;ifor(int i=0;im1['0'+i]=i;m2[i]='0'+i;}for(int i=0;im1['A'+i]=10+i;m2[10+i]='A'+i;}cinn>a>>b;if(a.length()t=m1[a[i]]+((iif(vis[nxt[u]]){if(vis[nxt[u]]==color)ans=min(ans,num-idx[nxt[u]]+1);return;}else {vis[u]=color;idx[u]=num;dfs(nxt[u],num+1,color);return;}}int main(){cinn;for(int i=1;iint x;pairint a=0,b=0;mapif(x%10==y%10)b++;s1[x%10]++;x/=10;s2[y%10]++;y/=10;}for(auto t:s1)if(s2.find(t.first)!=s2.end())a+=min(s1[t.first],s2[t.first]);return make_pair(a,b);}int main(){while(cinn,n){cnt=0;for(int i=1,x,y,z;icinxy>>z;a[i].x=x;a[i].m=make_pair(y,z);} int cnt=0,lst;for(int i=1000;ibool f=true;for(int j=1;jauto x=comp(a[j].x,i);if(comp(a[j].x,i)!=a[j].m){f=false;break;}}if(f){cnt++;lst=i;if(cnt1)break;}}if(cnt==1)printf("%d\n",lst);else printf("Not sure\n");}}
