当前位置: 首页 > news >正文

【枚举+trie+dfs】CF514 C

Problem - 514C - Codeforces

题意:

 

思路:

其实是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;
}

相关文章:

【枚举+trie+dfs】CF514 C

Problem - 514C - Codeforces 题意&#xff1a; 思路&#xff1a; 其实是trie上dfs的板题 先把字符串插入到字典树中 对于每次询问&#xff0c;都去字典树上dfs 注意到字符集只有3&#xff0c;因此如果发现有不同的字符&#xff0c;去枚举新的字符 Code&#xff1a; #in…...

【计算机视觉】BLIP:统一理解和生成的自举多模态模型

文章目录 一、导读二、背景和动机三、方法3.1 模型架构3.2 预训练目标3.3 BLIP 高效率利用噪声网络数据的方法&#xff1a;CapFilt 四、实验4.1 实验结果4.2 各个下游任务 BLIP 与其他 VLP 模型的对比 一、导读 BLIP 是一种多模态 Transformer 模型&#xff0c;主要针对以往的…...

【Ansible】Ansible自动化运维工具之playbook剧本搭建LNMP架构

LNMP 一、playbooks 分布式部署 LNMP1. 环境配置2. 安装 ansble3. 安装 nginx3.1 准备 nginx 相关文件3.2 编写 lnmp.yaml 的 nginx 部分3.3 测试 nginx4. 安装 mysql4.1 准备 mysql 相关文件4.2 编写 lnmp.yaml 的 mysql 部分4.3 测试 mysql5. 安装 php5.1 编写 lnmp.yaml 的 …...

Spring中的事务

一、为什么需要事务&#xff1f; 事务定义 将一组操作封装成一个执行单元&#xff08;封装到一起&#xff09;&#xff0c;要么全部成功&#xff0c;要么全部失败。 为什么要用事务&#xff1f; 比如转账分为两个操作&#xff1a; 第一步操作&#xff1a; A 账户 -100 元…...

38 非法地址访问的 segment fault 的调试

前言 在前面一篇文章 coredump 的生成和使用 中, 我们看到 "测试用例2 - 非法地址访问" 产生了一个 segment fault 我们这里 就来调试一下 这个 segment fault 是怎么回事 测试用例 #include "stdio.h"int main(int argc, char** argv) {int x 2; i…...

c++中c_str()的用法详解

c_str()就是将C的string转化为C的字符串数组&#xff01;&#xff01;&#xff01; C中没有string&#xff0c;所以函数c_str()就是将C的string转化为C的字符串数组&#xff0c;c_str()生成一个const char *指针&#xff0c;指向字符串的首地址。 下文通过3段简单的代码比较分析…...

谈谈关于新能源汽车的话题

新能源汽车是指使用新型能源替代传统燃油的汽车&#xff0c;主要包括纯电动汽车、插电式混合动力汽车和燃料电池汽车等。随着环境污染和能源安全问题的日益突出&#xff0c;新能源汽车已经成为全球汽车行业的发展趋势。下面我们来谈谈关于新能源汽车的话题。 首先&#xff0c;新…...

EventBus 开源库学习(二)

整体流程阅读 EventBus在使用的时候基本分为以下几步&#xff1a; 1、注册订阅者 EventBus.getDefault().register(this);2、订阅者解注册&#xff0c;否者会导致内存泄漏 EventBus.getDefault().unregister(this);3、在订阅者中编写注解为Subscribe的事件处理函数 Subscri…...

4_Apollo4BlueLite电源管理

1.Cortex-M4 Power Modes Apollo4BlueLite支持以下4种功耗模式&#xff1a; ▪ High Performance Active (not a differentiated power mode for the Cortex-M4) ▪ Active ▪ Sleep ▪ Deep Sleep &#xff08;1&#xff09;High Performance Mode 高性能模式不是arm定…...

Pytorch入门学习——快速搭建神经网络、优化器、梯度计算

我的代码可以在我的Github找到 GIthub地址 https://github.com/QinghongShao-sqh/Pytorch_Study 因为最近有同学问我如何Nerf入门&#xff0c;这里就简单给出一些我的建议&#xff1a; &#xff08;1&#xff09;基本的pytorch&#xff0c;机器学习&#xff0c;深度学习知识&a…...

举例说明typescript的Exclude、Omit、Pick

一、提前知识说明&#xff1a;联合类型 typescript的联合类型是一种用于表示一个值可以是多种类型中的一种的类型。我们使用竖线&#xff08;|&#xff09;来分隔每个类型&#xff0c;所以number | string | boolean是一个可以是number&#xff0c;string或boolean的值的类型。…...

记录一次Linux环境下遇到“段错误核心已转储”然后利用core文件解决问题的过程

参考Linux 下Coredump分析与配置 在做项目的时候&#xff0c;很容易遇到“段错误&#xff08;核心已转储&#xff09;”的问题。如果是语法错误还可以很快排查出来问题&#xff0c;但是碰到coredump就没办法直接找到问题&#xff0c;可以通过设置core文件来查找问题&#xff0…...

WPF中自定义Loading图

纯前端方式&#xff0c;通过动画实现Loading样式&#xff0c;如图所示 <Grid Width"35" Height"35" HorizontalAlignment"Center" VerticalAlignment"Center" Name"Loading"><Grid.Resources><DrawingBrus…...

用html+javascript打造公文一键排版系统14:为半角和全角字符相互转换功能增加英文字母、阿拉伯数字、标点符号、空格选项

一、实际工作中需要对转换选项细化内容 在昨天我们实现了最简单的半角字符和全角字符相互转换功能&#xff0c;就是将英文字母、阿拉伯数字、标点符号、空格全部进行转换。 在实际工作中&#xff0c;我们有时只想英文字母、阿拉伯数字、标点符号、空格之中的一两类进行转换&a…...

叮咚买菜财报分析:叮咚买菜第二季度财报将低于市场预期

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 卖方分析师对叮咚买菜第二季度财报的预测 尽管叮咚买菜&#xff08;DDL&#xff09;尚未明确披露第二季度财报的具体日期&#xff0c;但根据其以往的业绩公告&#xff0c;猛兽财经认为叮咚买菜很有可能会在8月的第二周发布…...

设计模式行为型——中介者模式

目录 什么是中介者模式 中介者模式的实现 中介者模式角色 中介者模式类图 中介者模式代码实现 中介者模式的特点 优点 缺点 使用场景 注意事项 实际应用 什么是中介者模式 中介者模式&#xff08;Mediator Pattern&#xff09;属于行为型模式&#xff0c;是用来降低…...

Vue——formcreate表单设计器自定义组件实现(二)

前面我写过一个自定义电子签名的formcreate表单设计器组件&#xff0c;那时初识formcreate各种使用也颇为生疏&#xff0c;不过总算套出了一个组件不是。此次时隔半年又有机会接触formcreate&#xff0c;重新熟悉和领悟了一番各个方法和使用指南。趁热打铁将此次心得再次分享。…...

人脸验证(Face verification) 和 人脸识别(Face recognition) 的区别

人脸验证(Face verification) 和 人脸识别(Face recognition) 的区别 Face verification 和 Face recognition 都是人脸识别的技术&#xff0c;但是它们的应用和目的不同。 Face verification&#xff08;人脸验证&#xff09;是指通过比对两张人脸图像&#xff0c;判断它们是…...

前端如何打开钉钉(如何唤起注册表中路径与软件路径不关联的软件)

在前端唤起本地应用时&#xff0c;我查询了资料&#xff0c;在注册表中找到腾讯视频会议的注册表情况&#xff0c;如下&#xff1a; 在前端代码中加入 window.location.href"wemeet:"; 就可以直接唤起腾讯视频会议&#xff0c;但是我无法唤起钉钉 之所以会这样&…...

数据可视化入门指南

数据可视化是一种将抽象的数值和数据转换为易于理解的图像的方法。它可以帮助人们更好地理解数据的含义&#xff0c;并且可以揭示数据中可能被忽视的模式和趋势。本文将为你提供一个简单的数据可视化入门指南。 为什么数据可视化重要&#xff1f; 在我们的生活中&#xff0c;数…...

Git-RSCLIP模型快速入门:10分钟实现第一个图文检索应用

Git-RSCLIP模型快速入门&#xff1a;10分钟实现第一个图文检索应用 1. 引言 你是不是经常遇到这样的情况&#xff1a;电脑里存了几千张照片&#xff0c;想找某张特定的图片却怎么也找不到&#xff1f;或者想用文字描述来搜索相关的图片&#xff0c;但传统的关键词搜索总是不够…...

PyTorch 2.8 镜像实战:基于LSTM的时序预测模型开发与部署

PyTorch 2.8 镜像实战&#xff1a;基于LSTM的时序预测模型开发与部署 1. 时序预测的LSTM解决方案 时序数据预测是AI领域最具挑战性的任务之一。传统统计方法在处理复杂非线性关系时往往力不从心&#xff0c;而长短期记忆网络&#xff08;LSTM&#xff09;凭借其独特的记忆单元…...

专业的办公家具哪家技术强

在企业发展进程中&#xff0c;办公家具的优劣至关重要。专业办公家具不仅能提升办公环境舒适度&#xff0c;还能彰显企业形象与实力。然而&#xff0c;市场上办公家具品牌众多&#xff0c;究竟哪家技术强呢&#xff1f;今天&#xff0c;就为大家详细介绍佛山市豪亿办公家具&…...

update_io_latency:为什么你的IO约束会变成负数?

在数字后端CTS阶段&#xff0c;很多同学都困惑过——为什么做完时钟树后&#xff0c;Timing Report里IO Port的clock latency突然变成了负数&#xff1f;景芯训练营仔细的同学都发现了&#xff0c;在Innovus中从ccopt 后的timing report中可以看到clock delay是从负值开始算起的…...

Haskell编译器优化:wiwinwlh GHC内部机制详解

Haskell编译器优化&#xff1a;wiwinwlh GHC内部机制详解 【免费下载链接】wiwinwlh What I Wish I Knew When Learning Haskell 项目地址: https://gitcode.com/gh_mirrors/wi/wiwinwlh wiwinwlh项目&#xff08;What I Wish I Knew When Learning Haskell&#xff09;…...

C++27原子智能降级策略(Auto-Degrade Atomic Pattern):当缓存行竞争超阈值时自动切换为lock-free队列——工业级源码级实现

第一章&#xff1a;C27原子智能降级策略的演进动因与设计哲学C27将首次引入原子智能降级&#xff08;Atomic Intelligent Fallback&#xff09;机制&#xff0c;其核心动因源于现代异构计算环境中硬件原子指令集碎片化加剧、内存模型语义边界模糊化&#xff0c;以及开发者在可移…...

Tickers:嵌入式无阻塞软件定时器库

1. 项目概述Tickers是一个轻量级、无阻塞的定时回调库&#xff0c;专为资源受限的嵌入式系统设计。其核心目标是彻底替代delay()函数&#xff0c;在不牺牲实时性、不引入线程调度开销的前提下&#xff0c;实现高精度、可重入、多实例的周期性函数调用。该库不依赖操作系统内核&…...

AI同事抑郁症诊断报告:大模型存在主义危机爆发

当测试对象成为“患者” 在软件测试的日常工作中&#xff0c;我们习惯于面对无生命的代码、逻辑严密的流程和可预期的行为边界。我们设计用例&#xff0c;模拟输入&#xff0c;验证输出&#xff0c;在“预期”与“实际”的比对中寻找偏差。然而&#xff0c;当测试对象从传统的…...

别再只盯着输入了!时间序列预测中,被忽视的‘标签自相关’问题与FreDF解法

时间序列预测的盲区&#xff1a;标签自相关性如何悄悄破坏你的模型精度 想象一下&#xff0c;你花费数周时间调整模型架构、优化超参数&#xff0c;甚至尝试了最新的Transformer变体&#xff0c;但预测结果始终差强人意。问题可能并不出在你精心设计的输入特征工程上&#xff0…...

如何在Windows上轻松安装安卓应用?APK-Installer终极指南

如何在Windows上轻松安装安卓应用&#xff1f;APK-Installer终极指南 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer APK-Installer是一款专为Windows平台设计的安卓应…...