P1032 题解

· · 题解

题目大意

有两个个字符串 a,b，有至多 6 个规则，可以把一个子字符串变换为另一个字符串。求至少多少次可以将 a 变成 b。

补充一下字符串的几个内置函数

string s;

  1. s.begin() 返回字符串 s 第一位下标的迭代器。
  2. s.end() 返回字符串 s 最后一位的下一个迭代器。
  3. s.substr(pos,len) 返回从下标 pos 开始 len 个字符构成的字符串。
  4. s.erase(pos_st,pos_nd) 删除从迭代器 pos_{st} 到迭代器 pos_{nd} 之间的所有字符。

    输入部分 while(cin)

    cin>>a>>b;
while(cin>>s[++tot].u){
cin>>s[tot].v;
maxl=max(maxl,int(s[tot].u.length()-s[tot].v.length()));
}
tot--;

    思路一：纯 dfs 暴力

    #include<iostream>
#include<string>
using namespace std;
string a,b;
string u[10],v[10];
string etr;
int tot,ans=0x7fffffff;
void dfs(string now,int step){
if(now==b){
    ans=min(ans,step);
    return;
}
if(step>=10){
    return;
}
string nown;
for(int i=1;i<=tot;i++){
    int lenu=u[i].length(),lenn=now.length(),lenv=v[i].length();
    for(int j=0;j+lenu-1<lenn;j++){
        if(now.substr(j,lenu)==u[i]){
            nown=now;
            nown.erase(nown.begin()+j,nown.begin()+j+lenu);
            nown=nown.substr(0,j)+v[i]+nown.substr(j,lenn-lenu-j);
            dfs(nown,step+1);
        }
    }
}
}
int main(){
cin>>a>>b;
while(cin>>u[++tot]){
    cin>>v[tot];
}
tot--;
dfs(a,0);
if(ans>=0x7fffffff) printf("NO ANSWER!");
else printf("%d",ans);
return 0;
}

    60pts,TLE

    思路二：

    输入后对字符串从短到长排序，可以减少一部分复杂度。

    #include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string a,b;
int tot,ans=0x7fffffff,maxl=0;
struct node{
string u,v;
bool operator<(const node& tmp){
    return v.length()<tmp.v.length();
}
}s[10];
inline void dfs(string now,int step){
if(now.length()>b.length()+maxl*10) return;
if(now==b){
    ans=min(ans,step);
    return;
}
if(step>=10 || step>=ans){
    return;
}
string nown;
for(int i=1;i<=tot;i++){
    int lenu=s[i].u.length(),lenn=now.length();
    for(int j=0;j+lenu-1<lenn;j++){
        if(now.substr(j,lenu)==s[i].u){
            nown=now;
            nown.erase(nown.begin()+j,nown.begin()+j+lenu);
            nown=nown.substr(0,j)+s[i].v+nown.substr(j,lenn-lenu-j);
            dfs(nown,step+1);
        }
    }
}
}
int main(){
cin>>a>>b;
while(cin>>s[++tot].u){
    cin>>s[tot].v;
    maxl=max(maxl,int(s[tot].u.length()-s[tot].v.length()));
}
tot--;
sort(s+1,s+tot+1);
dfs(a,0);
if(ans>=0x7fffffff) printf("NO ANSWER!");
else printf("%d",ans);
return 0;
}

    80pts,TLE

    思路三

    最后，使用 map 对字符串去重，大大减少了从不同方式求得相同字符串而占用的时间。\ 给出 AC 代码

    #include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
string a,b;
int tot,ans=0x7fffffff,maxl=0;
struct node{
string u,v;
bool operator<(const node& tmp){
    return v.length()<tmp.v.length();
}
}s[10];
map<string,int>mp;
void dfs(string now,int step){
if(mp[now]==1) return;
mp[now]=1;
if(now.length()>b.length()+maxl*10) return;
if(now==b){
    ans=min(ans,step);
    return;
}
if(step>=10 || step>=ans){
    return;
}
string nown;
for(int i=1;i<=tot;i++){
    int lenu=s[i].u.length(),lenn=now.length();
    for(int j=0;j+lenu-1<lenn;j++){
        if(now.substr(j,lenu)==s[i].u){
            nown=now;
            nown.erase(nown.begin()+j,nown.begin()+j+lenu);
            nown=nown.substr(0,j)+s[i].v+nown.substr(j,lenn-lenu-j);
            dfs(nown,step+1);
        }
    }
}
}
int main(){
cin>>a>>b;
while(cin>>s[++tot].u){
    cin>>s[tot].v;
    maxl=max(maxl,int(s[tot].u.length()-s[tot].v.length()));
}
tot--;
sort(s+1,s+tot+1);
dfs(a,0);
if(ans>=0x7fffffff) printf("NO ANSWER!");
else printf("%d",ans);
return 0;
}

    100pts,AC!