献给阿尔吉侬的花束：
算法原理：
用 a[N][N] 接收地图。
dis[N][N] 存储到每个点的路径长度。
从起点出发，广度优先遍历地图：
起点入队。
如果队列非空，一直执行下面语句：
- 队头出队。
- 遍历队头的上下左右四个方向：如果是 ‘.’ 走过去，并且该位置入队，该点对应的dis值更新为队头的dis + 1，该点更新为’#',表示走过了。如果是 ‘#’ 不做处理，如果是 ‘E’,走到了终点，输出该点对应的 dis 值。
如果队列为空，还没有找到终点，则无法到达，输出 oop!。
#include <iostream> #include <queue> #include <cstring> using namespace std; typedef pair<int, int> PII; const int N = 210; char a[N][N]; int dis[N][N]; void bfs(PII start) { queue<PII> q; q.push(start);//队头队，对应步骤1 while(!q.empty()) { PII u = q.front(); q.pop(); int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0 ,-1}; for(int i = 0; i < 4; i++)//遍历四个方向，对应步骤2 { int x = u.first + dx[i]; int y = u.second + dy[i]; if(a[x][y] == '#') continue;//如果是'#',不做任何处理 if(a[x][y] == '.')//如果是 '.'，更新对应内容 { dis[x][y] = dis[u.first][u.second] + 1; a[x][y] = '#'; q.push({x, y}); } if(a[x][y] == 'E')//如果是'E'，找到了，输出 { cout << dis[u.first][u.second] + 1 << endl; return; } } } cout << "oop!" << endl;//没有找到 } int main() { int t; cin >> t; while(t--) { memset(a, '#', sizeof(a));//初始化地图，各个点都是墙。 memset(dis, 0, sizeof(dis));//初始化dis int n,m; PII start; cin >> n >> m; for(int i = 1; i <= n; i++)//从第一行存储地图，因为四周都是墙，bfs时，可以不做越界判断 { for(int j = 1; j <= m; j++)//从第一；列存储地图，因为四周都是墙，bfs时，可以不做越界判断 { cin >> a[i][j]; if(a[i][j] == 'S')//记录下起点位置。 start.first = i, start.second = j, a[i][j] = '#'; } } bfs(start); } }
说明一下，地图初始化为全是墙，然后把地图存储在a[1][1] ~ a[n][m]后，地图四周会被墙包围，所以 bfs 的时候，不用做地图越界处理了。
红与黑
算法原理：
深度优先遍历算法。
对于某个点执行如下算法：
- 从该点出发，如果可以往上走就往上走，对上方点递归执行该算法。
- 从该点出发，如果可以往右走就往右走，对右方点递归执行该算法。
- 从该点出发，如果可以往下走就往下走，对下方点递归执行该算法。
- 从该点出发，如果可以往左走就往左走，对左方点递归执行该算法。
#include <cstring> #include <iostream> using namespace std; const int N = 25; int n, m; char g[N][N];//存储地板 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上右下左四个方向 int dfs(int x, int y)//深度优先遍历 { int cnt = 1; g[x][y] = '#'; for (int i = 0; i < 4; i ++ )//走四个方向 { int a = x + dx[i], b = y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= m) continue; if (g[a][b] != '.') continue; cnt += dfs(a, b);//如果可以走向某一个方向，对该方向上的点递归 } return cnt; } int main() { while (cin >> m >> n, n || m) { for (int i = 0; i < n; i ++ ) cin >> g[i];//一次读入一行 int x, y; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (g[i][j] == '@') { x = i; y = j; } cout << dfs(x, y) << endl; } return 0; }
交换瓶子
算法原理：
暴力枚举
1、通过观察可以发现，我们每一个数都必须回到它自己的位置上，比如 1 必须在第一位，2 必须在第二位上
2、那么我们就可以这样操作，由于每个数必须回到自己的位置，直接从 1 枚举到 n nn ，如果当前位置的数不等于它的下标，那么我们就必须要把它给替换掉
3、设当前位置为 i ii 的话，那么我们就从 i + 1 i+1i+1 开始往后枚举，直到找到对应的 a[j jj] 和我们的 i ii 相等，那么我们就把上个数交换，把交换次数++
4、容易证明这个算法的正确性，由于每个数必须回到原来的位置，所以我们这样子操作不会出现多于的步骤，因为每次操作都是必须的，即使这个算法看起来很麻烦
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int N=10010; int n; int a[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); int sum=0; for(int i=1;i<=n;i++) { if(a[i]!=i)//直接遍历，如果不是自身的话，我们必然要交换，所以不会出现多于的操作 { for(int j=i+1;j<=n;j++) if(a[j]==i) swap(a[i],a[j]); sum++; } } printf("%d\n",sum); return 0; }
完全二叉树的权值
算法原理：
前置：完全二叉树性质
对于第 i ii 层，保证存在 2 i − 1 2^{i-1}2i−1 个结点的满二叉树。
题目思路：
对于每一层的和，我们可以用 h hh 数组进行存储：
h 1 h_1h1 = ∑ i = 2 1 − 1 2 1 − 1 ( a i ) \sum\limits^{2^{1}-1}_{i=2^{1-1}}(a_i)i=21−1∑21−1(ai)
h 2 h_2h2 = ∑ i = 2 2 − 1 2 2 − 1 ( a i ) \sum\limits^{2^{2}-1}_{i=2^{2-1}}(a_i)i=22−1∑22−1(ai)
h 3 h_3h3 = ∑ i = 2 3 − 1 2 3 − 1 ( a i ) \sum\limits^{2^{3}-1}_{i=2^{3-1}}(a_i)i=23−1∑23−1(ai)
h 4 h_4h4 = ∑ i = 2 4 − 1 2 4 − 1 ( a i ) \sum\limits^{2^{4}-1}_{i=2^{4-1}}(a_i)i=24−1∑24−1(ai)
…
是不是发现突然很简单？对于每个 h i h_ihi，我们可以求 ∑ j = 2 i − 1 2 i − 1 ( a j ) \sum\limits^{2^{i}-1}_{j=2^{i-1}}(a_j)j=2i−1∑2i−1(aj) 就行啦！
#include <bits/stdc++.h> #define int long long using namespace std; const int INF = 0x7ffffff; int n; int a[1 << 17], h[17];//2^17 > 10^5 signed main() { scanf ("%lld", &n); for (int i = 1; i <= n; i ++) scanf ("%lld", a + i); //读入 ai，因为 n 的大小是 10^5, 所以用 scanf 这类较快的读入方式。 int i = 1, j = 0; while (i <= n) { ++ j; while (i < pow (2, j)) {//从 2^(j-1) 循环到 2^j-1 h[j] += a[i ++]; } } int maxx = -INF, res = 0;//找最大 for (i = 1; i <= j; i ++) if (h[i] > maxx) maxx = h[i], res = i; printf ("%lld\n", res); return 0; }
地牢大师
算法原理：
分析
- 该迷宫为立体，故需要三维数组构建迷宫模型
- 要求第一次搜到的点即为答案，则考虑BFS
- 记录
S和E的位置，S为搜索开始的点，E为搜索结束点 - 搜索过程中的每个位置需要向六个方向偏移，需要[偏移量]数组
- 偏移点需满足的要求：不越界，未走过，不能是墙
#
#include <bits/stdc++.h> using namespace std; const int N=110; int l,r,c; //迷宫参数 int px,py,pz,ex,ey,ez; //pi为S的位置，ei为E的位置 char mp[N][N][N]; //记录迷宫 int ans[N][N][N]; //存储答案 bool vis[N][N][N]; //记录该点是否走过的状态 struct point{ //点的坐标 int x,y,z; }; queue<point> st; //搜索队列 int dx[]={1,-1,0,0,0,0},dy[]={0,0,1,-1,0,0},dz[]={0,0,0,0,1,-1}; //偏移量数组 int bfs(){ while(!st.empty()){ //当队头不为空时，扩展搜索队头 auto p=st.front(); for(int i=0;i<6;i++){ int m_x=p.x+dx[i],m_y=p.y+dy[i],m_z=p.z+dz[i]; //偏移之后的点的坐标 if(m_x<=l&&m_y<=r&&m_z<=c&&m_x>=1&&m_y>=1&&m_z>=1&&!vis[m_x][m_y][m_z]&&mp[m_x][m_y][m_z]!='#'){ //判断条件 vis[m_x][m_y][m_z]=1; //更新该点走过的状态 ans[m_x][m_y][m_z]=ans[p.x][p.y][p.z]+1; //更新偏移后的点距离S的步骤 if(mp[m_x][m_y][m_z]=='E') return ans[m_x][m_y][m_z]; //搜到E直接返回答案 st.push({m_x,m_y,m_z}); //将该点入队，继续扩展搜索 } } st.pop(); //队头扩展搜索完毕后出队 } return 0; //所有的点扩展搜索完后若还未返回搜到E，说明无解 } int main(){ while(cin>>l>>r>>c&&l&&r&&c){ //多实例读入 //还原数据 memset(ans,0,sizeof(ans)); memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); while(st.size()){ st.pop(); } //读入迷宫 for(int i=1;i<=l;i++){ for(int j=1;j<=r;j++){ for(int k=1;k<=c;k++){ cin>>mp[i][j][k]; if(mp[i][j][k]=='S') px=i,py=j,pz=k; // if(mp[i][j][k]=='E') ex=i,ey=j,ez=k; // } } } vis[px][py][pz]=1; //标记S已经走过 st.push({px,py,pz}); //S点入队 int cnt=bfs(); //调用搜索，将从S点开始搜索 if(cnt!=0) printf("Escaped in %d minute(s).\n",cnt); else cout<<"Trapped!"<<endl; } return 0; }
全球变暖
算法原理
题目一看就是“连通块问题”，是基础搜索。用DFS或BFS都行：遍历一个连通块（找到这个连通块中所有的’#‘，并标记已经搜过，不用再搜）；再遍历下一个连通块…；遍历完所有连通块，统计有多少个连通块。
回到题目，什么岛屿不会被完全淹没？若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。
用DFS或BFS搜出有多少个岛（连通块），并且在搜索时统计那些没有高地的岛（连通块）的数量，就是答案。
因为每个像素点只用搜一次且必须搜一次，所以复杂度是O ( n 2 ) O(n^2)O(n2)的，不可能更好了。
#include<bits/stdc++.h> using namespace std; int n; char a[1010][1010]; //地图 int vis[1010][1010]={0}; //标记是否搜过 int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向 int flag; //用于标记这个岛中是否被完全淹没 void dfs(int x, int y) { vis[x][y] = 1; //标记这个'#'被搜过。注意为什么可以放在这里 if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#') flag = 1; //上下左右都是陆地，不会淹没 for(int i = 0; i < 4; i++){ //继续DFS周围的陆地 int nx = x + d[i][0], ny = y + d[i][1]; //if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //题目说边上都是水，所以不用这么写了 if(vis[nx][ny]==0 && a[nx][ny]=='#') //继续DFS未搜过的陆地，目的是标记它们 dfs(nx,ny); } } int main() { cin >> n; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j]; int ans = 0 ; for(int i = 1; i <= n; i++) //DFS所有像素点 for(int j = 1; j <= n; j++) if(a[i][j]=='#' && vis[i][j]==0) { flag = 0; dfs(i,j); if(flag == 0) //这个岛全部被淹 ans++; //统计岛的数量 } cout<<ans<<endl; return 0; }
