洛谷-P1563-玩具谜题

[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
using namespace std;
struct people{int fx;string name; 
}a[100005];//表示每个人的朝向和名字 
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<

#include
using namespace std;
struct people{int fx;string name; 
}a[100005];//表示每个人的朝向和名字 
int main()
{int n,m;cin>>n>>m;for(int i=0;i>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<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！