CF的传送门
题目的意思是给你n个字符串和m个询问,每次询问一个字符串是否可以通过改变其中的一个字母来得到n个字符串中
的任意一个,如果可以输出"YES",否则输出"NO";
字典树加DFS,首先对所给的字符串建立一颗字典树,然后对于每一个字符串的查询,进行dfs就行,具体看下代码吧!
在这里介绍个讲得不错的字典树博客: #3034715
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <set>#include <map>#include <queue>#include <vector>#include <cstdlib>#include <algorithm>#define ls u << 1#define rs u << 1 | 1#define lson l, mid, u << 1#define rson mid + 1, r, u << 1 | 1#define INF 0x3f3f3f3f#define MAX 3using namespace std;typedef long long ll;const int M = 6e5 + 100;const int mod = 2147483647;char s[M];struct Trie {int index; //根据需要进行变化Trie *next[MAX]; //表示每一层包含有多少种类的数Trie() { //初始化index = -1;memset(next,0,sizeof(next));}};Trie *root = new Trie; //字典树的根void Trie_insert(Trie *tr,int len) { //递归建立字典树if(s[len]) {int u = s[len] – 'a';if(tr -> next[u] == 0)tr -> next[u] = new Trie;Trie_insert(tr -> next[u],len + 1);} else tr->index = 1; //标记为1表示以到达字符串结尾}/*int deal_Trie(Trie *tr){ //递归销毁字典树if(tr == NULL){return 0;}for(int i = 0; i < MAX; i++){if(tr -> next[i]) //如果下一层还有,则递归销毁deal_Trie(tr -> next[i]);}free(tr);return 0;}*/bool dfs(Trie *tr,int len,int num) {if(s[len]) {int u = s[len] – 'a';if(tr->next[u] != 0) {if(dfs(tr->next[u],len + 1,num)) return true;}if(!num) {for(int i = 0; i < MAX; i++) {if(i != u && tr->next[i] != 0) {if(dfs(tr->next[i],len + 1,num + 1)) return true;}}}} else {if(num && tr->index == 1) return true;}return false;}int main() {int n,m;scanf("%d %d",&n,&m);while(n–) {scanf("%s",s);Trie_insert(root,0);}while(m–) {scanf("%s",s);if(dfs(root,0,0)) puts("YES");else puts("NO");}return 0;}
，经验是由痛苦中粹取出来的
