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

taozhengkai · 2026-03-08 18:03:12 · 题解

题目理解：

我们有一副 2n 张牌，有两种操作：

1. 交错洗牌（我就不解释了，毕竟题目有）。
2. 对调洗牌。

要把初始在第 i 个位置的牌移动到第 j 个位置，求最少的操作次数，不可能则输出 -1。

解题思路：

1. 只追踪目标牌的位置： 我们不需要模拟整副牌，只需关心目标牌的位置。设当前的位置在 t，经过一次操作后，它会移动到哪个新位置？

对调洗牌操作：

1. 如果 t 是奇数，则它与右边的牌交换，新位置是 t+1。
2. 如果 t 是偶数，则它与左边的牌交换，新位置是 t-1。

公式：

交错洗牌操作：

牌分成两半：

1. 左半部分（位置 1 \sim n）的牌会移到奇数位置。
2. 右半部分（位置 n+1 \sim 2n）的牌会移到偶数位置。

公式：

2. 转化为最短路问题：

将每个位置看作图中的一个节点（共 2n 个节点）。 从位置 t 出发，可以通过一次操作到达 S(t) 或 R(t)。 问题转化为：从节点 i 出发，求到节点 j 的最短路径长度。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,i,j;
int dist[200005];
void bfs(){
    memset(dist,-1,sizeof(dist));//变为-1 
    queue<int>q;//队列 
    q.push(i);//起点入队 
    dist[i]=0; 
    while(!q.empty()){
        int t=q.front();
        q.pop();
        int d=dist[t]+1;
        //scuffle操作 
        int scuffle;
        if(t%2==1){
            scuffle=t+1;
        }
        else{
            scuffle=t-1;
        }
        if(dist[scuffle]==-1){
            dist[scuffle]=d;
            if(scuffle==j){
                cout<<d;
                return;
            }
            q.push(scuffle); 
        }
        //riffle操作 
        int riffle;
        if(t<=n/2){
            riffle=2*t-1;//左半部分 
        }
        else{
            riffle=2*(t-n/2);//右半部分 
        }
        if(dist[riffle]==-1){
            dist[riffle]=d;
            if(riffle==j){
                cout<<d;
                return;
            }
            q.push(riffle);
        }
    }
    cout<<-1;
}
int main(){
    cin>>n>>i>>j;
    n*=2;//牌数变为2n 
    if(i==j){//小小特判一下 
        cout<<0;
        return 0;
    }
    bfs();//广搜 
    return 0;//完美结束 
}