深度优先搜索算法（3）——习题简述（1）

2.3 DFS习题简述本节将给出以下题的题解P1036 选数P1434 滑雪P1141 01迷宫P1149 火柴棒等式代码仓库链接https://github.com/zhenghan123456/algotithm_programming在这里建议每道题都认真思考习题题解只是简单表明一下思路不会和例题一样具体2.3.1P1036 选数那么如何进行素性判断两种方法预处理出素数表动态分析每一个数预处理出素数表需要进行5 × 10 6 5\times 10^65×106次计算每次计算效率是O ( 1 ) O(1)O(1)当然这是使用了一些超纲算法之后的效率结果似乎可行不过因为算法超纲先考虑第二种算法我这样说话好像AI的答复啊哈哈第二种算法就是检验每一个数效率应该是O ( x ) O(\sqrt{x})O(x​)然后要枚举的数应该有C n k C_n^kCnk​个所以总的效率就是O ( C n k x ) O(C_n^k\sqrt{x})O(Cnk​x​)经计算可行。然后就是要枚举k kk个数。题目要求对n nn个数中取k kk个数求和也就是枚举所有大小为k kk的子集由此联想到子集枚举的方法——状态压缩当然这不是重点的方法如果感兴趣可以看代码仓库中2\problems\P1036_1.cpp还有一种方法就是使用DFS了枚举所有可能的子集。这里还有一个注意事项为了不枚举重复子集和重复数字如{ 1 , 2 , 3 } \{1,2,3\}{1,2,3}和{ 1 , 3 , 2 } \{1,3,2\}{1,3,2}这里采取“不降枚举”的策略也就是只枚举升序的子集。代码位置2\problems\P1036_2.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nconstintmaxn25;intx[maxn];intn,k;boolisprime(intn){if(n2)return0;if(n2)return1;if(!(n1))return0;for(inti3;i*in;i2){if(!(n%i))return0;}return1;}intdfs(intdepth,intval,intsum){if(depthk)returnisprime(sum);intcnt0;_rep(i,val1,ndepth-k1)cntdfs(depth1,i,sumx[i]);returncnt;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinnk;_for(i,n)cinx[i];sort(x,xn);coutdfs(0,-1,0)endl;}2.3.2P1434 滑雪容易想到对于任何一个点不断往低处走不管是从那个点滑下来的能走的最远距离是相同的。由此想到了记忆化搜索也是DP思维。用一个DP数组存储每一个位置滑下来的最长距离思路就比较简单对于每一个格子往四个方向依次查找确定最小值因为路线具有单向性只能从高到低所以不需要vis数组记录走过的格子设计算法用dp[i][j]表示对应点滑下来的距离最大值往通过DFS往四个方向找到最短路径。每个点最终只被计算一次效率应该是O ( n 2 ) O(n^2)O(n2)可以接受代码位置2\problems\P1434.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nboolvis[105][105];inth[105][105];intdp[105][105];intdx[]{1,-1,0,0};intdy[]{0,0,1,-1};intr,c;intdfs(intx,inty){if(dp[x][y])returndp[x][y];intans1;_for(i,4){intnxxdx[i];intnyydy[i];if(nx0ny0nxrnych[nx][ny]h[x][y]){ansmax(ans,dfs(nx,ny)1);// 记得1}}returndp[x][y]ans;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinrc;intmaxlen0;_for(i,r)_for(j,c)cinh[i][j];_for(i,r)_for(j,c)maxlenmax(dfs(i,j),maxlen);coutmaxlenendl;}2.3.3P1141 01迷宫容易想到所有相通的块答案是相同的答案就是块的大小。那么如何找到块的大小呢这里给出的思路是用最上点的顶点来标记这个块中的所有点。这里是并查集的思想用树形结构来表示连通快。那么连通块的最上方的点就可以被记为根节点将连通块中所有其他点全部记为这个点的子节点这样就可以解出题了而存储子节点数组我选择使用vector这是因为效率比较高而且离卡常还比较远而如果每一个点都按照最大值存储的话会卡MLE所以使用vector是更好的选择。代码位置2\problems\P1141.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nconstintmaxn1010;boola[maxn][maxn];boolvis[maxn][maxn];intans[maxn][maxn];intdx[]{1,-1,0,0};intdy[]{0,0,1,-1};intn;#definepbpush_backstructpoint{intx,y;};structnode{point p;vectornode*child;}nodes[maxn][maxn];voiddfs(nodep,boolb,nodestart){if(vis[p.p.x][p.p.y])return;if(!(a[p.p.x][p.p.y]^b))return;vis[p.p.x][p.p.y]1;start.child.pb(p);// 添加节点_for(i,4){intxp.p.xdx[i];intyp.p.ydy[i];if(x0xny0yn)dfs(nodes[x][y],a[p.p.x][p.p.y],start);}}intmain(){ios::sync_with_stdio(0);cin.tie(0);intm;cinnm;_for(i,n)_for(j,n){nodes[i][j].p{i,j};charc;cinc;a[i][j]c-0;}_for(i,n)_for(j,n)dfs(nodes[i][j],!a[i][j],nodes[i][j]);_for(i,n)_for(j,n){intsznodes[i][j].child.size();for(autok:nodes[i][j].child){ans[k-p.x][k-p.y]sz;}}while(m--){inti,j;cinij;coutans[i-1][j-1]endl;}}2.4.4P1149 火柴棒等式这段代码就是一道枚举题枚举所有情况的两个加数和和然后判断是否满足条件2\problems\P1149_1.cpp当然这是DFS的文章因此当然要用DFS重写一遍代码了。对于迭代代码很多时候可以通过递归缩短代码而把算法把枚举改为“高级”一些的DFS代码代码位置2\problems\P1149_2.cpp#includebits/stdc.husingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti0;in;i)#define_rep(i,a,b)for(intia;ib;i)#defineendl\nintsticks[]{6,2,5,5,4,5,6,3,7,6};intn;intarr[3];intsticknum(intn){intres0;do{ressticks[n%10];n/10;}while(n);returnres;}intans0;// 可以使用循环代替voiddfs(intsum,intpos){if(sumn)return;// 剪枝if(pos3){ans((sumn)(arr[0]arr[1]arr[2]));return;}_for(i,1000){arr[pos]i;dfs(sumsticknum(i),pos1);}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinn;n-4;dfs(0,0);coutansendl;}