本文主要是介绍【2024.1.17练习】C++岛屿个数/整数删除/景区导游/砍树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2023蓝桥杯C++B组省赛F题：岛屿个数
#include<iostream>
#include<algorithm>
#include<queue>using namespace std;
typedef long long ll;const int dx[8] = { 1, -1, 0, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, 0, 1, -1, -1, 1, -1, 1 };/* 地图块周围的八块格子 */
int n, m;
char graph[60][60];/*实际图*/
bool vis[60][60];/*视图*/bool fill(int A, int B) { // 传入第 A 行第 B 列的地图块for (int i = 0; i <= n + 1; i++) {for (int j = 0; j <= m + 1; j++) {vis[i][j] = false; //给视图层地图赋值，视图层地图比实际地图大一圈}}queue<pair<int, int> > q; //元素为对组类型数据的队列q.emplace(A, B); //将该陆地块位置添加到队列末尾vis[A][B] = true; //视图层标记传入陆地块while (!q.empty()) {auto cur = q.front(); //auto修饰的变量自动选择合适的数据类型（对组），cur存入队列中数据q.pop();//出队操作int x = cur.first, y = cur.second;//x,y分别存储陆地块的行、列for (int i = 0; i < 8; i++) {int nx = x + dx[i], ny = y + dy[i];/* nx , ny 存储了传入陆地块周围八个格子的数据*/if (nx < 1 || nx > n || ny < 1 || ny > m) return true;//判断该陆地是否为边缘块，是则返回trueif (graph[nx][ny] == '0' && !vis[nx][ny]) { //若该周围块为海洋且对应视图块未标记vis[nx][ny] = true; //标记该视图块q.emplace(nx, ny); //队列中传入该视图块，下一次循环将监视该标记块的周围块}}}return false;//遍历结束，所有延伸标记的块均不为边缘块，则返回false
}void bfs(int A, int B) {queue<pair<int, int> > q;q.emplace(A, B);while (!q.empty()) {auto cur = q.front();q.pop();int x = cur.first, y = cur.second;for (int i = 0; i < 4; i++) {//利用队列广度搜索上下左右的块int nx = x + dx[i], ny = y + dy[i];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && graph[nx][ny] == '1') {//周围衔接陆地块graph[nx][ny] = '0';//陆地块变海洋块q.emplace(nx, ny);//周围块入队}}}
}int main() {ios::sync_with_stdio(false);int T;cin >> T;while (T--) {cin >> n >> m; //确定地图大小：n 行 m 列for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> graph[i][j];}} //输入地图数据int ans = 0; // ans 表示答案for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (graph[i][j] == '1') { //遍历地图，判断当前块是否为陆地if (!fill(i, j)) //fill函数：遍历该陆地块周围所有海洋，如果海水最终能漏出到地图边界，说明该陆地并没有被某个环包围，返回truegraph[i][j] = '0'; //将被环包围的陆地变为海洋，这样子岛屿将不复存在}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (graph[i][j] == '1') {//若再次遍历到陆地，则岛屿数+1ans++;bfs(i, j);//利用广度搜索删除掉该陆地块周围衔接的所有陆地块，这样地图上每个陆地块最终都只代表一个岛屿！}}}cout << ans << endl;}return 0;
}这道题的解法妙在判断岛屿是否被环包围，反其道而行之，改而分析周围的海洋能否衍生到地图边界。
2023蓝桥杯C++B组省赛H题:整数删除
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;
typedef long long ll;const int maxn = 5e5 + 10;ll v[maxn], l[maxn], r[maxn];void del(ll x) { //传入要删除的序号r[l[x]] = r[x], l[r[x]] = l[x]; //删除结点前驱的后继指向删除结点的后继，删除结点后继的前驱指向删除结点的前驱v[l[x]] += v[x], v[r[x]] += v[x]; //删除结点的两边结点数值增加
}int main() {int n, k; //n为数列长度，重复k次cin >> n >> k;priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;/*priority_queue为优先级队列，greater表示数字小的优先级高*/r[0] = 1, l[n + 1] = n;for (int i = 1; i <= n; i++) {cin >> v[i]; //v[1~n]用于存储数列l[i] = i - 1; //存储对应序号数字的左边一位，对应结点i的前驱r[i] = i + 1; //存储对应序号数字的右边一位，对应结点i的后继pq.emplace(v[i], i); //将数字和它在数列中的序号传入队列}while (k--) {auto p = pq.top(); //获取堆顶(队首)元素，即输入的最小数和其序号pq.pop(); //删除堆顶(队首)元素if (p.first != v[p.second]) {pq.emplace(v[p.second], p.second);k++;} //当原本的最小数因为吸收删除数值变大后，将其重新入队else del(p.second); //否则进行删除结点操作}ll head = r[0];while (head != n + 1) {cout << v[head] << " "; //输出最终结果数列head = r[head]; //访问下一个数}return 0;
}
这道题巧妙地构造了两个数组r[ ] 和l[ ]，充当了指针的作用，全程序看似没有使用链表，实则处处使用链表。
2023蓝桥杯C++B组省赛I题:景区导游
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;
typedef long long ll;const int maxn = 1e5 + 10;vector<pair<int, int>> e[maxn]; //动态数组用于存储景点，e[]是元素为链表的数组
ll fa[maxn], dep[maxn], son[maxn], siz[maxn], top[maxn];
ll c[maxn], suf[maxn]; //c[]用于存储旅游路线
ll sum[maxn];void dfs1(ll u, ll f, ll val) { //初始值：u=1(从点1开始搜索)，f=1(上一个搜索的点), val=0(已积累的搜索用时)fa[u] = f; //存储该点u上一个点fdep[u] = dep[f] + 1; //到达u点时搜索深度为dep[u]，第一个点为深度为1siz[u] = 1; sum[u] = val; //积累的从起点到达u所需时间valfor (auto x : e[u]) { // x:遍历获得容器里的每一个元素，即所有以u为起点的链表结点ll v = x.first; // v:u所连接的点if (v == f) continue; //若找到的下个点和上个点相同，则continue:直接进入下一次循环/* PS：由于路线是生成树，所以不存在回路，因此只要下个点不是上个点，就一定不会重复 */dfs1(v, u, val + x.second); //积累搜索用时，传入下一个点进行搜索siz[u] += siz[v]; //记录从u点能继续往下走到几个点（体积）if (siz[v] > siz[son[u]]) son[u] = v; //son[u]：u的最大体积子连接点}
}void dfs2(ll u, ll t) { //初始值：u=1, t=1，表示仍从1号点开始搜索top[u] = t;if (!son[u]) return; //到达叶子结点则返回dfs2(son[u], t); //从最长的1条分支开始搜索for (auto x : e[u]) {ll v = x.first; // v:u所连接的点if (v != son[u] && v != fa[u]) dfs2(v, v);}
}ll lca(ll x, ll y) { //寻找公共祖先函数while (top[x] != top[y]) { //循环直到x,y成为同一分支if (dep[top[x]] < dep[top[y]]) swap(x, y); //若x分支起点的深度比y小，则交换x,y值/*PS：上面这一步是因为x,y中有一方会率先找到祖先结点，它的深度一定小于未找到祖先结点的*/x = fa[top[x]]; //x获取较大分支起点深度的那个点的上个分支点}return dep[x] > dep[y] ? y : x; //返回同一分支上深度较浅的点
}ll get(ll x, ll y) { //输入旅游路线中相邻两个点，get函数将获得这两个点之间最短路径长度if (x == 0 || y == 0) return 0;return sum[x] + sum[y] - 2 * sum[lca(x, y)]; //两个点的本身的权值-公共祖先的权值*2
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); //取消同步int n, k; cin >> n >> k; //n为景点数，k表示旅游线路经过景点数for (int i = 1; i < n; i++) {int u, v, z; //分别代表：景点u，景点v，之间往返的时间zcin >> u >> v >> z;e[u].emplace_back(v, z); // u到v用时ze[v].emplace_back(u, z); // v到u用时z}dfs1(1, 1, 0);//第一次深度优先遍历：获得点1到各点的用时sum[u]、各点深度dep[u]、各点遍历的前驱fa[u]和最长后继son[u]dfs2(1, 1);for (int i = 1; i <= k; i++) cin >> c[i]; //录入旅游路线for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] + get(c[i], c[i + 1]);//suf[i]记录了旅游过程中总路程的增长ll pre = 0;for (int i = 1; i <= k; i++) { //输出用时cout << pre + get(c[i - 1], c[i + 1]) + suf[i + 1] << " ";//遍历输出每种旅游跳过路线的总路程pre += get(c[i - 1], c[i]);}return 0;
}
运用了LCA算法：生成树中两点间最短距离=两点各自到祖先结点的距离之和
2023蓝桥杯C++B组省赛J题:砍树
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;
typedef long long ll;const int maxn = 1e5 + 50;vector<int> e[maxn]; //存储动态数组的数组
ll fa[maxn], dep[maxn], son[maxn], siz[maxn], top[maxn];
ll diff[maxn]; //差分值void dfs1(ll u, ll f) { //初始当前搜索结点u=1,上一个搜索结点也为1fa[u] = f;dep[u] = dep[f] + 1; //搜索深度siz[u] = 1; //该节点之后可以访问到的结点总数，建立分支的依据for (auto x : e[u]) { //遍历该结点每个周边结点ll v = x;if (v == f) continue;dfs1(v, u); //深度优先搜索下一个结点siz[u] += siz[v];if (siz[v] > siz[son[u]]) son[u] = v; //确立子结点，用于建立分支}
}void dfs2(ll u, ll t) {top[u] = t; //top[u]代表u结点所属分支if (!son[u]) return; //访问到了叶子结点后退回dfs2(son[u], t); //深度优先搜索下一个子结点for (auto x : e[u]) { //子节点（主线）确立分支后开始遍历支线ll v = x;if (v != son[u] && v != fa[u]) dfs2(v, v);}
}ll lca(ll x, ll y) { //获取公共祖先结点while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);x = fa[top[x]];}return dep[x] > dep[y] ? y : x;
}void dfs(int x, int fx) {//从初始结点开始，0for (auto y : e[x]) { //遍历x结点连接结点if (y == fx) continue;dfs(y, x);diff[x] += diff[y]; //从端点到起点，每个结点获取其周边结点的差分值}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);//取消同步int n, m;cin >> n >> m; // n:结点数 m:隔离数for (int i = 1; i < n; i++) {int u, v;cin >> u >> v; //输入一条边的两个端点e[u].emplace_back(v);e[v].emplace_back(u);} //e[u]中存储了u可以抵达的每个顶点dfs1(1, 1); //确定了每个结点的深度、子结点和父结点dfs2(1, 1); //确立所有结点所属分支for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v; //输入要彼此隔离的结点diff[u]++, diff[v]++, diff[lca(u, v)] -= 2; //隔离点差分值+1，公共祖先结点差分值-2}dfs(1, 0); //本质上是获取了从每个隔离点到另一个对应点每条边经过的次数ll ans = -1;for (int i = 0; i <= n; i++) if (diff[i] >= m) ans = i - 1; //若该边的总经过次数不小于隔离数（意味着每对隔离点连接都经过该边），则可以砍cout << ans << endl;return 0;
}运用了LCA算法，寻找每对隔离点的公共祖先结点。
运用了树上边差分算法，计算点到点之间经过边的次数找到每对隔离点连接所需经过的公共边。
这篇关于【2024.1.17练习】C++岛屿个数/整数删除/景区导游/砍树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
