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

P1278 单词游戏 简单搜索+玄学优化

单词游戏

传送门

题目描述

Io 和 Ao 在玩一个单词游戏。

他们轮流说出一个仅包含元音字母的单词,并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。

游戏可以从任何一个单词开始。

任何单词禁止说两遍,游戏中只能使用给定词典中含有的单词。

游戏的复杂度定义为游戏中所使用的单词长度总和。

编写程序,求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。

输入格式

输入文件的第一行,表示一个自然数 N ( 1 ≤ N ≤ 16 ) N(1 \le N \le 16) N(1N16) N N N 表示一本字典中包含的单词数量以下的每一行包含字典中的一个单词,每一个单词是由字母 AEIOU 组成的一个字符串,每个单词的长度将小于等于 100 100 100,所有的单词是不一样的。

输出格式

输出文件仅有一行,表示该游戏的最大可能复杂度。

样例 #1

样例输入 #1

5
IOO
IUUO
AI
OIOOI
AOOI

样例输出 #1

16

注明

以上来自洛谷。 以上来自洛谷。 以上来自洛谷。

解题思路

直接找题意做即可。循环遍历每一个字符串,将其设为第一个字符串,然后暴搜就行了。注意当搜索次数达到 5 × 1 0 7 5\times 10^7 5×107 时,直接输出答案并结束程序。说起来有点抽象,结合代码容易理解。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n;
string s[20];
int _s[20];
bool vis[20];
int COUNT;
int Answer;
inline void dfs(int len, char c) {++COUNT;if (COUNT >= 5e7)cout << Answer, exit(0);Answer = max(Answer, len);for (register int i = 1; i <= n; ++i) {if (vis[i])continue;if (s[i][0] == c) {vis[i] = 1;dfs(len + _s[i], s[i][_s[i] - 1]);vis[i] = 0;}}
}
signed main() {cin >> n;for (register int i = 1; i <= n; ++i)cin >> s[i], _s[i] = s[i].size();for (register int i = 1; i <= n; ++i) {vis[i] = 1;dfs(_s[i], s[i][_s[i] - 1]);vis[i] = 0;}cout << Answer << endl;return 0;
}

闲话

一开始以为这题非常简单,没想到这么简单。注意到洛谷难度评级为:在这里插入图片描述
#@!&(#@&(@!$(!@&#()&*%%#&Y&&%%%#%@!&(<-开启词汇联想)

大佬 C Wx 用状压 DP 通过本题,牛炸了。

相关文章:

P1278 单词游戏 简单搜索+玄学优化

单词游戏 传送门 题目描述 Io 和 Ao 在玩一个单词游戏。 他们轮流说出一个仅包含元音字母的单词&#xff0c;并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。 游戏可以从任何一个单词开始。 任何单词禁止说两遍&#xff0c;游戏中只能使用给定词典中含有…...

软考 - 系统架构设计师 - 数据架构真题

问题 1&#xff1a; (相当于根据题目中提到的 4 点&#xff0c;说一下关系型数据库的缺点) &#xff08;1&#xff09;.用户数量的剧增导致并发负载非常高&#xff0c;往往会达到每秒上万次读写请求。关系数据库应付每秒上万次的 SQL 查询还勉强可以&#xff0c;但是应付上万…...

Ubuntu22.04下opencv4.9.0环境的搭建

目录 1、更新系统包列表:2、安装依赖项:3、下载 OpenCV 源代码:4、编译和安装 OpenCV:5、配置环境变量:6、测试1、更新系统包列表: 在终端中执行以下命令,以确保系统包列表是最新的: sudo apt update2、安装依赖项: 安装构建 OpenCV 所需的依赖项: sudo apt inst…...

Flask如何在后端实时处理视频帧在前端展示

怎么样在前端->选择视频文件->点击上传视频后->后端实时分析上传的视频->在前端展示后端分析结果&#xff08;视频&#xff0c;文本&#xff09; ↓ 咱们先看整看整体代码&#xff0c;有个大概的印象。 Flask后端代码 cljc车流检测Demofrom pytz import timezon…...

04-15 周一 GitHub仓库CI服务器actions-runner和workflow yaml配置文档解析

04-15 周一 GitHub仓库CI服务器配置过程文档 时间版本修改人描述2024年4月15日10:35:52V0.1宋全恒新建文档2024年4月17日10:33:20v1.0宋全恒完成github actions CI的配置和工作流配置文件解读文档的撰写 简介 一些基础概念 前提知识 仓库介绍 地址镜像介绍https://github.…...

论文笔记:SmartPlay : A Benchmark for LLMs as Intelligent Agents

iclr 2024 reviewer评分 5688 引入了 SmartPlay&#xff0c;一种从 6 种不同游戏中提取的基准 衡量LLM作为智能体的能力 1 智能代理所需的能力 论文借鉴游戏设计的概念&#xff0c;确定了智能LLM代理的九项关键能力&#xff0c;并为每项能力确定了多个等级&#xff1a; 长文…...

搜维尔科技:【工业仿真】煤矿安全知识基础学习VR系统

产品概述 煤矿安全知识基础学习VR系统 系统内容&#xff1a; 煤矿安全知识基础学习VR系统内容包括&#xff1a;下井流程&#xff08;正确乘坐罐笼、班前会、井下行走注意事项、工作服穿戴、入井检身及人员清点、下井前准备工作、提升运输安全&#xff09;&#xff1b;运煤流程…...

线程和进程的区别(面试)

线程和进程的区别 进程和线程的区别线程的优点 进程和线程的区别 1. 进程是系统进行资源分配和调度的一个独立单位,线程是程序执行的最小单位. 2. 进程有自己的内存地址空间,线程只独享指令流执行的必要资源,如寄存器和栈. 3. 由于同一进程的各线程共享内存和文件资源,可以不通…...

抓取电商产品数据的方法|电商平台商品详情数据|批量上架|商品搬家|电商封装API数据采集接口更高效安全的数据采集

大量级电商数据采集时使用电商API接口有以下优势&#xff1a; 1. 数据准确性&#xff1a;通过电商API接口获取数据&#xff0c;可以保证数据的准确性和实时性&#xff0c;避免了手动采集可能出现的错误和延迟。 2. 自动化采集&#xff1a;API接口可以实现自动化的数据获取和更…...

关联规则Apriori算法

1.前置知识 经典应用场景&#xff1a;购物车商品的关联规则。 符号表示&#xff1a; I代表项集,项是可能出现的值&#xff0c;例如购物车中能有尿布、啤酒、奶粉等&#xff0c;I{尿布、啤酒、奶粉}&#xff0c;尿布是项 K代表I中包含的项的数目&#xff0c;上面的k3 事…...

书生·浦语大模型全链路开源体系-第4课

书生浦语大模型全链路开源体系-第4课 书生浦语大模型全链路开源体系-第4课相关资源XTuner 微调 LLMXTuner 微调小助手认知环境安装前期准备启动微调模型格式转换模型合并微调结果验证 将认知助手上传至OpenXLab将认知助手应用部署到OpenXLab使用XTuner微调多模态LLM前期准备启动…...

HTML优化SEO

在网站开发中&#xff0c;除了关注设计和用户体验&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;也是提升网站流量和可见度的关键。合理的HTML结构和元素运用能够帮助搜索引擎更好地理解页面内容&#xff0c;从而提高搜索排名。以下是一些基于HTML的SEO优化技巧&#xf…...

RabbitMQ-交换机

文章目录 交换机fanoutDirecttopicHeadersRPC 交换机 **交换机 **是消息队列中的一个组件&#xff0c;其作用类似于网络路由器。它负责将我们发送的消息转发到相应的目标&#xff0c;就像快递站将快递发送到对应的站点&#xff0c;或者网络路由器将网络请求转发到相应的服务器…...

mapreduce中的MapTask工作机制(Hadoop)

MapTask工作机制 MapReduce中的Map任务是整个计算过程的第一阶段&#xff0c;其主要工作是将输入数据分片并进行处理&#xff0c;生成中间键值对&#xff0c;为后续的Shuffle和Sort阶段做准备。 1. 输入数据的划分&#xff1a; 输入数据通常存储在分布式文件系统&#xff08;…...

景区文旅剧本杀小程序亲子公园寻宝闯关系统开发搭建

要开发景区文旅剧本杀小程序亲子公园寻宝闯关系统&#xff0c;您需要考虑以下步骤&#xff1a; 1. 设计游戏场景和规则&#xff1a;根据亲子公园的主题和特点&#xff0c;设计适合亲子游玩的游戏场景和规则。您需要考虑游戏的安全性、趣味性和互动性&#xff0c;确保孩子们能够…...

性能优化---webpack优化

1、如何提高webpack打包速度 a、优化Loader--影响Loader打包速度的首要元素是Babel&#xff0c;Babel 会将代码转为字符串生成 AST&#xff0c;然后对 AST 继续进行转变最后再生成新的代码&#xff0c;项目越大&#xff0c;转换代码越多&#xff0c;效率就越低。先优化 Loader …...

YOLOv9改进策略 | 损失函数篇 | EIoU、SIoU、WIoU、DIoU、FocusIoU等二十余种损失函数

一、本文介绍 这篇文章介绍了YOLOv9的重大改进&#xff0c;特别是在损失函数方面的创新。它不仅包括了多种IoU损失函数的改进和变体&#xff0c;如SIoU、WIoU、GIoU、DIoU、EIOU、CIoU&#xff0c;还融合了“Focus”思想&#xff0c;创造了一系列新的损失函数。这些组合形式的…...

贪心算法-跳跃游戏

给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输…...

sql知识总结二

一.报错注入 1.什么是报错注入&#xff1f; 这是一种页面响应形式&#xff0c;响应过程如下&#xff1a; 用户在前台页面输入检索内容----->后台将前台输入的检索内容无加区别的拼接成sql语句&#xff0c;送给数据库执行------>数据库将执行的结果返回给后台&#xff…...

VSCode和CMake实现C/C++开发

VSCode和CMake实现Ubuntu下C/C++开发总结 目录 0.简介1.Linux系统介绍2.开发环境搭建2.1 编译器,调试器安装2.2 CMake安装3.GCC编译器3.1 编译过程3.2 g++重要编译参数4.g++编译实战4.0 编译前4.1 直接编译4.2 生成库文件并编译4.3 编译后4.3.1 编译完成后的目录结构4.3.2 运行…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...