Rebranding[Codeforces 591B]

Rebranding(CodeForces 591B)

: Codeforces Round #327 (Div. 2) Time:2000ms Memory:256MB

这道题主要是模拟字符串序列操作。最简单的办法便是直接对整个字符串进行操作，然而题目中字符串的长度$m$的最大取值为$200000$，最多可能的操作次数$n$的最大取值也是$200000$，因此$O(mn)$的时间复杂度是会超时的。（事实是确实有这么变态的数据，一开始fgets 200000长度都RE了）

从另一个角度考虑这个问题，在每一次操作过程当中，只是将对应的字母整体作了变换操作。

以第二个样例的第一次操作为例：

abacabadaba
其进行a b操作后，变为

babcbabdbab可以观察到原先的a位置全部变为b，原先的b全部变为了a，因此可以存储每个字母对应的下标位置，进行操作时a b时，就可以转化为将原先a指向a替换为a指向b，b指向b替换为b指向a。后续操作是建立在当前操作的基础之上，当前操作是正确的，利用循环不变式不难证明整个过程也是正确的，这里略去不证。

因此我在这里用一个队列数组保存每个字母对应的出现位置，每当扫进一个字母时，根据字母的对应关系将其进入相应的队列，从而在最终进行操作时，只是将队列的指针发生了移动，因而提高了效率，最后依据序号逐次将字母输出即可。该方法整体的时间复杂度为$O(m+n)$（初始化队列和队列输出中的第二层循环的贡献都可以看作是常数$k=26$，可略去），明显优于$O(mn)$的方法。

后来查阅CF题解时，我的大体思路是正确的，只是他用str数组来实现计算偏移代码实现更简洁，少了队列本身扩张的常数时间开销（队列的ENQUEUE和DEQUEUE都是$O(1)$时间的，因此对整个复杂度没有影响，但是内存分配确实会影响性能，好在STL采用多层分配器来实现，性能确实没有想象的那么差。）。

我的C++实现如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 char str[200006];
 6 queue<int> * mapper[30];
 7 int main()
 8 {
 9     for (int m = 0; m < 26; m++)
10         mapper[m] = new queue<int>;
11     int len, T;
12     cin >> len >> T;
13     getchar();
14     fgets(str, 200005, stdin);
15     for (int i = 0; i < len; i++)
16         mapper[str[i] - 'a']->push(i);
17     while (T--)
18     {
19         char a, b;
20         scanf("
%c %c", &a, &b);
21         if (a == b)continue;
22         queue<int> * tmpptr = mapper[b - 'a'];
23         mapper[b - 'a'] = mapper[a - 'a'];
24         mapper[a - 'a'] = tmpptr;
25     }
26     for (int i = 0; i < len; i++)
27         for (int j = 0; j < 26; j++)
28         {
29             if (mapper[j]->empty() == false)
30             {
31                 if (mapper[j]->front() == i)
32                 {
33                     putchar(j + 'a');
34                     mapper[j]->pop();
35                     break;
36                 }
37             }
38         }
39     return 0;
40 }

CF给的标程实现如下：

 1 #include <bits/stdc++.h>
 2 #define fi first
 3 #define sc second
 4 using namespace std;
 5 typedef pair<int,int> pi;
 6 char s[300009];
 7 char ch[30];
 8 int main(){
 9     int n,m;scanf("%d%d",&n,&m);
10     scanf("%s",s);
11     for(int i=0;i<26;i++)ch[i]=i+'a';
12     for(int i=0;i<m;i++){
13         char a,b;scanf(" %c %c",&a,&b);
14         for(int j=0;j<26;j++){
15             if(ch[j]==a)ch[j]=b;
16             else if(ch[j]==b)ch[j]=a;
17         }
18     }
19     for(int i=0;i<n;i++){
20         printf("%c",ch[s[i]-'a']);
21     }
22 }