1. 递归实现组合型枚举
从 1∼n 这n个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
代码
#include<iostream> using namespace std; bool st[20]; int n; void dfs(int i){ if (i==n+1){ for (int i=1;i<=n;i++){ if (st[i]) cout<<i<<" "; } cout<<endl; return; } st[i]=true; dfs(i+1); st[i]=false; dfs(i+1); } int main(){ cin>>n; dfs(1); }
2.递归实现组合型枚举
从1∼n 这n 个整数中随机选出m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 11 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1357 1357 排在1368 前面）。
数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25
输入样例
5 3
输出样例
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
代码
#include<iostream> using namespace std; int ans[30]; int st[30]; int m,n; void dfs(int x,int y){//从第x个数字开始遍历，且当前用掉了y个数字 if (y==m){ for(int i=0;i<m;i++) cout<<ans[i]<<" "; cout<<endl; return; } if (x+(m-y)>n+1)//从x个数字开始，剩m-y个数字，此时就算把数组剩下的数全遍历完也不能选满m个数 return; for(int i=x;i<=n;i++){//从第x个数字开始遍历而不是从第0个数字，不然会重复 if(st[i]) continue; st[i]=1; ans[y]=i; dfs(i+1,y+1); st[i]=0; } } int main(){ cin>>n>>m; dfs(1,0); return 0; }
走迷宫
给定一个n×m 的二维整数数组，用来表示一个迷宫，数组中只包含0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角)(n,m) 处，至少需要移动多少次。
数据保证(1,1) 处和(n,m) 处的数字为0，且一定至少存在一条通路。
输入格式
第一行包含两个整数n 和 m。
接下来 n 行，每行包含m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例
8
代码
#include<iostream> #include<queue> using namespace std; int n,m; bool st[105][105]; int g[105][105]; int dist[105][105]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; void bfs(){ queue<pair<int,int> > q; q.push({1,1}); st[1][1]=1; while(!q.empty()){ auto [x,y] =q.front(); q.pop(); for(int k=0;k<=3;k++){ int tx=x+dx[k]; int ty=y+dy[k]; if (tx<=0||tx>n||ty<=0||ty>m) continue; if (g[tx][ty]==1) continue; if (st[tx][ty]) continue; q.push({tx,ty}); dist[tx][ty]=dist[x][y]+1; st[tx][ty]=1; } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cin>>g[i][j]; } bfs(); cout<<dist[n][m]; }
树的重心
给定一颗树，树中包含n 个结点（编号 1∼n）和n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。
接下来 n−1 行，每行包含两个整数a 和b，表示点a 和点b 之间存在一条边。
输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例
4
代码
#include<iostream> #include<vector> #include<climits> using namespace std; int n; vector<int> g[100005]; int ans=INT_MAX; bool st[100005]; int dfs(int i){ st[i]=1; int s=1;//以i为树根的总结点数之和,算上i本体 int a=0;//i的子树的最大结点数 for(auto node:g[i]){ if (st[node]) continue; int sum=dfs(node);//以node为树根的子树的结点数，node是i的子树 s+=sum;//在遍历完i的每一个子树后，s值就是i树根的总结点数之和 a=max(sum,a); } ans=min(ans,max(a,n-s));//a表示i的子树的最大的一个，n-s表示去掉i树后剩下的结点数 return s; } int main(){ cin>>n; for(int i=1;i<=n-1;i++){ int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } dfs(1); cout<<ans; }
