作者:you_only89 | 来源:互联网 | 2023-09-25 20:31
NOIP2012第二题寻宝NOIP2012第二题寻宝考点题意思路代码考点模拟减枝题意原题链接给定一个长度为m环,寻找第i个值为1的节点,重复n次思路一看这道题就是模拟了(一条规
NOIP2012 第二题 寻宝
考点
题意
原题链接给定一个长度为m环,寻找第i个值为1的节点,重复n次
思路
一看这道题就是模拟了(一条规律到底),但是有许多坑点的确让人很难受,m的值很大,还要打个优化,幸好优化不算难打。使用优化后want会等于0,但是不是立刻上楼而是上顺时针第一个。但是在NOIP赛场中没有打上去的话只有70分的点,加上三行优化就30分了。
一幅图了解坑点(我居然还画了图…)
代码
#include
#include
#include
using namespace std;
const int maxfloor=10001;
const int maxroom=101;
int n,m;
int startroom;
struct room_info
{
bool up;
int sign;
};
room_info rooms[maxfloor][maxroom];
int floorstair[maxfloor];
int floor(int floornum,int s)
{
if(floornum==n+1) return 0;
int cnt=0;
int nowroom=s;
int want=rooms[floornum][s].sign;
want=want%(floorstair[floornum]);
if(want==0)
{
want=floorstair[floornum];
}
while(true)
{
if(rooms[floornum][nowroom].up==1)
++cnt;
if(cnt==want)
{
return (floor(floornum+1,nowroom)+rooms[floornum][s].sign)%20123;
}
++nowroom;
if(nowroom==m) nowroom=0;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=0;j {
scanf("%d%d",&rooms[i][j].up,&rooms[i][j].sign);
floorstair[i]+=rooms[i][j].up;
}
}
scanf("%d",&startroom);
printf("%d\n",floor(1,startroom));
return 0;
}