周测复盘【回溯】

P2089 烤鸡直接上我的代码等我彻底搞懂逻辑挂个链接来讲这个题呢挂不来链接反正给自己看的挂个文件路径算了C:\Users\22766\Videos\c5c32f36f01bbe40e0340881774c96cc.mp4#include bits/stdc.h using namespace std; int n; int target; vectorvectorint ans; void dfs(int pos, int sum, vectorint path) { if (pos 10) { if (sum target) { vectorint res; for (int num : path) res.push_back(num 1); ans.push_back(res); } return; } for (int val 0; val 2; val) { if (sum val target) continue; path.push_back(val); dfs(pos 1, sum val, path); path.pop_back(); } } int main() { cin n; target n - 10; if (target 0 || target 20) { cout 0 endl; return 0; } vectorint tmp; dfs(0, 0, tmp); cout ans.size() endl; for (auto v : ans) { for (int i 0; i 10; i) { if (i 0) cout ; cout v[i]; } cout endl; } return 0; }老师的提供的错误点一般都不会犯因为知道要用dfs但就是时而逻辑不清晰会卡壳P1036 [NOIP 2002 普及组] 选数写第一遍的时候状况百出啊但好在方法是对的但是运用不熟练改来改去依旧最后一个例子超时了好头疼遇到这种怎么办问了豆包提供了一种思路米勒 - 拉宾素性测试MR 随机素数判定对超大数极快不用预开数组本题首选没看懂转战b站#includebits/stdc.h using namespace std; typedef long long ll; int n, k; vectorll num; int cnt_ans 0; bool isprime(ll x) { if (x 2) return false; if (x 2) return true; if (x % 2 0) return false; ll sq sqrt(x); for (ll i 3; i sq; i 2) { if (x % i 0) return false; } return true; } /** * DFS回溯函数 * pos: 从数组第pos位开始选保证组合不重复 * select_cnt: 已经选了几个数 * sum_val: 当前选中数字的总和 */ void dfs(int pos, int select_cnt, ll sum_val) { // 递归终止条件1已经选够k个数 if (select_cnt k) { if (isprime(sum_val)) cnt_ans; return; } // 递归终止条件2遍历完所有数字直接返回 if (pos n) return; // 分支1选当前第pos这个数 dfs(pos 1, select_cnt 1, sum_val num[pos]); // 分支2不选当前第pos这个数直接往后走 dfs(pos 1, select_cnt, sum_val); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; num.resize(n); for (int i 0; i n; i) { cin num[i]; } // 初始状态从0下标开始选0个和为0 dfs(0, 0, 0); cout cnt_ans endl; return 0; }老师的代码边界处理更好就不会超时bool isprime(int x) { if(x2) return false; if(x2) return true; if(x%20) return false; for(int i3;1LL*i*ix;i2) if(x%i0) return false; return true; } void dfs(int dep,int st,int sum) { if(depk) { if(isprime(sum)) ans; return; } // 还需要选择 k-dep 个数 // 因此 i 最大只能到 n-(k-dep)1 for(int ist;in-(k-dep)1;i) { dfs(dep1,i1,suma[i]); } }P2036 [COCI 2008/2009 #2] PERKET卡壳卡在cha min(cha, llabs(s_sum - b_sum));这句的位置与边界的判断s_sum1 b_sum0代表一个食材都没选的空方案题目强制要求至少选 1 种配料这个方案非法必须删掉如果去掉这段代码空方案会参与计算直接把答案改错样例 1 就崩了。当所有食材全部执行「不选」分支递归最后走到pos n时s_sum 仍然是 1b_sum 仍然是 0→ 这就是全盘不拿任何配料的无效方案#includebits/stdc.h using namespace std; typedef long long ll; int n; vectorpairll,llta; ll cha1e18; void dfs(int pos,ll s_sum,ll b_sum) { if(posn) { if (s_sum 1 b_sum 0) { return; } cha min(cha, llabs(s_sum - b_sum)); return; } //chamin(llabs(s_sum-b_sum),cha); // 分支1 // 数值完全不动直接下一位 dfs(pos 1, s_sum, b_sum); //分支2 // 先算新的乘积、新的和避免修改原变量影响回溯 ll new_s_sum s_sum * ta[pos].first; ll new_b_sum b_sum ta[pos].second; dfs(pos 1, new_s_sum, new_b_sum); } int main() { cinn; ta.resize(n); for(int i0;in;i) { cinta[i].firstta[i].second; } dfs(0,1,0); coutchaendl; return 0; }P1162 填涂颜色这道题的回溯有点复杂大致的写出来了样例过了但是没有完全ac逻辑还在补全中老师解析中但题目给了一个极其重要的定义圈内的 0 无法通过其他 0 到达边界。反过来说所有能到达边界的 0一定都在圈外。欸嘿我是一点没想到。#includebits/stdc.h using namespace std; const int N40; int n,a[N][N]; bool vis[N][N]; int dx[4]{1,-1,0,0}; int dy[4]{0,0,1,-1}; void dfs(int x,int y) { vis[x][y]true; for(int k0;k4;k) { int nxxdx[k]; int nyydy[k]; if(nx0||nxn1||ny0||nyn1) continue; if(vis[nx][ny]) continue; if(a[nx][ny]1) continue; dfs(nx,ny); } } int main() { scanf(%d,n); // a 是全局数组外围默认全部为 0 for(int i1;in;i) for(int j1;jn;j) scanf(%d,a[i][j]); // 从人为添加的外围开始搜索 dfs(0,0); for(int i1;in;i) for(int j1;jn;j) if(a[i][j]0!vis[i][j]) a[i][j]2; for(int i1;in;i) { for(int j1;jn;j) printf(%d%c,a[i][j],jn?\n: ); } return 0; }下次触发信号看到求被封闭起来的区域判断某区域是否与边界连通内部不好判断外部很好判断应该想到从边界反向 Flood Fill ↓ 标记所有外部区域 ↓ 剩下的就是内部区域关键词封闭区域 先搜外面E. P1141 01迷宫这个题更是考虑的地方更多了本来想直接递归但是绝对会超时这个题是一直卡着总有情况没考虑到第一次见到连接块只能直接上解析#includebits/stdc.h using namespace std; typedef pairint,int PII; const int N1010; const int M1000010; char a[N][N]; int belong[N][N],sze[M]; int n,m,tot; int dx[4]{1,-1,0,0}; int dy[4]{0,0,1,-1}; void dfs(int sx,int sy) { tot; stackPII sta; sta.push({sx,sy}); belong[sx][sy]tot; while(!sta.empty()) { int xsta.top().first; int ysta.top().second; sta.pop(); sze[tot]; for(int k0;k4;k) { int nxxdx[k]; int nyydy[k]; if(nx1||nxn||ny1||nyn) continue; if(belong[nx][ny]) continue; // 必须走到与当前格数字不同的位置 if(a[nx][ny]a[x][y]) continue; // 入栈时立刻标记避免同一个格子重复入栈 belong[nx][ny]tot; sta.push({nx,ny}); } } } int main() { scanf(%d%d,n,m); for(int i1;in;i) scanf(%s,a[i]1); // 预处理所有连通块 for(int i1;in;i) { for(int j1;jn;j) { if(!belong[i][j]) dfs(i,j); } } while(m--) { int x,y; scanf(%d%d,x,y); printf(%d\n,sze[belong[x][y]]); } return 0; }P1433 吃奶酪初始思路首先计算距离可以用一块函数输出的是至少要跑的距离所以sum加上他们点算出来的距离总和用min来保留最小的结果输出的时候用coutfixedsetprecision(2)ans;保留两位小数然后注意到每次回溯更新小鼠的pos也要同步更新不需回到原点但是这样递归肯定也是次次都要递归要考虑到时间空间复杂度适不适合这样写解析给出 DFS 状态出现了大量重复需要合并的结论记忆化 DFS解析里是直接预处理距离了比我想得每一次递归的时候算要简洁的多更不会增大计算量典型记忆化dfs就直接上解析讲解视频后续补上#includebits/stdc.h using namespace std; const int N15; const int M115; int n,full; double x[N],y[N]; double dis[N][N]; double f[M][N]; bool vis[M][N]; double dfs(int mask,int now) { // 所有奶酪已经吃完 if(maskfull) return 0; // 这个状态以前已经计算过 if(vis[mask][now]) return f[mask][now]; vis[mask][now]true; double res1e100; for(int i0;in;i) { // 第 i 块奶酪还没有吃 if(!(mask(1i))) { resmin(res, dis[now][i] dfs(mask|(1i),i)); } } return f[mask][now]res; } int main() { scanf(%d,n); for(int i0;in;i) scanf(%lf%lf,x[i],y[i]); // 预处理奶酪之间的距离 for(int i0;in;i) { for(int j0;jn;j) { double dxx[i]-x[j]; double dyy[i]-y[j]; dis[i][j]sqrt(dx*dxdy*dy); } } full(1n)-1; double ans1e100; // 枚举第一块吃哪一个奶酪 for(int i0;in;i) { double firstsqrt(x[i]*x[i]y[i]*y[i]); ansmin(ans, firstdfs(1i,i)); } printf(%.2lf\n,ans); return 0; }