洛谷-P1563-玩具谜题

科技前沿 • 2025-04-02 12:53 • 阅读 25

大家好，我是讯享网，很高兴认识大家。

[NOIP2016 提高组] 玩具谜题 - 洛谷

视频讲解：玩具谜题_哔哩哔哩_bilibili

解题思路：

1.由题可知，每个玩具小人有两个属性，一个是朝向，另一个是名字，所以可以想到结构体变量设置两个属性变量int fx;string name;

2.首先分析情况，每条指令和小人的朝向与向左向右的方向关联，无外乎就是4种情况，即小人朝内向左数数，小人朝内向右数数，小人朝外向左数数，小人朝外向右数数，不会有其他的情况发生

3.然后看图分析小人的排队顺序，发现是逆时针排队的，编号从小到大，那么编号的变化无外乎两种情况，一种是逐个增加，要不就是逐个减少，因为形成了环状，所以会想到约瑟夫环状

讯享网

4.接下来利用循环先将结构体两个变量依次输入存储，然后创建循环，输入m条指令，每条指令有两个数，设为x和y，x表示朝向，y表示人数，那么当x=0,小人的朝向也是0的话，发现编号是顺时针移动，即编号依次减小，如果编号为0的话，让他变成n，形成环状，当x=0小人的朝向是1的话，编号是依次增加的，如果编号超出n，让他回到1，所以问题也就迎刃而解了，最后输出书签的名字即为结果

5.但是这种做法当数据量大的时候会超时，所以想到，如何不用循环，通过计算来节省时间，通过推导，如果编号增加的话利用模运算temp=(temp+n)%n,如果编号减少的话temp=(temp-y+n)%n,temp初始化为0，方便取余运算

代码实现（70分）

#include<bits/stdc++.h> using namespace std; struct people{ int fx; string name; }a[];//表示每个人的朝向和名字 int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i].fx>>a[i].name; int x,y;//分别表示每条指令的方向和人数 int temp=1;//书签表示当前位置 for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(x==0&&a[temp].fx==0)//如果这个人朝向圈内并且向左数数 { while(y--) { temp--;//书签递减 if(temp==0) temp=n;//如果等于0，让他回到n，形成环状 } } else if(x==0&&a[temp].fx==1)//如果这个人朝圈外并且向左数数 { while(y--) { temp++;//书签递增 if(temp==n+1) temp=1;//如果超出n，回到1，形成环状 } } else if(x==1&&a[temp].fx==0)//如果这个人朝圈内并且向右数数 { while(y--) { temp++;//书签递增 if(temp==n+1) temp=1;//如果超出n，回到1，形成环状 } } else//如果这个人朝圈外并且向右数数 { while(y--) { temp--;//书签递增 if(temp==0) temp=n;//如果超出n，回到1，形成环状 } } } cout<<a[temp].name; }

讯享网

代码实现（100分）

讯享网#include<bits/stdc++.h> using namespace std; struct people{ int fx; string name; }a[];//表示每个人的朝向和名字 int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++)//下标0开始存储，方便模运算 cin>>a[i].fx>>a[i].name; int x,y;//分别表示每条指令的方向和人数 int temp=0;//书签表示当前位置 for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(x==0&&a[temp].fx==0)//如果这个人朝向圈内并且向左数数 temp=(temp+n-y)%n; else if(x==0&&a[temp].fx==1)//如果这个人朝圈外并且向左数数 temp=(temp+y)%n; else if(x==1&&a[temp].fx==0)//如果这个人朝圈内并且向右数数 temp=(temp+y)%n; else//如果这个人朝圈外并且向右数数 temp=(temp+n-y)%n; } cout<<a[temp].name; }

洛谷-P1563-玩具谜题

相关推荐