【枚举+trie+dfs】CF514 C

清疚 2024-03-23 18:05 77阅读 0赞

[Problem - 514C - Codeforces][]

题意：

![5b42449d876c4235a6e81881e28f8ef5.png][]

思路：

其实是trie上dfs的板题

先把字符串插入到字典树中

对于每次询问，都去字典树上dfs

注意到字符集只有3，因此如果发现有不同的字符，去枚举新的字符

Code：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 4e5 + 10;
    const int M = 3e6 + 10;
    const int P = 131;
    
    string s;
    
    int tot = 0;
    int tag[N];
    int tr[N][30];
    
    void insert(string x) {
    	int p = 0;
    	for (int i = 0; i < x.size(); i ++) {
    		int u = x[i] - 'a';
    		if (! tr[p][u]) {
    			tr[p][u] = ++tot;
    		}
    		p = tr[p][u];
    	}
    	tag[p] = 1;
    }
    bool dfs(int dep, int u, int num) {
    	if (s[dep]) {
    		int v = s[dep] - 'a';
    		if (tr[u][v]) {
    			if (dfs(dep + 1, tr[u][v], num)) return true;
    		}
    		if (!num) {
    			for (int j = 0; j < 3; j ++) {
    				if (j != v && tr[u][j]) {
    					if (dfs(dep + 1, tr[u][j], num + 1)) return true;
    				}
    			}
    		}
    	}
    	else if (tag[u] && num) return true;
    	return false;
    }
    void solve() {
    	int n,m;
    	cin >> n >> m;
    
    	for (int i = 1; i <= n; i ++) {
    		cin >> s;
    		insert(s);
    	}
    
    	for (int i = 1; i <= m; i ++) {
    		cin >> s;
    		if (dfs(0, 0, 0)) {
    			cout << "YES" << "\n";
    		}else {
    			cout << "NO" << "\n";
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
    
    	int t = 1;
    	//cin >> t;
    	while(t --) {
    		solve();
    	}
    	return 0;
    }

[Problem - 514C - Codeforces]: https://codeforces.com/problemset/problem/514/C
[5b42449d876c4235a6e81881e28f8ef5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c4cb9220f385400a9a35eaba40067d8e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，77人围观）

还没有评论，来说两句吧...

相关阅读

相关【枚举+trie+dfs】CF514 C

[Problem - 514C - Codeforces][] 题意： ![5b42449d876c4235a6e81881e28f8ef5.png][] 思路：其实

清疚/ 2024年03月23日 18:05/ 0 赞/ 78 阅读

相关 C枚举

![1598479-20190917163036384-274404394.png][] 转载于:https://www.cnblogs.com/yunshangyue

Myth丶恋晨/ 2023年08月17日 16:05/ 0 赞/ 156 阅读

相关 c++枚举和c语言枚举_C语言枚举初学者指南

c++枚举和c语言枚举 Hey, folks! Hope you all are doing well. In this article, we will be discus

曾经终败给现在/ 2023年02月28日 06:05/ 0 赞/ 252 阅读

相关 C#——枚举类型

C\——枚举类型枚举类型是由基础整型数值类型的一组命名常量定义的值类型。若要定义枚举类型，请使用 enum 关键字并指定枚举成员的名称： enum Se

╰半夏微凉°/ 2022年11月19日 12:53/ 0 赞/ 294 阅读

相关 C#——枚举

枚举 ![0_13315183659D8L.gif][] > 声明枚举的条件：确定数量，确定值的取值范围。 > > 枚举的语法：（1）声明枚举的时候和类同级。 > >

灰太狼/ 2022年08月26日 04:48/ 0 赞/ 268 阅读

相关 C++枚举

1. 介绍第一次学习枚举类型时，觉得这个名字很诡异。但是后来发现，“枚举”真的特别传神，枚举就是可数的意思。当你发现某个类型的值是数得过来的，那就派枚举出场吧。

你的名字/ 2022年08月05日 00:58/ 0 赞/ 266 阅读

相关枚举【C#】

简单总结一下枚举的用法：什么是枚举？枚举简单的说是一种数据类型，只不过这种数据类型只包含自定义的特定数据，它是一组有共同特性的数据的集合。举个例子，颜色也可以

一时失言乱红尘/ 2022年06月16日 05:44/ 0 赞/ 272 阅读

相关 c#---枚举，结构

前言今天我们来学习一下c\中的枚举和结构。枚举 When 有一些固定的范围的值就可以用枚举，例如方向，性别等。 Where 枚举

迈不过友情╰/ 2022年05月25日 09:51/ 0 赞/ 271 阅读

相关 C#枚举

Gender.cs 解决方案管理器--->右击项目--->添加/类--->代码文件 /// <summary> /// 性别类型

àì夳堔傛蜴生んèń/ 2022年01月23日 22:57/ 0 赞/ 294 阅读

相关 C#枚举

using System; using System.Collections.Generic; using System.Linq; using System.Text;

秒速五厘米/ 2022年01月10日 15:49/ 0 赞/ 314 阅读