[语言月赛202305F] 你的牌太多了 2 题解

· · 题解

[语言月赛202305F] 你的牌太多了 2 题解

Source & Knowledge

2023 年 5 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考查循环、数组、函数。

文字题解

解析

依据题意模拟即可。

首先可以完成 B3745，我们的基本处理方法与之类似，这里也不再赘述 B3745 题解中出现的变量。

本题的一个难点在于，游戏进行的轮数和每轮游戏的回合数都是不确定的。对于不定长的循环，我们一般用 while 循环来处理。

定义函数 round(x) 表示当先手为 x 时，一轮游戏后下一轮先出牌的人，cnt[0] 表示扶苏的手牌数，cnt[1] 表示小 F 的手牌数。那么，当两人手牌数均不为 0 时，游戏将持续进行。我们采用这样的循环来控制游戏轮数：

while (cnt[0] && cnt[1]) {
  s = round(s);
}

为了便于处理，我们给读入的 s 减去 1。即 s = 0 表示扶苏先出，s = 1 表示小 F 先出。

接下来，我们处理每轮游戏的具体情况：

int round(int st) {
  //...
}

首先找到第一个出牌的人所处的牌，用打擂台的方法：

int id = 1;
while (vis[st][id] == true) ++id;
for (int i = id + 1; i <= n; ++i) if (vis[st][i] == false) {
  if ((p[st][i] < p[st][id]) || ((p[st][i] == p[st][id]) && (f[st][i] < f[st][id]))) {
    id = i;
  }
}

此时需要判断打出这张牌后是否有一方直接胜利：

--cnt[st];
if (cnt[st] == 0) return st;

此外别忘了标记这张牌已被打出。

我们用 plst 和 flst 表示上一张牌的点数和花色。初始时显然有 int plst = p[st][id], flst = f[st][id];。

接下来，我们同样用一个 while 循环来处理每轮游戏的所有回合：

while((id = nextcard(st, flst, plst)) != -1) {
  // do sth
}

在这里，nextcard 是在给出上一张牌的点数和花色、本轮出牌的人以后，返回这次出牌的人所出牌的下标的函数。如果没牌可出，返回 -1，此时这一轮结束，while 循环终止。

nextcard 函数的实现如下：

int nextcard(int st, int flst, int plst) {
  int ret = -1;
  for (int i = 1; i <= n; ++i) if (vis[st][i] == false) {
    if (f[st][i] != flst) continue;
    if (p[st][i] <= plst) continue;
    if (ret == -1) ret = i;
    else {
      if (p[st][i] < p[st][ret]) ret = i;
    }
  }
  return ret;
}

此外，由于实现比较复杂，我们给出 round 函数的内容，用作参考

int round(int st) {
  int id = 1;
  while (vis[st][id] == true) ++id;
  for (int i = id + 1; i <= n; ++i) if (vis[st][i] == false) {
    if ((p[st][i] < p[st][id]) || ((p[st][i] == p[st][id]) && (f[st][i] < f[st][id]))) {
      id = i;
    }
  }
  int plst = p[st][id], flst = f[st][id];
  vis[st][id] = true; --cnt[st];
  if (cnt[st] == 0) return st;
  st = 1 - st;
  while ((id = nextcard(st, flst, plst)) != -1) {
    plst = p[st][id];
    vis[st][id] = true;
    --cnt[st];
    if (cnt[st] == 0) return st;
    st = 1 - st;
  }
  return 1 - st;
}

最后，看一下游戏结束时最后一轮游戏的函数返回值，就能判定谁获得了胜利：

if (s == 1) {
  cout << "FR wins!\n";
} else {
  cout << "FS wins!\n";
}

视频题解