算法实战：预处理、滑窗、前缀和哈希与图论并查集

这些题目摘录自洛谷，属于典型竞赛题，涵盖模拟优化、图论性质、暴力枚举及动态规划等核心考点。通过练习这些题目，可以有效锻炼解题思路，将算法模板转化为实际代码能力。

本期涉及算法：模拟 + 优化，图的性质 + 并查集，暴力枚举 + 预处理 + 滑动窗口（优化），线性 dp，前缀和 + 哈希表 + 同余，正难则反 - 反图。

1. 寻宝

题目：P1076 [NOIP 2012 普及组] 寻宝

解法：模拟 + 优化

根据题意模拟爬楼过程。如果每层楼都遍历所有房间去找楼梯，时间复杂度会很高。我们可以用 cnt[i] 数组记录第 i 层楼有楼梯的房间数。对于要找的第 s 个楼梯，直接计算 s % cnt[i] 即可定位。注意取模结果为 0 时，应指向该层的最后一个符合条件的房间。

代码：

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e4 + 10, M = 110, MOD = 20123;

LL n, m;
bool st[N][N]; // 标记楼梯信息
LL s[N][M];    // 维护指示牌信息
LL cnt[N];     // 用于优化，存第 i 楼有楼梯的房间个数

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) { // 注意：房间编号从 0 开始
            int a, b;
            cin >> a >> b;
            if (a) {
                st[i][j] = true;
                cnt[i]++;
            }
            s[i][j] = b;
        }
    }

    int pos = 0;
    cin >> pos;
    LL ret = 0;

    for (int i = 1; i <= n; i++) {
        ret = (ret + s[i][pos]) % MOD; // 累加楼层数值
        
        // 优化：直接计算目标位置
        LL step = s[i][pos] % cnt[i];
        if (!step) step = cnt[i]; // 取模为 0 时对应最后一个
        
        while (1) {
            if (st[i][pos]) step--;
            if (step == 0) break;
            pos++;
            if (pos == m) pos = 0; // 走了一圈回到开头
        }
    }

    cout << ret << endl;
    return 0;
}

2. 村村通

题目：P1536 村村通

解法：图的性质 + 并查集

这道题的核心在于连通性。要将已经连接好的部分城镇和未连接的城镇全部连通，所需的最少边数等于 连通块的个数 - 1。因此，我们使用并查集来维护当前连通的点集。

输入可能包含多组数据，通常以 Ctrl+Z 结束输入。在实现时，记得初始化并查集结构。

代码：

#include <iostream>
using namespace std;

const int N = 1010;
int n, m;
int fa[N];

// 查找根节点，带路径压缩
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

// 合并集合
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        fa[rootX] = rootY;
    }
}

int main() {
    while (cin >> n >> m && n != 0) { // 处理多组数据
        for (int i = 1; i <= n; i++) fa[i] = i;
        
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            unite(u, v);
        }

        int components = 0;
        for (int i = 1; i <= n; i++) {
            if (fa[i] == i) components++;
        }

        cout << components - 1 << endl;
    }
    return 0;
}

以上题目适合蓝桥杯及各类算法比赛备战。建议在实际编码中多尝试不同的边界条件，加深理解。