自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:18:07，当前版本为作者最后更新于2025-03-19 17:58:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[语言月赛 202503] 洗牌 题解

Source & Knowledge

本题来源于 2025 年 3 月的语言月赛，涉及字符串的简单运用。

文字题解

Alice 记住了一摞 $2n$ 张扑克牌的初始顺序，并知道 Bob 采用特定的洗牌方式。我们需要还原 Bob 洗牌后的结果，然后按交替发牌规则确定 Alice 拿到的牌，并输出这些牌的顺序。

首先处理输入部分。其主要难点在于带逗号的字符串的处理，即，将带逗号的字符串以逗号为分界切成若干牌。

我们假设读入的带逗号字符串为 $s$。这里提供两种方式，分别代表普通方法和利用 C++ string 的方法。

普通方法 考虑从前到后遍历 $s$ 中的每个字符 $c$。过程中使用一个 string tmp 临时存储某个牌。当 $c$ 不为逗号，则将 $c$ 塞入 tmp 之后；当 $c$ 为逗号，则认为此时的 tmp 是一个完整的牌，将其存入需要的地方。

// 假设我们使用 string 数组 a 来存储所有的牌
string a[205]; // n 最大为 100，共有 2n 张牌
int cnt = 0; // cnt 表示目前已经存储了多少张牌

...

// 假设带逗号字符串为 s
cin >> s;
string tmp;
for (int i = 0; i < s.length(); i++) {
    char c = s[i];
    if (c != ',') {
        tmp += c;
    } else {
        ++cnt;
        a[cnt] = tmp;
        tmp = "";
    }
}
// 将最后一个牌存好，因为最后一个牌后没有逗号
++cnt; 
a[cnt] = tmp;

string 方法 使用 string 的 find() 方法和 substr() 方法。下简单介绍二者的使用方法：

• s.find(c, pos)：查找字符。从 string s 的第 pos（从 0 开始）位出发，找 c 字符出现的第一个位置，返回这个位置的下标。
• s.substr(pos, n)：截取子字符串。从 string s 的第 pos 位开始截取，截取出长度为 n 的子字符串，作为这个函数的返回值。

对于这道题目而言，我们可以截取 $2n$ 次字符串。过程中使用一个 cur 变量，记录上一次截取截到了哪里。每一次截取时，我们找 nxt = s.find(',', cur)，则 s.substr(cur, nxt - cur) 则为需要的结果。

int cur = 0;
for (int i = 1; i <= 2 * n; i++) {
    int nxt = s.find(',', cur);
    a[i] = s.substr(cur, nxt - cur);
    cur = nxt + 1;
}

整个输入部分可做如下处理：

char f[205];
int n;
string a[205];
string l[105], r[105]; // 分为左右两摞
cin >> n;
string s;
cin >> s;

// 用任意一种上面提到的方法处理 s

for (int i = 1; i <= n; i++) l[i] = a[i];
for (int i = 1; i <= n; i++) r[i] = a[i + n];

for (int i = 1; i <= 2 * n; i++) {
    cin >> f[i];
}

之后考虑洗牌。为了方便处理，我们在读入部分将牌分为了 l[], r[] 两个堆。我们可以使用 int lcnt, rcnt 代表当前已经从 l[] 和 r[] 中拿了几张牌。

我们另开 string b[205] 用于存储洗好的牌（同样按照从顶到底的顺序）。在洗牌时，我们不断地往 b 的顶部摞牌，因此越早放入的牌越应当在底部，整体的摞牌顺序应当是从底到顶，即 b[2 * n], b[2 * n - 1], ..., b[2], b[1]。

由此，我们可以做一个 $i= 1 \sim 2n$ 的 for 循环，每次判断 f[i] == 'L' 或 f[i] == 'R'，并从对应的牌堆中取牌放入 b[] 即可。

for (int i = 1; i <= 2 * n; i++) {
    if (f[i] == 'L') {
        ++lcnt;
        b[2 * n - (i - 1)] = l[lcnt];
    }
    if (f[i] == 'R') {
        ++rcnt;
        b[2 * n - (i - 1)] = r[rcnt];
    }
}
// 2 * n - (i - 1) 这个公式在 i = 1, 2, 3... 时，
// 分别等于 2 * n (- 0), 2 * n - 1, 2 * n - 2, ...

最后的输出部分，b[1], b[3], b[5], ... 为 Alice 拿到的牌，使用一个步长为 $2$ 的 for 循环输出即可。

for (int i = 1; i <= 2 * n; i += 2) {
    cout << b[i] << endl;
}