题解 CF514C 【Watto and Mechanism】
首先先介绍一下题意（管管可视为翻译）：
给出n个字符串（建立trie树）,然后再给出m个字符串, 让你判断在原给定的n个字符串中是否出现过出现过与这m个字符串互异的字符数恰好为1的字符串
（即字符串长度相同,并且 有且仅有一个字符不同,不过原题中的意思好像是字符串差异为1啊,没说完全相同的字符串不算满足要求,但是事实上给出的数据就是严格要求字符串之间有一个字符不同的= =|||）,
如果有则输出YES,没有则输出NO,依次输出答案。 然后字符串总数不超过6e5,字符总数也不超过6e5（应该吧...）
题目分析：trie树+深搜（可以算是水题但是也不算太太太水）
解题步骤：
1.建trie树,对于每个字符串结尾的节点标记true
（但是这里有一个多出来的操作,用于深搜时的剪枝,不过效率有没有提高我也没测,有兴趣的童鞋可以测一下）
2.依次读入m个字符串并在trie树中深搜查找是否有满足条件的字符串
3.输出答案return 0#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int M=7e5+100;
const int inf=1e9;
int n,m,len,cnt,now;
int to[M][3],lt[M];
bool is[M],flag;
string s;
bool dfs(int at,int now) {
if(at==len){ //搜索到尾了
if(is[now] && !flag) //当前节点有标记且flag已被标记为0
return true;
return false; //任一条件不满足都返回false
}
int tmp=s[at]-'a';
if(lt[now]<len) //剪枝操作,同上,效率有没有提高是不清楚的不过能过
return false;
for(int i=0; i<3; ++i)
if(to[now][i]){
if(i==tmp){ //与当前的字符相同
if(dfs(at+1,to[now][i]))
return true;
}
else if(flag){ //与当前的字符不同
flag=0;
if(dfs(at+1,to[now][i]))
return true;
flag=1;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1; i<=n; ++i) { //读入n个字符串并建trie树
cin>>s, len=s.length();
lt[0]=max(lt[0],len), //这里就是剪枝,lt数组记录当前节点以下的最长字符串长度,深搜时若搜到了长度小于当前字符串的枝条则剪枝
now=0;
for(int j=0; j<len; ++j) {
int tmp=s[j]-'a';
if(!to[now][tmp])
to[now][tmp]=++cnt;
now=to[now][tmp];
lt[now]=max(lt[now],len);
}
is[now]=1;
}
while(m--) { //深搜查询m个字符串
cin>>s, len=s.length(), flag=1;
if(dfs(0,0)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}然后第二种算法是Hash（想看的童鞋可以看一看,很短的）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
#define ll unsigned long long
#define P make_pair
using namespace std;
const int M=6e5+100;
const ll mod=99991;
int n,m; string s;
set< pair<int,ll> > st; ll f[M]={1,1}; //make_pair了之后貌似是快了一点
ll Hash() {
int len=s.length();
ll tmp=0;
for(int i=0; i<len; ++i)
tmp=tmp*mod+s[i];
return tmp;
}
bool check() {
int len=s.length();
ll h=Hash();
for(int i=0; i<len; ++i) for(char c='a'; c<='c'; ++c)
if(c!=s[i] && st.find(P(len,h-s[i]*f[len-i]+c*f[len-i]))!=st.end())
return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
for(int i=2; i<M; ++i)
f[i]=f[i-1]*mod;
cin>>n>>m;
for(int i=1; i<=n; ++i)
cin>>s, st.insert(P(s.length(),Hash()));
while(m--) {
cin>>s;
if(check()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}但是这个代码WA在了第27个点上,表示很难受,改了很久,一直以为是mod的值的问题,想想数据可能精心构造过,但是别人的Hash就过了：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
typedef long long ll;
const int MAX = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int KEY = 257;//ORZ
int n, m;
ll f[MAX];
set <ll> s;
char s1[MAX];
char s2[MAX];
void inti() {
f[0] = 1;
for(int i = 1; i <= MAX; i++){
f[i] = f[i-1] * KEY % MOD;
}
}
ll Hash(char *s1) {
int len = strlen(s1);
ll tmp = 0;
for(int i = 0 ; i < len; i++){
tmp = (tmp * KEY + s1[i]) % MOD;
}
return tmp;
}
bool check(char *s2) {
int len = strlen(s2);
ll h = Hash(s2);
for(int i = 0 ; i < len; i++){
for(ll ch = 'a'; ch <= 'c'; ch++){
if(ch == s2[i]) continue;
if(s.find((((ch - s2[i]) * f[len - i - 1] + h)%MOD + MOD)%MOD) != s.end())
return true;
}
}
return false;
}
int main() {
inti();
while(~scanf("%d%d", &n, &m)){
for(int i = 1; i <= n; i++)
scanf("%s", s1),
s.insert(Hash(s1));
for(int i = 1; i <= m; i++)
scanf("%s", s2),
puts(check(s2) ? "YES" : "NO");
}
return 0;
}很奇怪... 如果有童鞋看出来什么了可以评论一下,我也是有点无能为了了