https://codeforces.com/problemset/problem/1697/C
题意:给定长度为n的字符串s和t,两个字符串均只包含字符abc,现在对s进行操作,ab可变为ba,bc可变为cb,问不限次数操作后,s能否==t。
思路:先看abc数量是否相等,不相等无解。其次,考虑去掉所有b后,s和t是否相等,如果不相等则误解。如果相等,再看s的每个a是否在b的每个a前面或者相同位置,看s中每个c的位置是否都不比t中每个对应的c靠前,因为a只能往后移,c只能往前移。
总结:根据操作很容易想到b可以前移或者后移,联想到没有b的字符串s跟t应该相同,再考虑相同位置上的字符是否真的可以通过变换得到就行了,防止出现s = ba, t = ab无法移动的情况,就通过两个a的下标来考虑就行!所以另一种解法应该是去掉所有的b,然后得到新的s跟t,同时维护两个下标数组,直接看s是否跟t相等,再看下标是否都满足条件就行了。
inline void solve() {int n;string s, t;cin >> n >> s >> t;if (count(s.begin(), s.end(), 'b') != count(t.begin(), t.end(), 'b')) {cout << "NO\n";return; }int j = 0;for (int i = 0; i < n; ++i) {if (s[i] == 'b') {continue;}while (j < n && t[j] == 'b') {j ++;}if (j == n) {cout << "YES\n";return;}if (s[i] != t[j] || (s[i] == 'a' && i > j) || (s[i] == 'c' && i < j)) {cout << "NO\n";return;}j++;}cout << "YES\n";
}