P7210 [COCI2020-2021#3] Vlak 题解

RegisterFault · 2023-10-18 20:52:58 · 题解

根据题意，由于单词需要是歌曲列表中的前缀，所以可以建出 Trie 树，在树上进行搜索。

将 Nina 的歌曲列表树记为 N，Emilija 的记为 E。当前节点在 N 上为 p 号节点，在 E 上为 q 号节点。下面分几种情况讨论：

• 当前该 Emilija 走，p 没有儿子。返回 Nina 赢。

• 当前该 Nina 走，p 有儿子 v 而 q 没有。Nina 赢。

• 当前该 Nina 走，p, q 都有儿子 v。往 v 儿子走有 Nina 的必胜策略。Nina 赢。

  如果这三种情况都没有，则返回 Emilija 赢。

  对于 Emilija 的情况，反之亦然。

  参考代码使用指针写法。

#include <iostream>
#include <cstring>

using namespace std;

string s; int n, m;
struct node {
    node *s[26]; bool ed;
    node() {
        for (int i = 0; i < 26; i ++ )
            s[i] = NULL;
        ed = false;
    }
}*root1, *root2;
void insert(node *p, string s) {
    node *u = p; 
    for (auto i : s) {
        int v = i - 'a';
        if (u -> s[v] == NULL) u -> s[v] = new node();
        u = u -> s[v]; u -> ed = false;
    } u -> ed = true;
}
bool dfs(node *p, node *q, int u) {
    if (u == 0 and p -> ed) return 1;
    if (u == 1 and q -> ed) return 0;
    if (u == 0) {
        for (int i = 0; i < 26; i ++ ) {
            if (p -> s[i] == NULL) continue;
            if (q -> s[i] == NULL) return 0;
            if (!dfs(p -> s[i], q -> s[i], u ^ 1)) return 0;
        } return 1;
    } else {
        for (int i = 0; i < 26; i ++ ) {
            if (q -> s[i] == NULL) continue;
            if (p -> s[i] == NULL) return 1;
            if (dfs(p -> s[i], q -> s[i], u ^ 1)) return 1;
        } return 0;
    }
}
int main() {
    root1 = new node(); root2 = new node();
    ios::sync_with_stdio(false); 
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    while (n -- ) cin >> s, insert(root1, s);
    cin >> m;
    while (m -- ) cin >> s, insert(root2, s);
    if (!dfs(root1, root2, 0)) puts("Nina");
    else puts("Emilija"); return 0;
}