专栏文章

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

MMaxmilite管理员
B4249题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipvho4c
此快照首次捕获于
2025/12/03 18:37
3 个月前
此快照最后确认于
2025/12/03 18:37
3 个月前
查看原文

[语言月赛 202503] 洗牌 题解

Source & Knowledge

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

文字题解

Alice 记住了一摞 2n2n 张扑克牌的初始顺序，并知道 Bob 采用特定的洗牌方式。我们需要还原 Bob 洗牌后的结果，然后按交替发牌规则确定 Alice 拿到的牌，并输出这些牌的顺序。
首先处理输入部分。其主要难点在于带逗号的字符串的处理，即，将带逗号的字符串以逗号为分界切成若干牌。
我们假设读入的带逗号字符串为 ss。这里提供两种方式，分别代表普通方法和利用 C++ string 的方法。
普通方法 考虑从前到后遍历 ss 中的每个字符 cc。过程中使用一个 string tmp 临时存储某个牌。当 cc 不为逗号，则将 cc 塞入 tmp 之后；当 cc 为逗号，则认为此时的 tmp 是一个完整的牌，将其存入需要的地方。
CPP
// 假设我们使用 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 的子字符串，作为这个函数的返回值。
对于这道题目而言，我们可以截取 2n2n 次字符串。过程中使用一个 cur 变量，记录上一次截取截到了哪里。每一次截取时，我们找 nxt = s.find(',', cur)，则 s.substr(cur, nxt - cur) 则为需要的结果。
CPP
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;
}
整个输入部分可做如下处理：
CPP
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∼2ni= 1 \sim 2n 的 for 循环，每次判断 f[i] == 'L' 或 f[i] == 'R'，并从对应的牌堆中取牌放入 b[] 即可。
CPP
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 拿到的牌，使用一个步长为 22 的 for 循环输出即可。
CPP
for (int i = 1; i <= 2 * n; i += 2) {
    cout << b[i] << endl;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...