P1076 寻宝

admin

https://www.luogu.org/problemnew/show/P1076

题目描述
传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：

藏宝楼共有 N+1 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另 0 有 N 层，每层 M 个房间，这 M 个房间围成一圈并按逆时针方向依次编号为 0,…,M-1 。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字 x ，表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的 k 号房间。比如当前房间的指示牌上写着 2 ，则按逆时针方向开始尝试，找到第 2 个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。

寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。

请帮助小明算出这个打开宝箱的密钥。

输入输出格式
输入格式：
第一行 2 个整数 N 和 M ，之间用一个空格隔开。 N 表示除了顶层外藏宝楼共 N 层楼， M 表示除顶层外每层楼有 M个房间。

接下来 N×M 行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第 (i−1)×M+j 行表示第 i 层 j−1 号房间的情况（i=1,2,…,N ；j=1,2,…,M ）。第一个整数表示该房间是否有楼梯通往上一层（ 0 表示没有， 1 表示有），第二个整数表示指示牌上的数字。注意，从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。

最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从 0 开始）。

输出格式：
一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对 20123 取模的结果即可。

输入输出样例
输入样例#1：
2 3
1 2
0 3
1 4
0 1
1 5
1 2
1
输出样例#1：
5
说明
【数据范围】

对于50%数据，有 0<N≤1000,0<x≤10000 ；
对于100%数据，有 0<N≤10000,0<M≤100,0<x≤1,000,000 。

NOIP 2012 普及组 第二题

admin

这几乎是个纯粹的模拟题，只是需要用到一点%的简单知识，但是读懂题意不是件容易事，有些同学居然还不能模拟出样例，这就很为难了，我们先看看样例，

admin

先来一个硬模拟，完全按照题意，以一楼进入的那个房间开始，逆时针数硬数相应个有楼梯的房间。
用b(i)(j)表示房间第i楼j号房是否有楼梯，c(i)(j)表示要计入的数字，假设进来的房间号是k，要逆时针转的数字x=c(i)(j) 那么上楼的房间x应该这样求(类似约瑟夫问题)

1.                         x=c[i][k];
   
2.                         ans+=x;
   
3.                         ans%=20123;  // 基本取个模操作
   
4.                         ///走x下
   
5.                         while (x>0)
   
6.                                 {
   
7.                                         k++;
   
8.                                         if (k==m)k=0; //首尾相接
   
9.                                         if (b[i][k]==1) x--;
   
10.                                 }
    
11.                         //cout<<i<<' '<<k<<' '<<endl;
    
12.                

复制代码

大家看看中间那主要的一段，是不是很像约瑟夫问题，所以大家要背一些经典的程序段，可以拿来套用，就像语文英语都要比范文一样。但是这样交上去，都是0分呀，为什么呢？

admin

因为没有考虑题目中的“如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。”。我第一次做的时候也没有考虑到这个，看来读题目很重要！！这种感觉只能在多做题过程中去积累，因为当前房间可能有楼梯，于是加上一句特判。

1. if (b[i][k]==1) x--;//当前房间有楼梯

复制代码

组合成完整代码，交上去，对了5组，其他超时，预计之中。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int mm=110,mn=10100;
   
4. int m,n;
   
5. int b[mn][mm],c[mn][mm];
   
6. int i,j,k;
   
7. int ans,x;
   
8. int main()
   
9. {
   
10.         cin>>n>>m;
    
11.         for (i=1; i<=n; i++)
    
12.                 for (j=0; j<=m-1; j++)
    
13.                         cin>>b[i][j]>>c[i][j];
    
14. 
    
15.         cin>>k;
    
16.         ans=0;
    
17.         for (i=1; i<=n; i++)
    
18.                 {
    
19.                         x=c[i][k];
    
20.                         ans+=x;
    
21.                         ans%=20123;  // 基本取个模操作
    
22.                         ///走x下
    
23.                         if (b[i][k]==1) x--;//当前房间有楼梯
    
24.                         while (x>0)
    
25.                                 {
    
26.                                         k++;
    
27.                                         if (k==m)k=0;
    
28.                                         if (b[i][k]==1) x--;
    
29.                                 }
    
30.                         //cout<<i<<' '<<k<<' '<<endl;
    
31.                 }
    
32.         cout<<ans;
    
33. }

复制代码

admin

想到了没有必要转x下，同余思想，假设该层共有s个有楼梯的房间 那么第x个房间应该是等价于x%s个房间，但是又有一个隐患，x%s可能等于0，这里再次特判，把x%s 的值域[0..s-1]映射到[1..s]。

1. x%=s[i];if (x==0) x=s[i];

复制代码

加上统计s 的程序，完整程序如下：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int mm=110,mn=10100;
   
4. int m,n;
   
5. int b[mn][mm],c[mn][mm],s[mn];
   
6. int i,j,k;
   
7. int ans,x;
   
8. int main()
   
9. {
   
10.         cin>>n>>m;
    
11.         for (i=1; i<=n; i++)
    
12.                 for (j=0; j<=m-1; j++)
    
13.                         {
    
14.                                 cin>>b[i][j]>>c[i][j];
    
15.                                 s[i]+=b[i][j];
    
16.                         }
    
17. 
    
18.         cin>>k;
    
19.         ans=0;
    
20.         for (i=1; i<=n; i++)
    
21.                 {
    
22.                         x=c[i][k];
    
23.                         ans+=x;
    
24.                         ans%=20123;  // 基本取个模操作
    
25.                         x%=s[i];
    
26.                         if (x==0) x=s[i];
    
27.                         ///走x下
    
28.                         if (b[i][k]==1) x--;//当前房间有楼梯
    
29.                         while (x>0)
    
30.                                 {
    
31.                                         k++;
    
32.                                         if (k==m)k=0;
    
33.                                         if (b[i][k]==1) x--;
    
34.                                 }
    
35.                         //cout<<i<<' '<<k<<' '<<endl;
    
36.                 }
    
37.         cout<<ans;
    
38. }

复制代码

至此，AC！

admin

此题有好几个坑，当前房间有楼梯的话要注意，取余得0的时候也要注意，这些细节，不是1-2个题可以训练得到的，同学们，要认真多做题呀！哪怕是简单题，万一某个大题里面有这么一个细节，0起步问题，我们是不是就阴沟里翻船了？

admin

当前房间有楼梯可以把房间指针往前挪一个然后再统计，但是依然不能避免特判。
x%s==0 可以改写成x=(x%s)+s，这样会多算几次。
总之，这题的特例情况要认真考虑吧，否则就是各种翻车！