【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;//判断该陆地是否为边缘块，是则返回true
            if (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函数：遍历该陆地块周围所有海洋，如果海水最终能漏出到地图边界，说明该陆地并没有被某个环包围，返回true
                        graph[i][j] = '0'; //将被环包围的陆地变为海洋，这样子岛屿将不复存在
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (graph[i][j] == '1') {//若再次遍历到陆地，则岛屿数+1
                    ans++;
                    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上一个点f
    dep[u] = dep[f] + 1; //到达u点时搜索深度为dep[u]，第一个点为深度为1
    siz[u] = 1; 
    sum[u] = val; //积累的从起点到达u所需时间val
    for (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，之间往返的时间z
        cin >> u >> v >> z;
        e[u].emplace_back(v, z); // u到v用时z
        e[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算法：生成树中两点间最短距离=两点各自到祖先结点的距离之和