B4249 [语言月赛 202503] 洗牌 题解

Maxmilite · 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;
}