题解：B4138 [信息与未来 2016] 洗牌

Tarjan97 · 2026-07-23 23:02:21 · 题解

先理解题意：本题要求进行 k 次的操作，每次将这堆牌分成两堆交叉插入。

本题数据范围较小，属于一道模拟题。首先输入 n,k,i，接着进行 k 次操作，每次将牌分成两堆交叉插入，最后输出第 i 个位置的元素。

满分代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,x,a[1010],b[1010];
int main(){
    cin>>n>>k>>x;//此处的x为题目中的i
    m=n/2;//题目描述中的m
    for(int i=1;i<=n;i++)a[i]=i;//初始化
    while(k--){//k次操作
        memcpy(b,a,sizeof(b));//将a数组复制给b数组
        for(int i=1;i<=m;i++){
            a[i*2-1]=b[i];//处理前面m个元素
        }
        for(int i=1;i<=m;i++){
            a[i*2]=b[i+m];//处理后面m个元素
        }
    }
    cout<<a[x];//答案
    return 0;
}

注意一下这一行：

for(int i=1;i<=m;i++){
    a[i*2-1]=b[i];
}

如果在原数组 a 上进行计算，有的值会被覆盖，导致计算错误（直接0分），第一个用例对不了，但第二个用例能对，所以不要只测看起来数据大的用例！！！