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

ElysiaTruE · 2026-03-07 20:19:44 · 题解

首先要求把第 i 张牌洗牌到第 j 个位置，那么我们就忽略其他位置的牌，只看第 i 张牌洗牌后的位置。

由于有加减 1 的操作，把下标从 1 开始改为下标从 0 开始，这样可以直接用异或。

于是题目中的两种操作就转换为了：

• 将第 i 张牌放到第 \lfloor\frac{i}{n}\rfloor+2\times(i\bmod n) 个位置。
• 将第 i 张牌放到第 i\oplus1 个位置。

由于要求最小操作次数，可以 BFS 解决。代码非常短。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
int q[200005],ans[200005],h=1,t=1;
bool vis[200005];
int main(){
    int n,a,b;
    cin>>n>>a>>b;
    q[1]=a-1;
    vis[a-1]=1;
    while(h<=t){
        int x=q[h++];
        if(!vis[x%n*2+x/n])q[++t]=x%n*2+x/n,vis[x%n*2+x/n]=1,ans[x%n*2+x/n]=ans[x]+1;
        if(!vis[x^1])q[++t]=x^1,vis[x^1]=1,ans[x^1]=ans[x]+1;
    }
    cout<<(vis[b-1]?ans[b-1]:-1);
}

:::