bzoj 1819: [JSOI]Word Query电子字典 map+暴力

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1819


看到这个题后,先去网上查了查题解,发现都是trie树,偶然发现洛谷中有一篇题解是哈希

那么都已经用了字符串哈希了,map是不是也可行呢?

对于3种情况:

  • 删除串中某个位置的字母:枚举删除哪一个,然后用map找相等的
  • 添加一个字母到串中某个位置:相当于字典中的字符串删除某一位后,和当前字符串相等
  • 替换串中某一位置的一个字母为另一个字母:相当于同时删除同一位后相等

然后就由于某一个字符串可能被统计多遍,调不过去了

我就产生了什么都不管,打个暴力的想法:

  1. 我先打了一个map<string,bitset<10000> >的暴力,这是为了节省时间而牺牲了空间,然而交上去发现牺牲的空间太多了,洛谷过不了,bzoj不用想也过不了。
  2. 接下来尝试map<string,vector<int> >的暴力,发现洛谷T了2个点,那这样的话bzoj是不是就能A呢?是。

 

发表评论