1099 字串变换

2002年NOIP全国联赛提高组

定义：

    map<type1,type2>mp;

    相当于一个用type1当下标的数组。

 eg:

    map<double,int>mp;

    mp[2.6]=;

    cout<<mp[2.6];

    //输出３

查找：

直接向数组一样访问就行了，但是要先问一下是否存在。

if(mp.find(x)==mp.end())表示这个下标没有存过。

然后map的各种操作应该（应该？）都是O(log)的。

定义：

    string a;

    //可以定义字符串数组

访问其中下标为i的字母：

    int k=a[i];

    //注意是从0开始排的

在string a里面找子串b

    int pos=a.find(b);

    //如果存在子串b 返回b的第一个字符对应在a里面的下标（若有多个匹配，返回第一个匹配的下标）　否则返回-1

（划重点）

把string a从pos开始长l的字符整体换成字串b

    a.replace(pos,l+,b);

    //stl的区间都是左开右闭的

 /*

     qwerta

     P1032 字串变换

     Accepted

     100

     代码 C++，1.14KB

     提交时间 2018-09-26 19:13:29

     耗时/内存

     26ms, 1432KB

 */

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #include<map>

 using namespace std;

 string a[],b[];

 string ma,mb;

 queue<string>qs;//存字符串

 queue<int>qn;//存对应的转换次数

 int n=;

 map<string,int>m;

 int bfs()

 {

     qs.push(ma);//push初始状态

     qn.push();

     while(!qs.empty()&&qn.front()<)//如果有的搜并且次数不超过10

     {

         int d=qn.front();

         string s=qs.front();

         if(m.find(s)==m.end())//如果s在map中没有被记录过

         {

             m[s]=;//mark一下

             for(int c=;c<=n;++c)//枚举六种变换

             {

                 s=qs.front();

                 while((s.find(a[c]))!=-)//如果找得到子串a[c]

                 {

                     string ss=qs.front();//搞一个辅助的ss

                     int pos=s.find(a[c]);

                     ss.replace(pos,a[c].size(),b[c]);//把ss替换一下

                     if(ss==mb)return d+;//找到了就return

                     qs.push(ss);

                     qn.push(d+);//push当前的收获

                     s[pos]='*';//把s的这一位换成无关字符，这样下一次就会自动搜下一位了

                 }

             }

         }

         qs.pop();qn.pop();

     }

     return -;//搜完了还没搜到则无解

 }

 int main()

 {

     //freopen("a.in","r",stdin);

     ios::sync_with_stdio(false);

     cin.tie(false),cout.tie(false);//cin好伴侣（据说能快过scanf

     cin>>ma>>mb;

     while(cin>>a[n]>>b[n])n++;

     n--;

     int k=bfs();

     if(k==-){cout<<"NO ANSWER!";}

     else cout<<k;

     return ;

 }

不用map：

/*

    qwerta

    P1032 字串变换

    Accepted

    100

    代码 C++，1.14KB

    提交时间 2018-09-26 19:14:03

    耗时/内存

    389ms, 64472KB

*/

//（摔