首页 > 其他分享 >[NOIP2002 提高组] 字串变换

[NOIP2002 提高组] 字串变换

时间:2022-09-23 14:33:49浏览次数:70  
标签:temp NOIP2002 变换 texttt 字串 str include rightarrow

[NOIP2002 提高组] 字串变换

题目背景

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

题目描述

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

  • \(A_1\to B_1\)。
  • \(A_2\to B_2\)。

规则的含义为:在 \(A\) 中的子串 \(A_1\) 可以变换为 $ B_1\(,\)A_2$ 可以变换为 \(B_2\cdots\)。

例如:\(A=\texttt{abcd}\),\(B=\texttt{xyz}\),

变换规则为:

  • \(\texttt{abc}\rightarrow\texttt{xu}\),\(\texttt{ud}\rightarrow\texttt{y}\),\(\texttt{y}\rightarrow\texttt{yz}\)。

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

  • \(\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}\)。

共进行了 \(3\) 次变换,使得 \(A\) 变换为 \(B\)。

输入格式

第一行有两个字符串 \(A,B\)。

接下来若干行,每行有两个字符串 \(A_i,B_i\),表示一条变换规则。

输出格式

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

样例 #1

样例输入 #1

abcd xyz
abc xu
ud y
y yz

样例输出 #1

3

提示

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

【题目来源】

NOIP 2002 提高组第二题

思路:使用bfs暴力搜索所有的情况,第一次出现时所经过的步骤就是最优解

最开始的时候我其实犯了一个错误,就是没有意识到一个相同的字符串是可以转换成不同的字符串(测试点1),由此我将转换关系用unordered_map来存储,导致一个字符串只存在一种对应关系。修改后使用pair来存储。这也提醒了我在题目没有明确说明唯一对应关系的条件下,盲目使用类似哈希表一一的对应结构是一种不负责任的行为

第一次代码提交


#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
queue <string> q;
string final_str,begin_str,end_str="this_is_end_str";
vector<pair<string,string>>change;
const int MAX_STEP=10;
void bfs()
{
    int ans=0;
    q.push(begin_str);
    q.push(end_str);
    while(!q.empty()&&ans<=MAX_STEP)
    {
        string first=q.front();
        q.pop();
        if(first==end_str)
        {
            ans++;
            q.push(end_str);
            continue;
        }
        for(auto change_str:change)
        {
            int pos=0;
            while((pos=first.find(change_str.first,pos))!=string::npos)
            {
                string temp=first;
                temp.insert(pos+change_str.first.size(),change_str.second);
                q.push(temp.replace(pos,change_str.first.size(),""));       
                pos++;
                if(q.back()==final_str)
                {
                    cout<<ans+1<<endl;
                    return;
                }
            }
        }
    }
    if(ans>MAX_STEP)cout<<"NO ANSWER!"<<endl;
}
int main()
{
    cin>>begin_str>>final_str;
    pair<string,string>temp;
    while(cin>>temp.first>>temp.second)change.push_back(temp);
    bfs();
    return 0;
}

第二次代码优化

使用unordered_map进行优化,记录已经操作过的字符串,再次出现便不再压入队列中去
这次优化后代码速度和内存消耗少了许多,由于数据太水,上一个提交竟然能通过。这次提交能通过题解中大佬们提供的额外数据,但是上一个。。。。。。(我随便复制了个数据都过不了,直接卡住了。。。。)

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <unordered_map>//记录重复操作字符串
using namespace std;
queue <string> q;
unordered_map<string,int>map;
string final_str,begin_str,end_str="this_is_end_str";
vector<pair<string,string>>change;
const int MAX_STEP=10;
void bfs()
{
    int ans=0;
    q.push(begin_str);
    q.push(end_str);
    while(!q.empty()&&ans<=MAX_STEP)
    {
        string first=q.front();
        q.pop();
        if(first==end_str)
        {
            ans++;
            q.push(end_str);
            continue;
        }
        for(auto change_str:change)
        {
            int pos=0;
            while((pos=first.find(change_str.first,pos))!=string::npos)
            {
                string temp=first;
                temp.insert(pos+change_str.first.size(),change_str.second);
                temp.replace(pos,change_str.first.size(),"");
                if(!map[temp]) 
                {
                    map[temp]++;
                    q.push(temp);
                    if(temp==final_str)
                    {
                        cout<<ans+1<<endl;
                        return;
                    }
                }      
                pos++;
            }
        }
    }
    if(ans>MAX_STEP)cout<<"NO ANSWER!"<<endl;
}
int main()
{
    cin>>begin_str>>final_str;
    pair<string,string>temp;
    while(cin>>temp.first>>temp.second)change.push_back(temp);
    bfs();
    return 0;
}

标签:temp,NOIP2002,变换,texttt,字串,str,include,rightarrow
From: https://www.cnblogs.com/jyhlearning/p/16722602.html

相关文章

  • 深入浅出WPF变换(Transform)之矩阵(Matrix)
    背景知识Matrix是一个用于在二维坐标系中进行坐标转换的3*3仿射变换矩阵。什么是仿射变换?为什么是3*3,不是2*2?好的,让我们来复习一下(以下内容来自百度百科):仿射变换,又称仿......
  • 字符串变换最小字符串
    题目给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。变换规则:交换字符串中任意两个不同位置的字符。输入描述:一串小写字母组......
  • 霍夫变换原理及实现(Opencv C++)
    已知一幅图像中的n个点,假设我们希望找到这些点中位于直线上的子集。一种可能的解决方法是,首先找到由每对点确定的所有直线,然后寻找靠近特定直线的那些点的所有子集。这种方......
  • 查出两个字符串中的最长字串
    importjava.util.Scanner;publicclasstest01{publicstaticvoidmain(String[]args){/*Scannerscanner=newScanner(System.in);Stringstr......
  • 信息学奥赛一本通 1314:【例3.6】过河卒(Noip2002)
    时间限制:1000ms      内存限制:65536KB提交数:26367   通过数:11410【题目描述】棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下......
  • 洛谷 P1036 [NOIP2002 普及组] 选数(dfs)
    https://www.luogu.com.cn/problem/P1036题目大意:从给定的n个数中选出m个求和,结果是一个素数的情况有多少种?输入43371219输出1这个题目的代码是根据Acwing中......
  • 【JS】6. Z 字形变换
    6.Z字形变换二维数组模拟就是找出放单词位置的规律出来varconvert=function(s,numRows){//如果要求的行数都超过了字符串的长度或者本身行数要求就为1......
  • Abel 变换的一个代数证明
    Abel变换的一个形式:\[\sum^{n}_{i=1}a_ib_i=\sum^{n-1}_{i=1}b_{i}(a_{i}-a_{i+1})+\sum^{n}_{i=1}b_{i}a_{n}\]别的形式可以看百度百科.几何证明比较容易就不说......
  • NTT(快速数论变换)
    NTT(快速数论变换)在取模的情况下,解决多项式乘法.n,m表示多项式的次数,从低到高读入constintNR=1<<22,g=3,gi=332748118,mod=998244353;//998244353的......
  • 【瞎口胡】快速数论变换 NTT
    在FFT中,因为是浮点数计算因此会掉精度。如果你不知道FFT是什么,请阅读这里。如果在模意义下,我们可以选择不使用复平面的单位根,而是模意义下的单位根。考虑单位根的性......