Educational Codeforces Round 130 (Rated for Div. 2) C awoo‘s Favorite Problem

柔情只为你懂 2024-03-30 12:24 31阅读 0赞

[Problem - C - Codeforces][]

题意：

给你两个串s,t，有两种操作：

1.把'ab'变成'ba'

2.把'bc'变成'cb'

问你是否可以把s变成t

思路：

要想把s变成t，可以向右扫描，也可以向左扫描

我们考虑向右扫描，这样有个特性就是扫到一半，左边全是排序好的，右边是乱的

**对于这种相邻两项交换的操作，我们可以等效成通过某个字符作为介质进行交换**

对于操作1：因为不能改变字符左边的，因此可以等效为：'b'通过介质'a'向左移动

对于操作2：因此不能改变字符左边的，因此可以等效为：'c'通过介质'b'向左移动

我们从左到右扫描，如果遇到s\[i\]==‘c’或t\[i\]==‘a’，没有任何介质可以把'a’往前移动，因此这种情况直接判NO

如果t\[i\]==‘b’，即要把s\[i\]变成'b'，那么我们可以通过操作1把'b'通过介质'a'移动过来，那么我们可以穿越这些介质'a'，如果遇到的不是'b'，就判NO，否则交换

同理，如果t\[i\]=='c'，那么可以通过操作2把'c'通过介质'b'移动过来，我们同样穿越介质'b'，如果约到的不是'c'就判NO，否则交换

Code：

#include <bits/stdc++.h>
    using namespace std;
    int n,a=0,b=0;
    string s,t;
    void solve(){
    	a=0,b=0;
    	cin>>n>>s>>t;
    	for(int i=0;i<=n-1;i++){
    		a=max(i,a),b=max(i,b);
    		if(s[i]!=t[i]){
    			if(s[i]=='c'||t[i]=='a'){
    				cout<<"NO"<<'\n';
    				return;
    			}
    			if(t[i]=='b'){
    				while(s[a]=='a'&&a<=n-1) a++;
    				if(s[a]=='c'||a>=n){
    					cout<<"NO"<<'\n';
    					return;
    				}else swap(s[i],s[a]);
    				}else if(t[i]=='c'){
    					while(s[b]=='b'&&b<=n-1) b++;
    					if(s[b]=='a'||b>=n){
    						cout<<"NO"<<'\n';
    						return;
    					}else swap(s[i],s[b]);
    				}
    			}
    		}
    		cout<<"YES"<<'\n';
    	}
    int main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

**总结：**

**操作题先去等效操作，再去考虑题目本身**

**对于这种相邻两项交换的操作，我们可以等效成通过某个字符作为介质进行交换**

**对于s变成t的题型，考虑从左到右去一一对应，注意左边对应好的部分不能去破坏它**

[Problem - C - Codeforces]: https://codeforces.com/contest/1697/problem/C