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

lsixuan · 2026-03-08 13:53:38 · 题解

思路：

这道题的本质是 BFS 找最短路径，核心是把洗牌操作转化为位置变换公式，再用 BFS 逐层探索，找到从初始位置到目标位置的最少步数。

通过观察，我们发现：

交错洗牌：

• 前 n 张牌的新位置为 2 \times x+1；

• 后 n 张牌的新位置为 2 \times (x-n)；

对调洗牌：

• 若 x 是奇数，新位置为 x+1;

• 若 x 是偶数，新位置为 x-1;

弄懂公式后套 BFS 模版即可，不会的请移步至模版题。

注意，当 i=j 时需要特判为 0，数组空间开 2n。

Code：

#include<bits/stdc++.h>
using namespace std;
int n,i,j;
struct node{int x,y;};
queue<node> q;
bool vis[200005];
int Riffle(int x){
    if(x<=n) return x*2-1;
    return (x-n)*2;
}
int Scuffle(int x){
    if(x%2==1) return x+1;
    return x-1;
}
signed main(){
    cin>>n>>i>>j;
    if(i==j){
        cout<<"0"<<endl; return 0;
    }
    // bfs 部分
    q.push({i,0}); vis[i]=1;
    while(!q.empty()){
        node no=q.front(); q.pop();
        int pos=no.x,step=no.y;
        int ans1=Riffle(pos),ans2=Scuffle(pos);
        if(ans1==j){
            cout<<step+1<<endl; return 0;
        }
        if(!vis[ans1]){
            vis[ans1]=1;
            q.push({ans1,step+1});
        }
        if(ans2==j){
            cout<<step+1<<endl; return 0;
        }
        if(!vis[ans2]){
            vis[ans2]=1;
            q.push({ans2,step+1});
        }

    }
    // 所有可能都试完了，无法实现
    cout<<"-1"<<endl;
    return 0;
}