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

P1032 [NOIP2002 提高组] 字串变换

[NOIP2002 提高组] 字串变换

题目背景

本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水,各种做法都可以通过,不代表算法正确。因此本题题目和数据仅供参考。

本题为搜索题,本题不接受 hack 数据。关于此类题目的详细内容

题目描述

已知有两个字串 A , B A,B A,B 及一组字串变换的规则(至多 6 6 6 个规则),形如:

  • A 1 → B 1 A_1\to B_1 A1B1
  • A 2 → B 2 A_2\to B_2 A2B2

规则的含义为:在 A A A 中的子串 A 1 A_1 A1 可以变换为 $ B_1 , , A_2$ 可以变换为 B 2 ⋯ B_2\cdots B2

例如: A = abcd A=\texttt{abcd} A=abcd B = xyz B=\texttt{xyz} Bxyz

变换规则为:

  • abc → xu \texttt{abc}\rightarrow\texttt{xu} abcxu ud → y \texttt{ud}\rightarrow\texttt{y} udy y → yz \texttt{y}\rightarrow\texttt{yz} yyz

则此时, A A A 可以经过一系列的变换变为 B B B,其变换的过程为:

  • abcd → xud → xy → xyz \texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz} abcdxudxyxyz

共进行了 3 3 3 次变换,使得 A A A 变换为 B B B

输入格式

第一行有两个字符串 A , B A,B A,B

接下来若干行,每行有两个字符串 A i , B i A_i,B_i Ai,Bi,表示一条变换规则。

输出格式

若在 10 10 10 步(包含 10 10 10 步)以内能将 A A A 变换为 B B B,则输出最少的变换步数;否则输出 NO ANSWER!

样例 #1

样例输入 #1

abcd xyz
abc xu
ud y
y yz

样例输出 #1

3

提示

对于 100 % 100\% 100% 数据,保证所有字符串长度的上限为 20 20 20

【题目来源】

NOIP 2002 提高组第二题

题目解析

这道题目是一个字符串变换问题,我们需要找出将字符串 A 转换为字符串 B 的最少步骤数,或者判断是否无法在 10 步内完成转换。让我为您分析这道题目并提供解题思路。

题目解析:

  1. 我们有两个字符串 A 和 B,以及一组变换规则。
  2. 每个规则允许我们将字符串中的某个子串替换为另一个子串。
  3. 我们需要找出使用这些规则将 A 转换为 B 的最少步骤数。
  4. 如果无法在 10 步内完成转换,我们需要输出 “NO ANSWER!”。

解题思路:
这个问题可以使用广度优先搜索(BFS)来解决。以下是具体的步骤:

  1. 创建一个队列,初始将字符串 A 加入队列。
  2. 创建一个集合来记录已经访问过的字符串,以避免重复处理。
  3. 创建一个变量来记录当前的步数,初始为 0。
  4. 进行 BFS:
    a. 当队列不为空且步数小于等于 10 时,执行以下操作:
    b. 获取当前队列的大小(当前层的节点数)。
    c. 对当前层的每个节点进行处理:
    • 如果当前字符串等于目标字符串 B,返回当前步数。
    • 否则,尝试应用每个变换规则:
      • 找到可以应用规则的所有位置。
      • 对每个位置,生成新的字符串。
      • 如果新字符串没有被访问过,将其加入队列和已访问集合。
        d. 当前层处理完毕后,步数加 1。
  5. 如果 BFS 结束仍未找到目标字符串 B,输出 “NO ANSWER!”。

这种方法的优点是:

  1. 它保证能找到最少的步骤数(如果存在的话)。
  2. 它能有效地避免重复状态,提高效率。
  3. 它能在到达 10 步时及时停止,避免不必要的计算。

实现这个算法时,我们需要注意以下几点:

  1. 使用 C++ 的 string 类来方便地处理字符串。
  2. 使用 unordered_set 来快速检查字符串是否被访问过。
  3. 使用 queue 来实现 BFS。
#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;struct Rule {string from, to;
};int bfs(const string& start, const string& target, const vector<Rule>& rules) {queue<string> q;unordered_set<string> visited;q.push(start);visited.insert(start);int steps = 0;while (!q.empty() && steps <= 10) {int size = q.size();for (int i = 0; i < size; i++) {string current = q.front();q.pop();if (current == target) {return steps;}for (const Rule& rule : rules) {size_t pos = 0;while ((pos = current.find(rule.from, pos)) != string::npos) {string next = current;next.replace(pos, rule.from.length(), rule.to);if (visited.find(next) == visited.end()) {q.push(next);visited.insert(next);}pos += rule.from.length();}}}steps++;}return -1;  // No solution found within 10 steps
}int main() {string A, B;cin >> A >> B;vector<Rule> rules;string from, to;while (cin >> from >> to) {rules.push_back({from, to});}int result = bfs(A, B, rules);if (result != -1) {cout << result << endl;} else {cout << "NO ANSWER!" << endl;}return 0;
}

这个实现使用了上述描述的 BFS 方法。它的主要组成部分是:

  1. Rule 结构体用于存储变换规则。
  2. bfs 函数实现了广度优先搜索算法。
  3. main 函数中,我们读取输入并调用 bfs 函数。

这个解决方案应该能够有效地解决给定的问题。它会找到最少的变换步骤(如果存在的话),或者在无法在 10 步内完成变换时输出 “NO ANSWER!”。

需要注意的是,这个解决方案的时间复杂度可能在最坏情况下相当高,特别是当有很多可能的变换时。然而,考虑到问题的约束(最多 10 步,字符串长度不超过 20),这个解决方案应该能够在合理的时间内处理大多数情况。

相关文章:

P1032 [NOIP2002 提高组] 字串变换

[NOIP2002 提高组] 字串变换 题目背景 本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水&#xff0c;各种做法都可以通过&#xff0c;不代表算法正确。因此本题题目和数据仅供参考。 本题为搜索题&#xff0c;本题不接受 hack 数据。关于此类题目的详细内容 题目…...

Android 12系统源码_多屏幕(一)多屏幕设备显示Activity

前言 分屏&#xff1a;是指一个屏幕分出多个窗口&#xff0c;分别显示不同应用的界面&#xff0c;这在当前的手机设备中很常见。多屏&#xff1a;是指一个设备存在多个屏幕&#xff0c;这些可能是虚拟屏幕或者实体硬件屏幕&#xff0c;不同的应用同时显示在不同的屏幕中&#…...

如何判断IP地址属于住宅IP还是机房IP

在数字化时代,IP地址作为互联网通信的基础标识&#xff0c;扮演着重要的角色。无论是网络管理、数据分析还是安全监控&#xff0c;正确识别IP地址的类型——尤其是区分是住宅IP还是机房IP&#xff0c;对于确保网络安全、优化网络性能以及合法合规运营具有重要意义。IPIDEA代理I…...

C#TreeView控件应用

1、代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms;namespace TestApp…...

计算机网络-数据链路层

基本概念 数据链路和链路 链路&#xff1a;指的是从一个节点到相邻节点的一段物理线路&#xff0c;且中间没有任何其他的交换节点 数据链路&#xff1a;传输数据时&#xff0c;除了一条物理线路&#xff0c;还需要一些必要通信协议来控制这些传输。 数据链路层的三个基本问…...

农场游戏中的时间管理实例

一、准备工作 在Unity中创建承载日期和时间的文本 二、设置游戏的时间戳 using System.Collections; using System.Collections.Generic; using UnityEngine; //标识这个类可以被序列化 [System.Serializable] public class GameTimestamp {// 游戏时间戳的成员变量public in…...

css 数字平铺布局

效果图 <!DOCTYPE html> <html> <head><meta charset"utf-8"><title>活动中心</title><meta name"viewport" content"maximum-scale1.0,minimum-scale1.0,user-scalable0,widthdevice-width,initial-scale1.0…...

【开源】嵌入式Linux(IMX6U)应用层综合项目(2)--智能家居APP

目录 1.简介 1.1功能介绍 1.2技术栈介绍 1.3演示视频 1.4硬件介绍 2.软件设计 2.1智能家居UI设计 2.2.main函数 3.结尾&#xff08;附网盘链接&#xff09; 1.简介 此文章并不是教程&#xff0c;只能当作笔者的学习分享&#xff0c;只会做一些简单的介绍&#xff0c;其…...

CUDA常见编译器配置问题一览

CUDA常见编译器配置问题一览 关注TechLead&#xff0c;复旦博士&#xff0c;分享云服务领域全维度开发技术。拥有10年互联网服务架构、AI产品研发经验、团队管理经验&#xff0c;复旦机器人智能实验室成员&#xff0c;国家级大学生赛事评审专家&#xff0c;发表多篇SCI核心期刊…...

【Android】系统级应用升级后的安装位置

系统级应用的安装位置一般在codePath/system 下面&#xff0c; 如果手动的去进行adb install覆盖安装&#xff0c;通过dumpsys package可以发现是安装在/data/app/里&#xff0c; 如果是通过标准的系统升级方式呢&#xff1f; 这里我们来通过升级查看一下&#xff0c; 升级…...

uniapp 使用renderjs通信

一、 server层向renderjs传值&#xff0c;并初始化renderjs prop&#xff1a;可以随便定义 renderTaskDetail&#xff1a;是传往renderjs的数据 change:prop&#xff1a;prop和必须上面prop字段一样 renderScript.initAmap&#xff1a;【 renderScript】需要renderjs 中scr…...

PostgreSQL 15

一、安装前的准备 1、版本信息 操作系统CentOS 7.9.2009PostgreSQL 版本PostgreSQL 15-15.7 2、下载安装包 RPM Chart - PostgreSQL YUM Repositoryhttps://yum.postgresql.org/rpmchart/进入官网&#xff0c;找到相应版本 点击框选内容 依次进入下载页面&#xff0c;下载相…...

给本地设备搭建一个云端语音助手

概述 本语音助手实现了从关键词唤醒 (KWS) 到语音识别 (ASR) 再到自然语言理解 (NLU) 的完整流程。该系统可以通过监听用户的音频输入,检测指定的关键词,并将用户的语音转换为文本,最后与预设的命令进行匹配,执行相应的操作(具体实现请参考main.py),为你的设备配置远程…...

yolov5车辆类型识别TXT数据集

YOLOV5训练车辆类型识别TXT数据集&#xff0c; 一共1400张图片&#xff0c;共分7个类別&#xff0c; 分别为Bus&#xff0c;Car&#xff0c;SportsCar&#xff0c;MicroBus&#xff0c;Truck&#xff0c;SUV&#xff0c;Jeep是TXT格式的数据集&#xff0c;用LabelImg工具进行标…...

day22(mysql数据库主从搭建)

上午&#xff1a; 1、为mysql添加开机启动chkconfig 2、编辑配置文件my.cnf 3、修改环境变量 4、mysql角色授权 角色不生效 在配置文件中不添加activate_all_roles_on_loginon glibc安装&#xff0c;my.cnf在项目目录之下 rpm安装&#xff0c;my.cnf文件在/etc/my.cnf 5、自…...

返璞归真:通过简化用例来简化用户界面01

Larry Constantine 著harvey 译 我们常被问及精简那些最简化、抽象和通用窗体用例的重要性。到底有多重要呢&#xff1f;在以用户为 中心的设计中&#xff0c;简化那些重要窗体的用例是获得成功的关键。它能够为开发者设计优秀的用户界面 助一臂之力。通过消除不必要的或技术驱…...

书生大模型学习笔记2 - Python

Python实现wordcount 请实现一个wordcount函数&#xff0c;统计英文字符串中每个单词出现的次数。返回一个字典&#xff0c;key为单词&#xff0c;value为对应单词出现的次数。 解题思路&#xff1a;首先把字母转小写>然后把单词取出来去除标点>循环单词列表>key已存…...

JavaScript三级联动jQuery写法

HTML结构 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>三级联动</title><!-- <style…...

无人机挂载抓捕网

一、技术原理与机制 无人机挂载抓捕网装置的技术原理是通过无人机平台的飞行能力和灵活性&#xff0c;结合特制的抓捕网装置&#xff0c;实现对目标的快速、准确抓捕。抓捕网装置在接收到指令后&#xff0c;通过特定机制快速展开并包围目标&#xff0c;从而实现抓捕任务。 二…...

174.地下城游戏——LeetCode

题目 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里&#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

Python 高效图像帧提取与视频编码:实战指南

Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...