信息学奥赛一本通 1958：【12NOIP普及组】寻宝 | 洛谷 P1076 [NOIP2012 普及组] 寻宝

信息学奥赛一本通 1958：【12NOIP普及组】寻宝 | 洛谷 P1076 [NOIP2012 普及组] 寻宝 【题目链接】

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

【题目考点】 1. 模拟 2. 循环遍历数组 【解题思路】

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

房间指示牌号码 x x x的范围能达到 1 0 6 10^6 106，而每层的房间数 M M M只有100的数量级。这说明在选择房间的过程中，不需要真的做 x x x次选择。（类似问题：已知现在钟表分针指向3，请问1万分钟后分针指向几）
假设该层有楼梯的房间数为u。

如果 x % u x%u x%u为0，那么需要选择 u u u次如果 x % u x%u x%u不为0，需要选择 x % u x%u x%u次。 在做房间选择时，注意要对数组做循环遍历，当下标i遍历到M-1时，下一次i要变为0，就像在一个环上遍历一样。写法为：j = (j + 1) % M结果取模：根据 ( a + b ) % M = ( a % M + b % M ) % M (a+b)%M = (a%M + b%M)%M (a+b)%M=(a%M+b%M)%M，要使结果取模M，那么可以在加法过程中，每得到一个中间结果都对其取模M，结果是一样的。 【题解代码】 解法1：

#include
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;
}