题解：P15647 [ICPC 2022 Tehran R] Magic with Cards

AI_god · 2026-03-09 06:58:10 · 题解

思路

BFS，因为总共就 2\times n 种状态。

对于每个位置都可以产生两种分支（交错洗牌，对调洗牌）。

对于交错洗牌：

• 若 x \le n，则下一个位置是 2\times x-1；
• 若 x>n，则下一个位置是 (x-n)\times2。

对于对调洗牌：

• 若 x 为偶数，则下一个位置是 x-1；
• 若 x 为奇数，则下一个位置是 x+1。

注意用 BFS 不要习惯用成 DFS，其次有很多细节需要注意，本题可以先不判断下一个位置是否走过，只用在每个位置开始时判断一下即可。

复杂度 O(n)，因为 BFS 每个位置至多只会走一遍。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,x,y;
ll vis[200005];
ll flag=0;
void bfs(){
    queue<ll>qx,qd;
    qx.push(x),qd.push(0);
    while(!qx.empty()){
        ll x=qx.front(),d=qd.front();
        qx.pop(),qd.pop();
        if(vis[x]==0){
            vis[x]=1;
            if(x==y){
                cout<<d<<endl;flag=1;break;
            }
            if(x<=n)qx.push(x*2-1),qd.push(d+1);
            else qx.push((x-n)*2),qd.push(d+1);
            if(x%2==0)qx.push(x-1),qd.push(d+1);
            else qx.push(x+1),qd.push(d+1);
        }
    }
    return ;
}
int main(){
    cin>>n>>x>>y;
    bfs();
    if(flag==0)cout<<"-1"<<endl;
    return 0;
}