NOIP2012 PJ T2 寻宝

题目描述：https://www.luogu.org/problem/P1076

分析：本题貌似是个暴力模拟，直接按照题目要求做即可。

#include<bits/stdc++.h>
using namespace std;
int a[10005][105];
bool b[10005][105];
int main()
{
	//freopen("treasure.in","r",stdin);
	//freopen("treasure.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<m;j++) scanf("%d%d",&b[i][j],&a[i][j]);//输入不解释
	}
	int x;
	scanf("%d",&x);
	int f=1,ans=0;//f表示当前层数，ans表示密钥
	while(f<=n)
	{
		int s=0,num=a[f][x];//s记录经过楼梯数量，num表示在该层看到的第一个指示牌上的数字
		for(int i=x;;i++)
		{
			if(b[f][i%m]) s++;//该处有楼梯，计数++
			if(s==num)//找到第num个楼梯
			{
				ans=(ans+num)%20123,x=i%m,f++;//累加并取模，记录房间编号，层数++
				break;
			}
		}
	}
	printf("%d",ans);//输出不用再取模了
	return 0; 
}

　　然而，只得了50分。这份代码TLE了。因为在寻找楼梯时，一直在同一层转圈，这样的话就浪费很多时间。我们可以用c[i]记录第i层楼梯的数量，可以避免很多不必要的计算。如下：

#include<bits/stdc++.h>
using namespace std;
int a[10005][105];
bool b[10005][105];
int c[10005];
int main()
{
	//freopen("treasure.in","r",stdin);
	//freopen("treasure.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<m;j++) scanf("%d%d",&b[i][j],&a[i][j]),c[i]+=b[i][j];//记录每层楼梯数量
	}
	int x;
	scanf("%d",&x);
	int f=1,ans=0;
	while(f<=n)
	{
		int s=0,num=(a[f][x]-1)%c[f]+1;//去除重复转圈，注意取模时的特殊处理
		for(int i=x;;i++)
		{
			if(b[f][i%m]) s++;
			if(s==num)
			{
				ans=(ans+a[f][x])%20123,x=i%m,f++;
				break;
			}
		}
	}
	printf("%d",ans);
	return 0; 
}

　　这样就可以AC了。话说当年PJ好难啊。。。