MLE on test 19
原题链接：11814.Watto and Mechanism
2024-08-19 20:51:22
发布于：浙江
12阅读
0回复
0点赞
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fileO(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fileC fclose(stdin); fclose(stdout);
using namespace std;
inline ll read(){
ll f=1,outt=0;char a=getchar();
while(a>'9'||a<'0'){if(a=='-')f=-1;a=getchar();}
while(a<='9'&&a>='0'){outt*=10;outt+=a-'0';a=getchar();}
return f*outt;
}
const int MAXN = 1e7 + 9;
int n, m;
int trie[MAXN][3];
int ed[MAXN];
int change(char c)
{
return c - 'a';
}
int root = 1;
int cnt = 1;
void add(string s)
{
int nown = root;
for(auto i : s)
{
int k = change(i);
if(!trie[nown][k])
{
trie[nown][k] = ++cnt;
}
nown = trie[nown][k];
ed[nown]++;
}
}
bool dfs(string s, int i, int nown, int flag)
{
if(flag > 1)
return 0;
if(i == (int)s.length())
return (flag == 1) && ed[nown];
int k = change(s[i]);
bool fg = 0;
if(trie[nown][k])
{
fg = fg || dfs(s, i + 1, trie[nown][k], flag);
}
if(trie[nown][(k + 1) % 3] && !flag)
{
fg = fg || dfs(s, i + 1, trie[nown][(k + 1) % 3], flag + 1);
}
if(trie[nown][(k + 2) % 3] && !flag)
{
fg = fg || dfs(s, i + 1, trie[nown][(k + 2) % 3], flag + 1);
}
return fg;
}
void solve()
{
n = read();
m = read();
for(int i = 0; i < n; i++)
{
string ins;
cin >> ins;
add(ins);
}
while(m--)
{
string fs;
cin >> fs;
if(dfs(fs, 0, root, 0))
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}
return;
}
int T;
int main()
{
T = 1;
// T = read();
while(T--)
{
solve();
}
return 0;
}
有帮助，赞一个