CF852G Bathroom terminal 题解

前言

我不理解为什么有人喜欢简单问题复杂化啊啊啊啊啊啊啊啊啊

因为字典树不会写，所以只好写一个搜索水过去。

题意

求 N 个由字母 a 到 e 组成的字符串（单词串）与一些包含 ? 的模式串的匹配个数。每一个 ? 匹配 a 到 e 的字母或者空字符。

分析

根据题目数据分析，最多有 3 个 ?，所以对于每一个模式串，与之匹配的单词串最多由 6^3 = 216 个；考虑到 M 最大为 5000，暴搜绰绰有余。

所以只需要对每一个模式串进行深搜，枚举所有可能的情况，进行判断即可。

解决

考虑使用 multiset 维护单词串的集合，set 维护搜索到的所有匹配串的集合（其实也可以用 map）。

（但是因为我们校内模拟赛打了这道题，时限 1 秒，可以使用效率在大多数情况下更优的 unordered_set 来维护所有匹配串的集合）

不过要特别注意，在考场上测试随机数据时发现，对于多次相同且几乎所有单词串都匹配的情况下，可以硬生生把你卡到 12 秒左右。因此，可以使用 unordered_map 存储每一次询问，重复时取出。

完整代码如下：

#include <iostream>
#include <string>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define FILE_OPEN(filename) \
    freopen(filename".in", "r", stdin); \
    freopen(filename".out", "w", stdout);


using std::string;
using std::set;
using std::cin;
using std::multiset;
using std::unordered_set;
using std::unordered_map;

string mode_s;
string target_s;
unordered_set<string> all_status;
multiset<string> target_strs;
unordered_map<string, int> ans_rec;

void dfs(const string &s) noexcept
{
    string b;
    int i, j, cnt = 0;
    int lens = s.length();
    for (i = 0; i < lens; i++) {
        if (s[i] == '?') {
            cnt++;
            b = s;
            b.erase(i, 1);
            dfs(b);
            b = s;
            for (j = 'a'; j <= 'e'; j++) {
                b[i] = j;
                dfs(b);
            }
        }
    }
    if (!cnt) {
        all_status.insert(s);
    }
}

int n, m;
int i, j;
int ans;

int main() noexcept
{
    FILE_OPEN("game");
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) {
        cin >> target_s;
        target_strs.insert(target_s);
    }
    for (i = 1; i <= m; i++) {
        all_status.clear();
        ans = 0;
        cin >> mode_s;
        // map 的默认值是 0，这里设成 -1 特殊标记
        if (ans_rec[mode_s] == 0) {
            dfs(mode_s);
            for (unordered_set<string>::iterator it = all_status.begin();
                it != all_status.end(); it++) {
                ans += target_strs.count(*it);
            }
            printf("%d\n", ans);
            ans_rec[mode_s] = ans == 0 ? -1 : ans;
        } else {
            printf("%d\n", ans_rec[mode_s] == -1 ? 0 : ans_rec[mode_s]);
        }
    }
}