洛谷B4138题解

分析

题意

有 $n$ 张编号为 $1\sim n$ 的牌（$n$ 为偶数），每次洗牌将牌均分为前后两半，然后交叉插入合并（前 $1$、后 $1$、前 $2$、后 $2$……）。重复洗牌 $k$ 次后，求第 $i$ 个位置的牌的编号。

思路

1. 初始化数组存储牌的初始顺序，下标对应牌的位置。
2. 模拟洗牌过程：每次洗牌使用临时数组存储新顺序，按规则从前后两半交替取数。
3. 重复 $k$ 次洗牌操作后，直接输出第 $i$ 个位置的数值即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int ans[N], tmp[N];
int main() {
    int n, k, i;
    cin >> n >> k >> i;
    int m = n / 2;
    for (int j = 1; j <= n; j++) ans[j] = j;
    for (int t = 0; t < k; t++) {
        int pos = 1;
        for (int j = 1; j <= m; j++) {
            tmp[pos++] = ans[j];
            tmp[pos++] = ans[j + m];
        }
        for (int j = 1; j <= n; j++) ans[j] = tmp[j];
    }
    cout << ans[i] << endl;
    return 0;
}