算法实战进阶：预处理、滑动窗口、前缀和与图论并查集应用

前言

这些题目摘录自洛谷，均为典型算法题，适合用于蓝桥杯及各类竞赛备战。通过练习可以锻炼解题思路，从掌握算法模板过渡到具体题目的分析与运用。

本期涉及的核心算法包括：模拟优化、图的性质与并查集、暴力枚举结合预处理与滑动窗口、线性 DP、前缀和结合哈希表与同余性质、以及正难则反的逆向图思维。

1. 寻宝

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

解法：模拟 + 优化

根据题意直接模拟爬楼过程是可行的，但如果每层楼都遍历寻找楼梯房间，时间复杂度会较高。我们可以进行优化：

使用 cnt[i] 数组记录第 i 层楼有楼梯的房间总数。当需要找第 s 个符合要求的房间时，利用取模运算 s % cnt[i] 即可定位。需要注意的是，如果取模结果为 0，实际上对应的是该层的第 cnt[i] 个房间。

代码实现

#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++) {
            int a, b;
            cin >> a >> b;
            if (a) {
                st[i][j] = ;
                cnt[i]++;
            }
            s[i][j] = b;
        }
    }

     pos = ;
    cin >> pos;
    LL ret = ;

     ( i = ; i <= n; i++) {
        ret = (ret + s[i][pos]) % MOD;
        
        
        LL step = s[i][pos] % cnt[i];
         (!step) step = cnt[i];

         () {
             (st[i][pos]) step--;
             (step == ) ;
            pos++;
             (pos == m) pos = ; 
        }
    }

    cout << ret << endl;
     ;
}