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]);
}
}
}