华师一附中OI组

标题: DFS大楼 [打印本页]
作者: admin    时间: 2018-5-10 17:39
标题: DFS大楼
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    时间: 2018-8-26 18:59
一个问题要是需要用DFS来解决的话，首先的考虑几个问题，以M个数字里面选N个为例，这个是最基本的：
1、待选的对象是谁。这里是M个数字
2、规则是什么样的，也就是for循环里面的那个k的变化情况，这里就是1到M，和上面一样，简化了嘛！
3、约束条件是什么，就是for循环里面的那个if，这里就是说选过的不能再选，所以需要一个bool数组；
4、终止条件是什么，就是进入函数的那个if，这里就是N个数字已经选完，开始选第N+1个数字，所以是i>=N+1
这四个问题都想清楚了，套格式就是程序。
作者: admin    时间: 2019-10-25 15:34
简单的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.                                         }

  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.                         }

  13. }
复制代码
作者: admin    时间: 2019-10-25 15:53
一个问题要是需要用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    时间: 2019-10-25 15:54
间隔排列：
  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);///不可以被占用

  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.     }

  33. }
  34. int main()
  35. {
  36.     for (int i=1; i<=n; i++) b[i]=1;
  37.     dfs(1);

  39.     return 0;
  40. }
复制代码
作者: admin    时间: 2019-10-25 15:56
标准的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. }

  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. }
复制代码
作者: 张溯源    时间: 2020-3-1 21:25
本帖最后由 张溯源 于 2020-3-1 21:27 编辑

孙老师果然真是牛逼
献上关于组合的代码：
  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    时间: 2020-3-2 13:04
1657 选书值得一做
作者: 朱品屹    时间: 2020-8-5 09:36
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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2