DFS大楼

admin

DFS是信息学奥赛的重要内容，学好DFS是进入中级选手的标记，DFS的题目主要涉及数学建模，状态标识，规则转换，程序优化等方面
1、入门题目                              
      12345五个数字选出三个组成一个三位数，这样的三位数有多少个。    基本pmn
      ABCDE五个字母组成的长度为三的字符串，有多少个                      位置转换
      AAABBCDE中选出3个字母组成字符串有多少个                              有重排列
      ABCDE中选出3个人去参加比赛，有多少种方法                              组合的生成
     练习题：
     P1706 全排列问题  http://www.hsyit.cn/forum.php?mo ... 5875&extra=page%3D1
     P1157 组合的输出  http://www.hsyit.cn/forum.php?mo ... 5874&extra=page%3D1
     P1691 有重复元素的排列问题  http://www.hsyit.cn/forum.php?mo ... 5876&extra=page%3D1
     P1036 选数  http://www.hsyit.cn/forum.php?mo ... 5881&extra=page%3D1

2、基本变形  包括选择约束，位置跳过，深度可变，极值记忆、剪枝等
     123456789排成一排，相邻的两个数字之和为质数，有多少种方法，排成一个环呢  有约束条件的pmn     
     11223344八个数字排成一排，要求i和i之间隔i个位置，如何摆放？                       位置上有约束
     1*2的骨牌去覆盖4*4 的格子，有多少种方法                                                    平面约束
     1-9九个数字放在3*3的方格里，相邻的数字之和为质数，怎么放？所谓相邻，指左右上下的数字
     m个物品在一定的约束条件下怎么选才能使总和最大                                          背包问题     

     100分成6个数的和     http://www.hsyit.cn/forum.php?mod=viewthread&tid=24
     P2404 自然数的拆分问题  http://hsyit.cn/forum.php?mod=viewthread&tid=35927
     P1049 装箱问题 http://hsyit.cn/forum.php?mod=viewthread&tid=36213
     P1443 马的遍历  http://www.hsyit.cn/forum.php?mo ... 5886&extra=page%3D1   
     P1238 走迷宫  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35919
     P1060 开心的金明  http://www.hsyit.cn/forum.php?mo ... 5890&extra=page%3D1
     P1123 取数游戏  http://www.hsyit.cn/forum.php?mo ... 5882&extra=page%3D1
     2^n最少要算多少次乘法  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3663&highlight=2
     P1784 数独   http://www.hsyit.cn/forum.php?mo ... 5788&highlight=1784
     P1019 单词接龙 http://www.hsyit.cn/forum.php?mod=viewthread&tid=35880
     P1101 单词方阵 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36006
     P2819 图的m着色问题 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36045  
     P1692 部落卫队  http://hsyit.cn/forum.php?mod=viewthread&tid=36396

     
3、技巧   

    P1473 零的数列 Zero Sum   http://www.hsyit.cn/forum.php?mod=viewthread&tid=35991        
    1-m之间那个数字的约数最多，若相同，输出最小的那个  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35845
    P1254 扇区填数 http://www.hsyit.cn/forum.php?mo ... 5884&extra=page%3D1        
    P1731 [NOI1999]生日蛋糕 http://www.hsyit.cn/forum.php?mo ... hlight=%C9%FA%C8%D5  
    智慧珠游戏    http://www.hsyit.cn/forum.php?mo ... 5879&extra=page%3D1
    P1139 单向双轨道  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35924   
    P1092 虫食算  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36035
    P1021 邮票面值设计 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36036
    P2668 斗地主 http://www.hsyit.cn/forum.php?mod=viewthread&tid=35889
    IOI'94 汽车问题  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36358
    P3956 棋盘 http://hsyit.cn/forum.php?mod=viewthread&tid=36320

4、迭代加深的技术
    埃及分数    http://www.hsyit.cn/forum.php?mod=viewthread&tid=35932
    UVA1343 The Rotation Game  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35933                  
    P2324 [SCOI2005]骑士精神 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36013
    poj2870Light Up  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35934
    解集个数  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36355


5、进阶
     P1514 引水入城  http://hsyit.cn/forum.php?mod=viewthread&tid=36397
     P1139 单向双轨道 http://www.hsyit.cn/forum.php?mod=viewthread&tid=35924
     还是N皇后 http://www.hsyit.cn/forum.php?mod=viewthread&tid=35992            
     P1363 幻想迷宫     http://www.hsyit.cn/forum.php?mod=viewthread&tid=35987
    加强版的数独

朱品屹

admin 发表于 2020-3-2 13:04
1657 选书值得一做

1. #include<iostream>
   
2. using namespace std;
   
3. int a[50],ans=0,x,t1,t2;;
   
4. bool b[50],like[50][50];//like[i][j]表示第i个人喜欢第j本书。
   
5. void dfs(int i)
   
6. {
   
7.         if(i>x) ans++;
   
8.         else
   
9.         {
   
10.                 for(int k=1;k<=x;k++)
    
11.                 {
    
12.                         if(b[k]&&like[i][k])//此书未选且第i个人喜欢这本书
    
13.                         {
    
14.                                 a[i]=k;  //a数组如果不用输出可以不要
    
15.                                 b[k]=0;
    
16.                                 dfs(i+1);
    
17.                                 b[k]=1;
    
18.                         }
    
19.                 }
    
20.         }
    
21. }
    
22. int main()
    
23. {
    
24.         cin>>x;
    
25.         if(x==0) cout<<0;  //这里要特判一下
    
26.         else
    
27.         {
    
28.                 for(int i=1;i<=x;i++)
    
29.                 {
    
30.                         cin>>t1>>t2;
    
31.                         like[i][t1]=1;
    
32.                         like[i][t2]=1;
    
33.                 }
    
34.                 for(int i=1;i<=x;i++)
    
35.                         b[i]=1;
    
36.                 dfs(1);
    
37.                 cout<<ans;
    
38.         }
    
39.         return 0;
    
40. }

复制代码

admin

1657 选书值得一做

张溯源

孙老师果然真是牛逼
献上关于组合的代码：

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. int n,r;
   
5. int a[23];
   
6. bool b[23]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
   
7. void pr()
   
8. {
   
9.         for(int i=1;i<=r;i++)
   
10.                 printf("%3d",a[i]);
    
11.         cout<<endl;
    
12. }
    
13. void pmn(int i)
    
14. {
    
15.         if(i>r)
    
16.                 pr();
    
17.         else
    
18.         {
    
19.                 for(int h=a[i-1]+1;h<=n;h++)
    
20.                         if(b[h]==1)
    
21.                         {
    
22.                                 b[h]=0;
    
23.                                 a[i]=h;
    
24.                                 pmn(i+1);
    
25.                                 b[h]=1;
    
26.                         }
    
27.         }
    
28. }
    
29. int main()
    
30. {
    
31.         cin>>n>>r;
    
32.         pmn(1);
    
33.         return 0;
    
34. }

复制代码

admin

标准的5选3

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=10;
   
4. int a[mm];/// 选出来的
   
5. int b[mm];  ///是否被选择
   
6. int m,n,j;
   
7. void pp()
   
8. {
   
9.     for (int i=1; i<=n; i++) cout<<a[i]<<' ' ;
   
10.     cout<<endl;
    
11. }
    
12. void dfs(int i)
    
13. {
    
14.     if (i>n) pp();
    
15.     else for (int j=1; j<=m; j++)
    
16.             if (b[j])
    
17.             {
    
18.                 a[i]=j;
    
19.                 b[j]=0;
    
20.                 dfs(i+1);
    
21.                 b[j]=1;
    
22.             }
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.     m=5,n=3;
    
28.     b[1]=b[2]=b[3]=b[4]=b[5]=1;
    
29.     dfs(1);
    
30.     return 0;
    
31. }

复制代码

admin

间隔排列：

1. #include <iostream>
   
2. using namespace std;
   
3. const int mm=18;
   
4. bool b[mm];
   
5. int a[mm*2];
   
6. int n=4;
   
7. void dfs(int i)
   
8. {
   
9.     int j,k;
   
10.     if (i>n*2)  ///摆放完毕，输出
    
11.     {
    
12.         for(j=1; j<=n*2; j++) cout<<a[j]<<' ';
    
13.         cout<<endl;
    
14.     }
    
15.     else if (a[i]>0) dfs(i+1);  ///！！！这个格子已经被预先摆放了
    
16.     for (k=1; k<=n; k++)  
    
17.     {
    
18.         int x=i+k+1; ///计算那一个格子的位置
    
19.         bool b1=(x<=2*n); ///不可以超出范围
    
20.         bool b2=(a[x]==0);///不可以被占用
    
21. 
    
22.         bool bb=b[k] && b1 && b2;
    
23.         if (bb)
    
24.         {
    
25.             a[i]=a[x]=k;
    
26.             b[k]=0;
    
27.             dfs(i+1);
    
28.             b[k]=1;
    
29.             a[i]=a[x]=0;
    
30.         }
    
31.     }
    
32. 
    
33. }
    
34. int main()
    
35. {
    
36.     for (int i=1; i<=n; i++) b[i]=1;
    
37.     dfs(1);
    
38. 
    
39.     return 0;
    
40. }
    

复制代码

admin

一个问题要是需要用DFS来解决的话，首先的考虑几个问题，以M个数字里面选N个为例，这个是最基本的：
1、搜索的对象是谁。这里是N个位置上的数字，也就是说dfs(i)中i表示第i个位置，a(i)=k表示第i个位置上放的数字是k。
2、规则是什么样的，也就是for循环里面的那个k的变化情况，这里就是1到M，和上面一样，简化了嘛！
3、约束条件是什么，就是for循环里面的那个if，这里就是说选过的不能再选，所以需要一个bool数组；
4、终止条件是什么，就是进入函数的那个if，这里就是N个位置上的数字已经选完，开始选第N+1个位置，所以是i>=N+1
这四个问题都想清楚了，套格式就是程序。

再看一个难一点的间隔排列：假设有8个数字，11223344
1、搜索的对象是谁。这里是8个位置，每个位置上的数字，注意：不是4而是8。a(i)=k表示第i个位置上放数字k而不是数字i放在k位置上！！！！
2、规则是什么样的，也就是for循环里面的那个k的变化情况，这里就是1到4，也要注意！但是比上面那题多了一点，放过了的直接跳过去。所以多了一个if
3、约束条件是什么，就是for循环里面的那个if，这里就比较多了，1选过的不能再选，2要能保证两个数码都能放得下去。所以比较复杂。
4、终止条件是什么，就是进入函数的那个if，这里就是8个位置已经选完，所以是i>=9

对比下楼下的这两个程序

admin

简单的DFS一般有两种框架，我喜欢用第一种

1. void dfs(int i)
   
2. {
   
3.         if (i>=N+1) /// 到达深度终点
   
4.                 pp() ///输出或者判断
   
5.         else
   
6.                         for (int k=1; k<=M; k++) ///循环使用M条规则
   
7.                                 if (b)  ///若可行
   
8.                                         {
   
9.                                                 a[i]=k; ///记录这个决策
   
10.                                                 B[x]=0; ///相应的约束条件变化
    
11.                                                 dfs(i+1); ///递归下一个
    
12.                                                 B[x]=1; ///还原相应的约束条件
    
13.                                         }
    
14. 
    
15. }

复制代码

也有人把这个终点判断放在for循环里面，这似乎不是很要紧

1. viod dfs(int i)
   
2. {
   
3.     for (int k=1; k<=M; k++) ///循环使用M条规则
   
4.                 if (b)  ///若可行
   
5.                         {
   
6.                                 a[i]=k; ///记录这个决策
   
7.                                 B[x]=0; ///相应的约束条件变化
   
8.                                 if (i<N) dfs(i+1); ///递归下一个
   
9.                                 else pp();
   
10.                                 B[x]=1; ///还原相应的约束条件
    
11.                         }
    
12. 
    
13. }

复制代码

admin

一个问题要是需要用DFS来解决的话，首先的考虑几个问题，以M个数字里面选N个为例，这个是最基本的：
1、待选的对象是谁。这里是M个数字
2、规则是什么样的，也就是for循环里面的那个k的变化情况，这里就是1到M，和上面一样，简化了嘛！
3、约束条件是什么，就是for循环里面的那个if，这里就是说选过的不能再选，所以需要一个bool数组；
4、终止条件是什么，就是进入函数的那个if，这里就是N个数字已经选完，开始选第N+1个数字，所以是i>=N+1
这四个问题都想清楚了，套格式就是程序。