P1706 在一个方阵中有多少个#上下左右相邻的区域用dfs遍历每个点标记P1331 对于一列数给它排序问有几种排法顺序不同就算一种用dfs遍历每个数内含回溯达到交换数字顺序P1036 对于一列数选出三个数相加和为质数问有几种选法用dfs遍历每个数让其回溯时避免同样的数字以不同的顺序出现P1036 选数题目大意已知n nn个整数从中选出k kk个数进行相加统计总和是素数的组合一共有多少种。注意n ≤ 20 n\le 20n≤20选数是组合不考虑顺序vis 只能保证一条递归链条里面不会重复选同一个元素。但是不能阻止不同顺序挑选同一批元素产生重复方案。同一个数字只能选一次不需要输出具体是哪些数只输出满足条件的方案数量。样例输入 (n4,k3)数字3 7 12 19所有3数组合(371222)不是素数(371929)素数(3121934)不是素数(7121938)不是素数满足条件只有1种输出1。核心思路DFS回溯枚举所有选k kk个数的组合 素数判断#includebits/stdc.h using namespace std; #define int long long #define endl \n #define pii pairint,int #define fi first #define se second const int N101; int n,k; vectorinta; //vectorboolvis; int ans0; bool check(int x){ if(x2)return true; else if(x2)return false; else if(x%20)return false; else{ for(int i3;i*ix;i2){ if(x%i0) return false; } } return true; } //pos当前遍历到数组第几个位置 //cnt已经选了多少个数 //sum已经选出数字的累加和 void dfs(int pos,int step,int sum){ if(stepk){ if(check(sum)) ans; return; } for(int ipos;in;i){ dfs(i1,step1,suma[i]); //vis[i]false; } } void slove(){ cinnk; a.resize(n1); //vis.resize(n1); ans0; for(int i1;in;i){ cina[i]; } dfs(1,0,0); coutansendl; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _1; //cin_; while(_--) slove(); return 0; }P1331 海战 - 洛谷P1331 海战题目大意R行C列网格#代表船.代表海水。船是方形由#四连通构成。两艘船上下/左右4方向不能相邻斜对角挨在一起是允许的。不合法输出Bad placement.合法输出船只总数。数据R , C ≤ 1000 R,C\le 1000R,C≤1000。核心思路非法快速判定遍历所有2×2田字格如果某个田字格内#恰好等于3个代表两艘船4方向接触直接非法。遇到未访问的#就是新船。对每一块连通块记录最大最小行列、格子数量校验是否是方形,并且格子数边长×边长不满足则非法。全部校验通过输出船的数量。#includebits/stdc.h using namespace std; const int N1005; char mp[N][N]; bool vis[N][N]; int r,c; int dx[]{-1,1,0,0}; int dy[]{0,0,-1,1}; int minx,maxx,miny,maxy,cnt; void dfs(int x,int y) { vis[x][y]true; cnt; minxmin(minx,x); maxxmax(maxx,x); minymin(miny,y); maxymax(maxy,y); for(int i0;i4;i) { int nxxdx[i]; int nyydy[i]; if(nx1nxrny1nyc!vis[nx][ny]mp[nx][ny]#) { dfs(nx,ny); } } } int main() { cinrc; for(int i1;ir;i) for(int j1;jc;j) cinmp[i][j]; int ship0; bool oktrue; for(int i1;ir;i) { for(int j1;jc;j) { if(mp[i][j]#!vis[i][j]) { //初始化当前连通块边界 minxmaxxi; minymaxyj; cnt0; dfs(i,j); //等到把#上下左右的位置全都访问并加入之后 //看看这些#所在的位置形成的矩形的面积与现有的面积是否相等 //如果不相等这不是方形的船就不算船 int S(maxx-minx1)*(maxy-miny1); if(S!cnt) { okfalse; } ship; } } } if(!ok) { coutBad placement.endl; } else { coutThere are ship ships.endl; } return 0; }P1706 全排列问题 - 洛谷P1706 全排列问题题目大意给定整数n nn1 ≤ n ≤ 9 1\le n \le91≤n≤9输出1 ∼ n 1\sim n1∼n的全部不重复全排列按字典序输出。每个数字占5个字符宽度每一行输出一组排列。例n3输出1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1核心思路DFS回溯维护一个数组path保存当前正在构造的排列。布尔数组vis[]标记数字是否已经被选过防止重复选取。dfs(step)step表示当前填第几个位置递归终止条件stepn代表一组排列生成完毕格式化打印path。循环数字i从1~n如果vis[i]false标记已选放入path递归下一层递归返回后回溯取消标记。i从1往n遍历天然保证输出是字典序。#includebits/stdc.h using namespace std; const int N 12; int n; int res[N]; //保存当前排列 bool vis[N]; void dfs(int step){ if(stepn){ for(int i1;in;i){ printf(%5d,res[i]); cout fixed setprecision(2); } printf(\n); return; } for(int i1;in;i){ if(!vis[i]){ vis[i]true; res[step]i;//代表不同种排序 dfs(step1); vis[i]false; } } } int main(){ cinn; dfs(1); return 0; }备选C STL函数next_permutation也可以直接生成全排列。#includebits/stdc.h using namespace std; int a[10]; int main() { int n,i,j1,k; cinn; for(i1;in;i) {a[i]n-i1;j*i;}//题目好像没说要从小到大输出 //但保险起见还是初始赋值为最大序列 //即a[1~n]n~1;顺便计算n! for(i1;ij;i) {next_permutation(a1,an1); for(k1;kn;k) cout a[k];//排一次输出一次 //空格建议复制 coutendl; } return 0; }