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

dlc666 · 2026-03-08 13:48:46 · 题解

题意

有一副共 2n 张牌的牌堆，有两种洗牌方式。

• Riffle（交错洗牌）： 将牌分成两部分 \langle c_{1}, \ldots, c_{n} \rangle 和 \langle c_{n+1}, \ldots, c_{2n} \rangle，然后产生 \langle c_{1}, c_{n+1}, c_{2}, c_{n+2}, \ldots, c_{n}, c_{2n} \rangle。
• Scuffle（对调洗牌）： 从 \langle c_{1}, c_{2}, \ldots, c_{2n} \rangle 产生 \langle c_{2}, c_{1}, c_{4}, c_{3}, \ldots, c_{2n}, c_{2n-1} \rangle。

现选择牌堆中的两个位置 i 和 j，问将第 i 张牌带到第 j 个位置所需的最少洗牌次数。如果洗不到输出 -1。

思路

注意到 1 \leq n \leq 10^{5}，数据范围较小，可以直接使用广度优先搜索解决。
对于每个位置，都分别用两种洗牌方法试一试。但注意要加上记忆化，否则会死循环。
由于使用的是广搜，当找到目标位置 j 时直接输出洗牌次数即可，一定是最优洗牌次数。当搜完后仍没有到达 j，输出 -1。
完毕！好题。

代码

#include<bits/stdc++.h>
using namespace std;
struct gyy{
    int a,k;//a是当前牌的位置，k是到达当前牌的洗牌次数 
}c;
//c用于插入数据 
int n,i,j;
bool memory[200005];//记忆化 
queue<gyy>s;//BFS队列
int riffle(int x){//交错洗牌 
    if(x<=n){
        //前半堆变化：x+(x-1) 自己的位置x前面加了x-1个数 
        return x+x-1; 
    }else{
        //后半堆变化：2*(x-n) 第x-n组的后一个 
        return 2*(x-n);
    }
}
int scuffle(int x){//对调洗牌 
    if(x%2==0){
        //偶数位置往前调1 
        return x-1;
    }else{
        //奇数位置往后调1 
        return x+1;
    }
}
int main(){
    cin>>n>>i>>j;
    if(i==j){//特判已到 
        cout<<0;
        return 0;
    }
    memory[i]=1;
    c.a=riffle(i);c.k=1;
    memory[c.a]=1;
    s.push(c);
    c.a=scuffle(i);c.k=1;
    memory[c.a]=1;
    s.push(c);
    while(!s.empty()){
        int num=s.front().a,kk=s.front().k;
        if(num==j){//到了就输出洗牌次数 
            cout<<kk;
            return 0;
        }
        c.a=riffle(num);c.k=kk+1;
        if(memory[c.a]==0){//记住：只搜没搜过的 
            memory[c.a]=1;
            s.push(c);
        }
        c.a=scuffle(num);c.k=kk+1;
        if(memory[c.a]==0){
            memory[c.a]=1;
            s.push(c);
        }
        s.pop();
    }
    cout<<-1;//洗不到输出-1 
    return 0; 
}