P1563【NOIP2016】玩具谜题

difficultlong · 2024-09-21 22:26:32 · 题解

题目传送门

思路

关键：

方向、朝向

请观察此表：

可以发现：

• 如果方向与朝向不同，则为逆时针方向。
• 如果方形与朝向相同，则为顺时针方向。

这很像异或的性质！

所以，我们可以用异或（ 位运算 ）来做！

异或运算符^是一个二进制操作符，它执行位级别的异或操作。异或运算的基本规则是：相同为0，相异为1。

所以，我们可以用 a 数组记录朝向，并写一个临时的 x y 分别表示方向，距离。

在读入之后

设 L 为当前的小人序号，则判断条件为：

if(x^a[L]==0){//也可以写!(x^a[L]) ,这是方向与朝向相同的情况 
    //填写操作步骤 
}
else{//就是x^a[L]==1 ,这是方向与朝向不同的情况 
    //填写操作步骤 
}

注意，在寻找眼镜时，是从1号小人开始的,那么我们的起始位置就需要设为1！

在这里，我们将起始位置设为 L 。

但是问题来了，如果 L+y\le n 或者 L-y\geq1 都好说，

可是偏偏作者愿意给我们找点事干。

• 此时 n=7 ，-1+7=6，由于小人是围成的一个圆圈，所以大家可以（妙不可言）发现，此时就是移动后的序号！

注： m 指的是有 m 条指令，用 for 循环来读入每一条指令。

for(int i=1;i<=m;i++){//从第一条指令开始一直到第m条指令 
    int x,y;//定义方向为x，移动的距离为y
    cin>>x>>y;
    if(x^a[L]==0){//朝向与方向相同的情况 
        L-=y;//顺时针方向就要将号数减少
        if(L<=0){//出现特殊情况 
            L+=n;
        }
    } 
    else{//朝向与方向不同的情况 
        L+=y;//逆时针方向就要将号数增加
        if(L>n){//出现特殊情况 
            L%=n;
        }
    } 
}

好的，如果你能看到这里，那么你已经超过了99.9%的人！

好吃的陷阱

范围这是一个令人值得思考的问题。

在特判中，一定要判断好准确的范围，否则，你提交程序，立地成佛！

• 比如在特判时，if语句中的条件 L 一定要大于 n （ >n ），而不是大于等于 n ( \geq n )。

• 同样的，在特判中 if 语句中的条件 L 一定是小于等于0( \le 0 ），而不是小于0（ < 0）。

来了，他来了，曾经听取WA声一片AC的代码走来了

#include<bits/stdc++.h>
using namespace std;
int a[100001];
string s[100001];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>s[i];
    }
    int L=1;
    for(int i=1;i<=m;i++){//从第一条指令开始一直到第m条指令 
        int x,y;//定义方向为x，移动的距离为y 
        cin>>x>>y;
        if(x^a[L]==0){//朝向与方向相同的情况 
            L-=y;//顺时针方向就要将号数减少
            if(L<=0){//出现特殊情况 
                L+=n;//+n将特殊情况，变为正常 
            }
        } 
        else{//朝向与方向不同的情况 
            L+=y;//逆时针方向就要将号数增加
            if(L>n){//出现特殊情况 
                L%=n;//%n将特殊情况，变为正常 
            }
        } 
    }
    cout<<s[L];
    return 0;
}

附加：

我们想要程序运行的速度变快，该怎么办？ 这里我给大家提供一个速度翻倍，却不动脑筋的方法。

我们可以关掉并解除 cin 和 cout 的同步与绑定，因为这样会浪费时间（主要体现在缓冲区）。

1. 缓冲区同步的等待
2. 缓冲区刷新的时间
3. 绑定的解除

可以保证这样的速度极快，比 scanf 和 printf 还要快一些！

用这两段代码即可：

std::ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);

融合我们的代码之后：

#include<bits/stdc++.h>
using namespace std;
int a[100001];
string s[100001];
int main(){
    std::ios_base::sync_with_stdio(false);//解除同步、绑定
    //与printf scanf的绑定
    cin.tie(0);cout.tie(0);//优化cin、cout（缓冲区）
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>s[i];
    }
    int L=1;
    for(int i=1;i<=m;i++){//从第一条指令开始一直到第m条指令 
        int x,y;//定义方向为x，移动的距离为y 
        cin>>x>>y;
        if(x^a[L]==0){//朝向与方向相同的情况 
            L-=y;//顺时针方向就要将号数减少
            if(L<=0){//出现特殊情况 
                L+=n;//+n将特殊情况，变为正常 
            }
        } 
        else{//朝向与方向不同的情况 
            L+=y;//逆时针方向就要将号数增加
            if(L>n){//出现特殊情况 
                L%=n;//%n将特殊情况，变为正常 
            }
        } 
    }   
    cout<<s[L];//输出最后L指向的位置
    return 0;
}