P14091 [ICPC 2023 Seoul R] Magic Cards

Solution

题目链接: P14091 [ICPC 2023 Seoul R] Magic Cards

难度:普及/提高-

题面:

Chansu and Junsu are friends in International College of Programming Convergence. One day, Chansu met Junsu and said that “I’ll do a magic trick for you. Pick any number between $1$ and $12$, and don’t tell me your number. Just keep it in your mind.” Junsu chose $11$ in mind. Chansu then showed Junsu the following four cards one by one, asking “Is there your number in this card?” at each time.

So, Junsu answered “Yes, yes, no, yes” in this order. After Chansu did some magically looking gestures with his arms and legs for a while, he finally shouted, “I’ve got your number. It is $11$.” And Junsu was quite
surprised because it was exactly the number he kept in mind.

Chansu didn’t tell Junsu the secret of the trick, but only “These cards have a great magic power, so they can read your mind and tell me something only in a magical language, which only I can understand.”

How does this work? Can you figure out the secret?

Now, you are to write a program that answers the number in your friends’ minds. We can generalize the magic trick as follows: You have $K$ magic cards in each of which exactly $M$ integers between $1$ and $N$, possibly with
some redundancy, are written, and you perform the magic trick to $F$ friends. From the yes/no-sequences from the $F$ friends, you will be able to pick out the correct numbers.

输入格式

Your program is to read from standard input. The input starts with a line containing four integers, $N,K,M$, and $F$ ($1\le N\le 500,000,1\le K\le 100,1\le M\le 5,000,1\le F\le 50,000$). In each of the following $K$ lines, there are $M$ integers between 1 and $N$, which represent the $M$ numbers written in each magic card. In each of the following $F$ lines, you are given a string of length $K$ over { Y , N } \{\texttt Y, \texttt N\} {Y,N}, which represents the answer of each friend such that a $\text{Y}$ means a “yes” and an $\text{N}$ means a “no”. You can assume that all the answers from the
friends are correctly given according to their numbers chosen in mind.

输出格式

Your program is to write to standard output. Print exactly $F$ lines. For each $i=1,2,\dots ,F$, the $i$-th line should consists of the number in the $i$-th friend’s mind. If it is impossible to identify the one and only number of the $i$-th friend, print out 0 in the $i$-th line.

输入输出样例 #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

题意:我们有n张卡片,每张卡片上面都是一组数字,然后根据每个询问的人对每张卡片说的答案(Y代表这组数字里里含有那个数字),给出他心里想的数字,如果不能确定,或者有多个数字可能则返回0

下面是本题的几点思路分析 o(=•ェ•=)m：

1. 题目给出的数据非常大,可以考虑使用 trie(字典树) 解决,它可以快速查询是否存在该状态,时间复杂度为 O(n)

2. 我们可以把每一张卡片当作是一个状态 mask,那么我们可以得到 F 个状态,将他们插入字典树中,由于可能存在一种情况是有多个数字状态相同,因此我们把在每一个的卡片状态相同的索引加入在 ed 中,如果最后 ed 数组中的大小大于1,那么就证明存在多个有可能的数, 于是返回 0, 如果等于1,那就说明可以唯一确定一个数,直接返回 ed.back()即可.

3. 对于每一个查询,将其对每个卡片状态的回答,查询是否有一致状态卡片,如果存在相同的状态,那么就返回结尾位置

4. 在本题中其实是想要得到一个数字在每个卡片中的 存在状态 与查询一致,对于字典树来说,如果存在一个数字在每个卡片中的存在状态与查询一致的,那么从根节点开始必然会有一条路到结尾节点,因此返回尾节点索引

---

字典树的定义

下图是借用 OI-WIKI 上的图

字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子, 1 → 4 → 8 → 12
表示的就是字符串 caa。

插入字符串进入字典树的操作:

void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = true;
  }

---

查询字符串进入字典树的操作:

bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
}

---

Code

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int MAXN = 5e7;
int trie[MAXN][2], cnt;
vector<int> ed[MAXN];

void insert(string &s, int idx)
{
    int p = 0;
    for (char ch : s)
    {
        int c = (ch == 'Y');
        if (!trie[p][c])
        {
            trie[p][c] = ++cnt;
        }
        p = trie[p][c];
    }

    ed[p].push_back(idx);
}

int query(string &s)
{
    int p = 0;
    for (char ch : s)
    {
        int c = (ch == 'Y');
        if (!trie[p][c])
        {
            return 0;
        }
        p = trie[p][c];
    }
    return ed[p].size();
}

void solve()
{
    int N, K, M, F;
    cin >> N >> K >> M >> F;

    vector<string> card(N + 1, string(K, 'N'));
    for (int j = 0; j < K; ++j)
    {
        for (int t = 0; t < M; ++t)
        {
            int x;
            cin >> x;
            card[x][j] = 'Y';
        }
    }

    for (int i = 1; i <= N; ++i)
    {
        insert(card[i], i);
    }

    for (int i = 0; i < F; ++i)
    {
        string s;
        cin >> s;

        int x = query(s);
        cout << (x == 1 ? ed[x][0] : 0) << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}****

ps: 作为一个蒟蒻写的题解,如果有什么错落,恳请各位大佬在评论区不吝赐教 orz ༼ つ ◕_◕ ༽つ

附一个卖萌的 gif: