题解：P1076 [NOIP2012 普及组] 寻宝

· · 题解

时空隧道

很明显这是一道模拟题，需要注意的是循环时的边界设置以及赋值。

思路：

对于每一层第一个进入的房间，其指示牌上的数表示要找出此层中第几个有楼梯的房间。最终的密钥就是所有层第一个进入的房间指示牌上的数累加后得到的值。

注意：

  1. 由题得：每一层的房间围成一个圈，编号从 0 开始。

  2. 由于 x 的最大值是 10^6 ，如果直接模拟寻找过程会超时，因此需要将 x 模那一层的楼梯数，从而最多只需模拟一圈。

AC代码

 #include<bits/stdc++.h>
using namespace std;
const int mod=20123;
int n,m;
//n为除顶层外藏宝楼的层数，m为除顶层外每层的房间数。
int a[10005][205];
//a数组表示(i,j)房间是否有楼梯通往(i+1,j)房间。
int b[10005][205];
//b数组记录(i,j)房间指示牌上的数字。
int c[10005];
//c(i)是第i层中通往(i+1)层的楼梯的数量。
int x;
//表明出发点在底层x号房间。
int ans;
//ans是小明打开宝箱的密钥。
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
        //每层房间编号从0开始。
            cin>>a[i][j]>>b[i][j];
            c[i]+=a[i][j];
            //c[i]每次累加第i层j号房间是否有楼梯，若有则加1。
        }
    }
    cin>>x;
    for(int i=1;i<=n;i++){
        ans=(ans+b[i][x])%mod;
        //ans累加这层第一个进入的房间指示牌上的数。
        int cnt=0;
        //cnt在内循环中记录已经找到的楼梯数量。
        for(int j=x;j<m;j++){
//注意：j之所以从x开始，是因为此时小明正在(i,j)房间，如果这里有楼梯，也是算作第一个找到的。
            if(a[i][j]) cnt++;
            //判断(i,j)房间里是否存在楼梯；若存在，则计数器加1。
            if(cnt==(b[i][x]-1)%c[i]+1){
            //找到了第i层第b[i][x]个有楼梯的房间。
                x=j;
                break;
                //确定(i+1)层的起始房间号，并退出。
            }
            if(j+1==m)j=-1;
            /*由于j是从x开始的，而j+1==m时答案在x号房间之前，因此需要从头开始找。
这里需要注意：不能将j赋值为0，因为每次循环结束时j都会+1，所以应赋值为-1。
            */
        }
    }
    cout<<ans%mod;
    //保险起见ans再模一次20123。
    return 0;
}

如有意见或疑问请私聊。

谢谢大佬！