首页 > [NOIP2002]字串变换
开通博客写题解
头像 savage
发表于 2019-08-29 15:34:59
题目描述 已知有两个字串 A, B及一组字串变换的规则（至多6个规则）: A1 -> B1 A2 -> B2 规则的含义为：在A中的子串 A1可以变换为 B1、A2可以变换为 B2 …。 例如：A＝'abcd'　B＝'xyz' 变换规则为： ‘abc 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 不属于这个时代的愚者忠实信徒
发表于 2023-07-21 19:34:56
这题用dfs暴力能过，这里是参考大佬代码，用的双向广搜（正好早上在看这个知识点？） #include<iostream> #include<math.h> #include<vector>       展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Reyortsed
发表于 2021-11-11 07:46:08
题意：给你一个初始字符串和一个目标字符串，还有一些变换规则，问你用这些变换规则最小要多少步可以将初始字符串变为目标字符串。 看体面感觉没什么，而且数据范围也不大，我直接写了一个bfs，交了，洛谷上过了，但是牛客没过，t了，这就很离谱了，我应该说牛客数据很顶还是说洛谷数据太水了呢，而且洛谷 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 Z_L_G
发表于 2025-04-07 23:00:35
题意 给定两个字符串a，b，不超过6条变换规则，,如果能在十步以内使用变换规则将a变换为b，输出步数，否则输出NO ANSWER! 思路 对于最优极限情况，每一步内a可用6次变换规则，总复杂度为6^10 只要超过两种规则出现重复使用，单项搜索就会TLE 所以使用双向搜索，维护两个队列，一个从a 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 ZZZYM
发表于 2022-02-21 12:07:54
字串变换 参考题解 思路 由于字符串变换的状态很多，空间复杂度和时间复杂度过大，所以采用双向广搜 代码 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”