这些题目摘录自洛谷,属于考察各类算法运用的典型好题,适合用于蓝桥杯及各类算法比赛的备战练习。重点在于锻炼解题思路,从掌握算法模板过渡到分析具体应用场景。
1. 寻宝
解法:模拟 + 优化
根据题意模拟爬楼过程。如果每层楼都遍历去找特定房间,时间复杂度会很高。我们可以优化这个过程:用一个 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;
}
}
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;
;
}


