[数据结构与算法]信息学奥赛一本通 1958：【12NOIP普及组】寻宝 | 洛谷 P1076 [NOIP2012 普及组] 寻宝

【题目链接】

ybt 1958：【12NOIP普及组】寻宝
洛谷 P1076 [NOIP2012 普及组] 寻宝

【题目考点】

1. 模拟

2. 循环遍历数组

【解题思路】

根据题意，模拟一个人选择房间不断上楼的过程。
要注意以下几点：

• 房间指示牌号码$x$的范围能达到$10^6$，而每层的房间数$M$只有100的数量级。这说明在选择房间的过程中，不需要真的做$x$次选择。（类似问题：已知现在钟表分针指向3，请问1万分钟后分针指向几）
  假设该层有楼梯的房间数为u。
  • 如果$x\%u$为0，那么需要选择$u$次
  • 如果$x\%u$不为0，需要选择$x\%u$次。
• 在做房间选择时，注意要对数组做循环遍历，当下标i遍历到M-1时，下一次i要变为0，就像在一个环上遍历一样。写法为：j = (j + 1) % M
• 结果取模：根据$(a+b)\%M=(a\%M+b\%M)\%M$，要使结果取模M，那么可以在加法过程中，每得到一个中间结果都对其取模M，结果是一样的。

【题解代码】

解法1：

#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define M 105
int n, m, ans;
int x[N][M];//x[i][j]:第i层第j房间的标牌号，表示逆时针方向选择第x[i][j]房间可以上楼 
int upNum[N];//upNum[i]:第i层有几个有楼梯的房间 
int isUp[N][M];//isUp[i][j]:第i层第j房间是否有楼梯 
int main()
{
    scanf("%d %d", &n ,&m);
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < m; ++j)
        {
            scanf("%d %d", &isUp[i][j], &x[i][j]);
            if(isUp[i][j])//统计第i层有楼梯的房间数量
                upNum[i]++;
        }
    int j, roomNum;//roomNum:需要选择有楼梯的房间的最少次数 
    scanf("%d", &j);//起始房间号 
    for(int i = 1; i <= n; ++i)
    {
        ans = (ans + x[i][j]) % 20123;//一边加一边取模
        if(x[i][j] % upNum[i] == 0)//求出需要选择房间的最少次数
            roomNum = upNum[i];
        else
            roomNum = x[i][j] % upNum[i];
        int k = 0;//看过的有楼梯的房间数
        if(isUp[i][j])
            k++;
        while(k < roomNum)//循环结束后，j指向第roomNum个房间，进入上一层的j房间 
        {
            j = (j + 1) % M;//循环遍历数组，M-1的下一个位置是0   
            if(isUp[i][j])//如果j房间有楼梯 
                k++;
        }
    }
    cout << ans; 
	return 0;
}