P14091 [ICPC 2023 Seoul R] Magic Cards

题目描述

Chansu 和 Junsu 是国际编程融合学院的朋友。一天，Chansu 遇见 Junsu，并说：“我给你表演一个魔术。你在 $1$ 到 $12$ 之间挑一个数字，不要告诉我，只记在心里。”Junsu 心里选了 $11$。Chansu 随后依次给 Junsu 展示了下图中的四张卡片，每次都问：“你的数字出现在这张卡片中吗？”。

所以，Junsu 按顺序回答了：“是，是，否，是”。Chansu 做了一些神秘的手势和动作后，最终喊道：“我知道你的数字了，是 $11$。”这让 Junsu 非常吃惊，因为这正是他心里想的数字。

Chansu 没有告诉 Junsu 魔术的秘密，只说：“这些卡片有很强的魔法力量，它们能读懂你的心思，并用只有我能明白的魔法语言告诉我一些事情。”

这是如何做到的？你能揭秘这个魔术的原理吗？

现在，你需要编写一个程序，来回答朋友们心中的数字。我们可以将魔术的一般情形归纳如下：你有 $K$ 张魔法卡片，每张卡片上写有恰好 $M$ 个 $1$ 到 $N$ 之间的整数（可能有重复），你要为 $F$ 个朋友表演魔术。通过 $F$ 个朋友对应的“是/否”序列，你要找出他们心中的数字。

输入格式

你的程序需要从标准输入读取数据。输入的第一行包含四个整数 $N,K,M,F$（$1\le N\le 500,000,1\le K\le 100,1\le M\le 5,000,1\le F\le 50,000$）。接下来的 $K$ 行，每行有 $M$ 个 $1$ 到 $N$ 的整数，表示每张魔法卡片上写下的数字。再接下来的 $F$ 行，每行是长度为 $K$ 的只包含 $\text{Y}$ 和 $\text{N}$ 的字符串，表示每个朋友的回答，$\text{Y}$ 代表“是”，$\text{N}$ 代表“否”。你可以假定所有朋友的回答都与他们所选的数字严格对应。

输出格式

你的程序要输出 $F$ 行。对于每个 $i=1,2,\dots ,F$，第 $i$ 行应输出第 $i$ 个朋友心里的数字。如果无法唯一确定某个朋友的数字，则在该行输出 $0$。

输入输出样例 #1

输入 #1

12 4 6 3
1 9 7 11 3 5
2 10 3 6 7 11
4 5 6 7 6 12
8 11 10 9 12 9
YYNY
NNNY
YNNN

输出 #1

11
8
1

输入输出样例 #2

输入 #2

13 4 6 4
1 9 7 11 3 5
2 10 3 6 7 11
4 5 6 7 6 12
8 11 10 9 12 9
YYNY
NNNY
YNNN
NNNN

输出 #2

11
8
1
13

输入输出样例 #3

输入 #3

14 4 6 4
1 9 7 11 3 5
2 10 3 6 7 11
4 5 6 7 6 12
8 11 10 9 12 9
YYNY
NNNY
YNNN
NNNN

输出 #3

11
8
1
0

说明/提示

由 ChatGPT 5 翻译

C++实现

#include <bits/stdc++.h>
using namespace std;
int n, k, m, f;
unordered_map<string, int> mp;
unordered_map<string, int> cnt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k >> m >> f;
    vector<string> v(n + 5, string(k, 'N'));
    for(int j = 0; j < k; j ++)
        for(int i = 0; i < m; i ++) {
            int x;
            cin >> x;
            v[x][j] = 'Y';//这个输入我想了很久，也是我认为最精华的一部分
        }
    for(int i = 1; i <= n; i ++) {
        string s = v[i];
        cnt[s] ++;
        if (cnt[s] == 1)
            mp[s] = i;//没有重复就设为i
        else
            mp[s] = 0;//重复就设为0
    }
    while(f --) {
        string s;
        cin >> s;
        cout << mp[s] << '\n';
    }
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容