题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1819
看到这个题后，先去网上查了查题解，发现都是trie树，偶然发现洛谷中有一篇题解是哈希
那么都已经用了字符串哈希了，map是不是也可行呢？
对于3种情况：
- 删除串中某个位置的字母：枚举删除哪一个，然后用map找相等的
- 添加一个字母到串中某个位置：相当于字典中的字符串删除某一位后，和当前字符串相等
- 替换串中某一位置的一个字母为另一个字母：相当于同时删除同一位后相等
然后就由于某一个字符串可能被统计多遍，调不过去了
我就产生了什么都不管，打个暴力的想法：
- 我先打了一个map<string,bitset<10000> >的暴力，这是为了节省时间而牺牲了空间，然而交上去发现牺牲的空间太多了，洛谷过不了，bzoj不用想也过不了。
- 接下来尝试map<string,vector<int> >的暴力，发现洛谷T了2个点，那这样的话bzoj是不是就能A呢？是。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<bits/stdc++.h> #define pb push_back using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; map<string,vector<int> >mp[22],same; bool ans[10010]; inline string del(string s,int x){ return s.substr(0,x-1)+s.substr(x); } inline void ins(string s,int num){ same[s].pb(num); for(int i=1; i<=s.size(); i++){ string ss=del(s,i); mp[i][ss].pb(num); } } inline void add(vector<int>v){ for(int i=0; i<v.size(); i++)ans[v[i]]=true; } int main(){ string s; n=rd(),m=rd(); for(int i=1; i<=n; i++){ cin>>s; ins(s,i); } while(m--){ memset(ans,0,sizeof(ans)); cin>>s; if(same[s].size()){ puts("-1"); continue; } for(int i=1; i<=s.size()+1; i++)add(mp[i][s]); for(int i=1; i<=s.size(); i++){ string ss=del(s,i); add(same[ss]); add(mp[i][ss]); } int num=0; for(int i=1; i<=n; i++)num+=ans[i]; printf("%d\n",num); } return 0; } |
