华师一附中OI组

标题: P1076 寻宝 [打印本页]
作者: admin    时间: 2018-6-28 14:47
标题: P1076 寻宝
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    时间: 2021-4-11 19:49
这几乎是个纯粹的模拟题，只是需要用到一点%的简单知识，但是读懂题意不是件容易事，有些同学居然还不能模拟出样例，这就很为难了，我们先看看样例，
作者: admin    时间: 2021-4-12 10:10
先来一个硬模拟，完全按照题意，以一楼进入的那个房间开始，逆时针数硬数相应个有楼梯的房间。
用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    时间: 2021-4-12 10:16
因为没有考虑题目中的“如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。”。我第一次做的时候也没有考虑到这个，看来读题目很重要！！这种感觉只能在多做题过程中去积累，因为当前房间可能有楼梯，于是加上一句特判。
  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];

  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    时间: 2021-4-12 10:25
想到了没有必要转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.                         }

  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    时间: 2021-4-12 10:28
此题有好几个坑，当前房间有楼梯的话要注意，取余得0的时候也要注意，这些细节，不是1-2个题可以训练得到的，同学们，要认真多做题呀！哪怕是简单题，万一某个大题里面有这么一个细节，0起步问题，我们是不是就阴沟里翻船了？
作者: admin    时间: 2021-4-12 10:33
当前房间有楼梯可以把房间指针往前挪一个然后再统计，但是依然不能避免特判。
x%s==0 可以改写成x=(x%s)+s，这样会多算几次。
总之，这题的特例情况要认真考虑吧，否则就是各种翻车！



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2