题解归档 - cf104118K

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118K
• 本地来源：problems/cf104118K/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/K
• 原始标题：Gym 104118K - Kapitan Amazing

思路

Gym 104118K - Kapitan Amazing

The oily keys are exactly the letters that appear in the password:

• every oily key must appear at least once;
• no non-oily key may appear.

So each query is possible iff the set of distinct letters in the query equals the set of * positions on the keyboard.

Complexity: O(total query length).

Checks:

• official sample 1
• statement sample 2 reconstructed from PDF logic

代码

来源：problems/cf104118K/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> key(3);
    cin >> key[0] >> key[1] >> key[2];

    string layout[3] = {"QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"};
    int target = 0;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < (int)key[i].size(); ++j) {
            if (key[i][j] == '*') target |= 1 << (layout[i][j] - 'A');
        }
    }

    int q;
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        int got = 0;
        for (char ch : s) got |= 1 << (ch - 'A');
        cout << (got == target ? "POSSIBLE" : "IMPOSSIBLE") << '\n';
    }
    return 0;
}