引言本篇记录搜索专题刷题包含 LeetCode 岛屿数量、NOIP 历年真题数的划分、单词接龙、产生数、方格填数、猫粮规划。涉及知识点DFS、BFS、回溯剪枝、Floyd 传递闭包、0‑1 背包、折半搜索 meet‑in‑middle200. 岛屿数量 - 力扣LeetCode✨✨涉及:DFSBFS解题过程:直接遍历整个格子 grid如果遇到‘1’代表发现一座新的岛屿岛屿计数使用DFS或者BFS把它这个连通的所有’1’全部替换成’0’(标记成已经访问过)直接把陆地变为水省的额外去开vis数组DFSclass Solution { private: int dx[4]{-1,1,0,0}; int dy[4]{0,0,-1,1}; void dfs(vectorvectorchar grid,int x,int y,int m,int n) { if(x0||xm||y0||yn||grid[x][y]0) { return ; } grid[x][y]0; for(int i0;i4;i) { int nextxxdx[i]; int nextyydy[i]; dfs(grid,nextx,nexty,m,n); } } public: int numIslands(vectorvectorchar grid) { int mgrid.size(); int ngrid[0].size(); int cnt0; for(int i0;im;i) { for(int j0;jn;j) { if(grid[i][j]1) { cnt; dfs(grid,i,j,m,n); } } } return cnt; } };BFSclass Solution { private: int dx[4]{-1,1,0,0}; int dy[4]{0,0,-1,1}; public: int numIslands(vectorvectorchar grid) { int mgrid.size(); int ngrid[0].size(); int cnt0; for(int i0;im;i) { for(int j0;jn;j) { if(grid[i][j]1) { cnt; queuepairint,intq; q.push({i,j}); grid[i][j]0; while(!q.empty()) { auto tq.front(); q.pop(); int xt.first; int yt.second; for(int k0;k4;k) { int nxxdx[k]; int nyydy[k]; if(nx0nxmny0nyngrid[nx][ny]1) { grid[nx][ny]0; q.push({nx,ny}); } } } } } } return cnt; } };[P1025NOIP 2001 提高组] 数的划分 - 洛谷✨涉及:DFS一个简单的DFS直接DFS去搜变量i、sumn和stepk#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n,k; ll ans0; void DFS(ll x,ll sum,ll step) { if(stepk) { if(sumn) { ans; } return ; } for(ll ix;sumin;i) { DFS(i,sumi,step1); } } int main() { IOS cinnk; DFS(1,0,0); coutansendl; // coutfixedsetprecision(x) ; return 0; }[P1019NOIP 2000 提高组] 单词接龙疑似错题 - 洛谷✨✨涉及:DFS 回溯字符串处理mark 计数解题过程题目条件每个单词最多用2次两个单词拼接必须只是前后缀重叠不可存在包含关系DFS回溯:mark[i]递归 返回后mark[i]–撤销状态mark记录单词使用次数#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; string s[25]; ll mark[25]; ll ans0; string judge(string s1,string s2) { ll len1s1.size(); ll len2s2.size(); for(ll i1;imin(len1,len2);i) { if(s1.substr(len1-i,i)s2.substr(0,i)) { return s1.substr(0,len1-i)s2; } } return 0; } void dfs(string da) { if(da.size()ans) { ansda.size(); } for(ll i1;in;i) { if(mark[i]2) { continue; } string s1judge(da,s[i]); if(s1!0) { mark[i]; dfs(s1); mark[i]--; } } } int main() { IOS char c; cinn; for(ll i1;in;i) { cins[i]; } cinc; for(ll i1;in;i) { if(s[i][0]c) { mark[i]; dfs(s[i]); mark[i]--; } } coutansendl; // coutfixedsetprecision(x) ; return 0; }[P1037NOIP 2002 普及组] 产生数 - 洛谷✨✨涉及:Floyd 传递闭包 高精度乘法不需要 DFS解题过程数据说明在题目中n的范围直接到1e64非常的大 肯定就用字符串存关于题目n2342–53–6那么对于整个过程中2可以变成2 和53可以变成本身3和64只有变 本身 这一个选择4整个过程中只有每个变化相乘 4种变化但是这个过程中也涉及到————高精度乘法(高精度乘低精度)高精度vector低位存在数组前面输出的时候再反转就好vectorllmul(vectorlla,ll x) { vectorllres; ll t0; for(ll num:a) { tnum*x;//高精度*低精度 res.push_back(t%10); t/10; } while(t!0) { res.push_back(t%10); t/10; } return res; }还有一个特殊情况假如说2–4;4–6 ;那就可以得到一个2–6的传递过程————可以用Floyd传递闭包三重循环mid必须放在最外层//Floyd传递闭包 for(ll mid0;mid9;mid) { for(ll i0;i9;i) { for(ll j0;j9;j) { if(f[i][mid]f[mid][j]) { f[i][j]true; } } } }#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; string s; ll k; bool f[10][10]; vectorllmul(vectorlla,ll x) { vectorllres; ll t0; for(ll num:a) { tnum*x; res.push_back(t%10); t/10; } while(t!0) { res.push_back(t%10); t/10; } return res; } int main() { IOS cinsk; for(ll i0;i9;i) { f[i][i]true; } for(ll i1;ik;i) { ll x,y; cinxy; f[x][y]true; } //Floyd传递闭包 for(ll mid0;mid9;mid) { for(ll i0;i9;i) { for(ll j0;j9;j) { if(f[i][mid]f[mid][j]) { f[i][j]true; } } } } ll cnt[10]{0}; //统计多少种变化 for(ll i0;i9;i) { for(ll j0;j9;j) { if(f[i][j]) { cnt[i]; } } } vectorllans; ans.push_back(1); for(char c:s) { ll dc-0; ansmul(ans,cnt[d]); } reverse(ans.begin(),ans.end()); for(ll x:ans) { coutx; } coutendl; // coutfixedsetprecision(x) ; return 0; }P1406 方格填数 - 洛谷✨✨✨解题过程涉及:DFS 回溯 搜索剪枝全排列枚举可以从题目中明确:图样中明显可以看出来每行每列每个对角线的和值为:tarsum/n;先保证行和列已经填充完毕并且和值等于tar再判断对角线依次输出题目中已经要求了字典序最小说明当找到一组就可以用exit(0)结束在填充棋盘格时:填充完毕后就可以去完成这一步了判断行和列的和值、最后就应该去完成对角线的判断了、这一步就非常容易了#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; vectorlla; bool vis[20]; ll tar; ll g[5][5]; void dfs(ll pos) { ll xpos/n; ll ypos%n; //对角线 if(posn*n) { ll d10; ll d20; for(ll i0;in;i) { d1g[i][i]; d2g[i][n-i-1]; } if(d1tard2tar) { couttarendl; for(ll i0;in;i) { for(ll j0;jn;j) { if(j0) { cout ; } coutg[i][j]; } coutendl; } exit(0); } return ; } //行和列 for(ll i0;ia.size();i) { if(vis[i]) { continue; } vis[i]true; g[x][y]a[i]; bool oktrue; if(yn-1) { ll sum10; for(ll j0;jn;j) { sum1g[x][j]; } if(sum1!tar) { okfalse; } } if(xn-1ok) { ll sum10; for(ll j0;jn;j) { sum1g[j][y]; } if(sum1!tar) { okfalse; } } if(ok) { dfs(pos1); } vis[i]false; } } int main() { IOS cinn; ll sum0; a.resize(n*n); for(ll i0;in*n;i) { cina[i]; suma[i]; } tarsum/n; sort(a.begin(),a.end()); dfs(0); // coutfixedsetprecision(x) ; return 0; }B3624 猫粮规划 - 洛谷✨✨✨✨暴力解法暴力版本适合数据小的n20//暴力DFS时间超限了 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; bool b[45]; ll n; ll l,r; ll w[45]; ll ans0; void DFS(ll step,ll sum) { if(stepn1) { if(sumlsumr) { ans; } return ; } DFS(step1,sum); DFS(step1,sumw[step]); } int main() { IOS cinnlr; for(ll i1;in;i) { cinw[i]; } DFS(1,0); coutansendl; // coutfixedsetprecision(x) ; return 0; }优化解DP只能改用DP了但这个也没办法太大的数据如果sum比较大的话也是过不了的现在就01问题了当有一个新的食物x对于目标是食物量j来说就是dp[j]dp[j]dp[j-x];分两种情况:(不选)原来就得到的食物量的方法(选)用x后多的方法#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n,l,r; ll w[50]; ll sum; int main() { IOS cinnlr; sum0; for(ll i1;in;i) { cinw[i]; sumw[i]; } vectorlldp(sum1,0); dp[0]1; for(ll i1;in;i) { ll xw[i]; for(ll ksum;kx;k--) { dp[k]dp[k]dp[k-x]; } } ll ans0; for(ll il;ir;i) { ansdp[i]; } coutansendl; // coutfixedsetprecision(x) ; return 0; }最优解就是折半搜索n40 时 w[i]也非常大时用整体思路就是把n个物品切成两半:分为左右部分DFS暴力枚举左半所有子集和存到a中;右半存到b在这个题目中我们希望 labr变形就可以得到l-abr-a然后把我们就可以把全部物品切成左半堆 left、右半堆 right。去统计分别两堆中的子集和让a与b组合第一次 dfs算左边所有子集和存到 a第二次 dfs算右边所有子集和存到 b#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n,l,r; ll w[50]; ll ans0; void dfs(ll pos,ll s,vectorllw1,vectorllres) { if(posw1.size()) { res.push_back(s); return ; } dfs(pos1,s,w1,res); dfs(pos1,sw1[pos],w1,res); } int main() { IOS cinnlr; vectorllleft; vectorllright; for(ll i0;in;i) { cinw[i]; if(in/2) { left.push_back(w[i]); } else { right.push_back(w[i]); } } vectorlla; vectorllb; dfs(0,0,left,a); dfs(0,0,right,b); sort(b.begin(),b.end()); for(ll x:a) { ll Ll-x; ll Rr-x; auto it1lower_bound(b.begin(),b.end(),L); auto it2upper_bound(b.begin(),b.end(),R); ans(it2-it1); } coutansendl; // coutfixedsetprecision(x) ; return 0; }