Codeforces-1697 C: awoo‘s Favorite Problem

题目传送门：Codeforces-1697 C

  给定两个长度为 n n n 的字符串 s s s 和 t t t。每个字符串中包含三种字符：a、b、c。
  现在可以做两种操作：将 s s s 字符串中的 “ab” 换成 “ba”；将 s s s 字符串中的 “bc” 换成 “cb”。问能否经过任意数量的这两种操作，将 s s s 转换为 t t t。

  首先，两个字符串里的各种字符对应的数量应该是一样的。
  之后我们考虑给出的两个移动方式，这个题是将交换移动变成了单向交换，若是 a 与 b 可以互换，b 与 c 可以交换，那么我们很容易可以看出，这种方案就相当于 b 可以在字符串中自由移动。这种情况下，只需要检查 s s s、 t t t 中把 b 去掉后 a、c 出现的顺序是否一致即可。
  现在我们加入了 b 移动的方向，即只能从 a 右边移动到 a 的左边，只能从 c 左边移动到 c 右边。这也是一种移动， a、c 不会被交换，因此第二段的结论不变。这里可能要有种动态规划的直觉，我们假设第 i i i 个非 b 字符前的位置都已经匹配好了，即 s 1 ⋯ i = t 1 ⋯ i s_{1cdots i}=t_{1cdots i} s1⋯i​=t1⋯i​。 实际上我们此时只要考虑下一个非 b 字符能否调整周围可以调整的 b 来匹配 t t t 即可，这个是可以暴力模拟出来的。
  题解给了另一种醒目的做法：对于 s s s 中下一个非 b 字符位置 j j j，我们要匹配 t t t 中对应的位置 k k k。若这个字符为 a，那么 s s s 右边要有充足的字符去调整 a 的位置，且这个位置只能向右，此时若 j > k j > k j>k，那么无论怎么调整，两个字符都无法匹配到，同理，若这个字符是 c，那么 j < k j < k j   将操作理解为 a、c 的移动也是不错的选择。

#include 
using namespace std;

int main() {
   int T, n; string s, t;
   cin >> T;
   while(T--) {
       cin >> n >> s >> t;
       map M;
       for(int i=0; i
           cout << "NO" << endl; fl = true; break;
       }
       if(!fl) {
           for(int l=0, r=0; l
               while(s[l] == 'b') ++l;
               while(r
                   if(t[r] != 'b') {
                       fl = true;
                       l=n; break;
                   }
                   ++r;
               }
               if(l == n) break;
               if(s[l] == 'a' && l > r) fl=true, l=n;
               if(s[l] == 'c' && l < r) fl=true, l=n;
           }
           if(fl) cout << "NO" << endl;
           else cout << "YES" << endl;
       }
   }
   return 0;
}