[NOIP 2012 普及组] 寻宝

知识点

循环索引、前缀计数、模拟

解题思路

逐层保存有楼梯的房间编号。当前房间指示值加入密钥；用lower_bound找不小于当前编号的第一处楼梯（越界就绕回0），在有梯编号列表中前进(x-1)模楼梯数步，得到下一层进入房间。

正确性说明

有梯编号列表按房间逆时针编号递增，与题目寻找顺序一致。lower_bound包含当前位置，恰好满足当前有梯算第一个；前进x-1步并模列表长度，等价于逐间绕圈找第x处楼梯。逐层更新和取模累加因此正确。

易错点

从0编号；累加的是刚进入的房间指示值，不是最终上楼房间的值；不能直接按房间数M取模。

复杂度

时间O(NM+N log M)，空间O(NM)，按输入格式需保存全部楼层后才能读起点。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<vector<int>>a(n,vector<int>(m)),stair(n);for(int i=0;i<n;i++)for(int j=0;j<m;j++){int s;cin>>s>>a[i][j];if(s)stair[i].push_back(j);}int pos;cin>>pos;int ans=0;for(int i=0;i<n;i++){int x=a[i][pos];ans=(ans+x)%20123;auto&v=stair[i];int k=lower_bound(v.begin(),v.end(),pos)-v.begin();pos=v[(k+(x-1)%v.size())%v.size()];}cout<<ans<<'\n';}