Dog Tricks

题目描述

The videos showcasing a wide variety of tricks performed by your two pet dogs, Amy and Bessie, have become popular content in the Icpca Kingdom. To explore the potential for further videos, you taught the dogs a new trick.

The new trick is performed using plates aligned from left to right. Each plate holds either an apple or a banana.

When you command Amy, she holds a banana in her mouth and looks at each plate in turn from left to right. She skips any plate with a banana and, upon reaching the first plate with an apple, places the banana she was carrying on that plate, picks up the apple, and continues to the right. Then she skips any plate with an apple and, upon reaching the first plate with a banana, places the apple she was carrying on that plate, picks up the banana, and comes back to you, successfully completing the trick. If the fruits on the plates are not arranged in a way that allows this, the trick fails.

When you command Bessie, she holds an apple in her mouth and looks at each plate in turn from left to right. She skips any plate with an apple and, upon reaching the first plate with a banana, places the apple she was carrying on that plate, picks up the banana, and continues to the right. Then she skips any plate with a banana and, upon reaching the first plate with an apple, places the banana she was carrying on that plate, picks up the apple, and comes back to you, successfully completing the trick. If the fruits on the plates are not arranged in a way that allows this, the trick fails.

You cannot command both dogs simultaneously, nor can you command one dog while the other is performing a trick.

In the next video project, you want to rearrange the fruits on the plates into the target state by repeatedly having the dogs perform successful tricks. You are given the initial and target states of the fruits on the plates. Starting from the initial state, can you rearrange the fruits on the plates into the target state by issuing no more than a specified number of commands to Amy and Bessie in an appropriate order? If possible, find a sequence of such commands.

输入

The input consists of at most 100 test cases, each in the following format.
n
s
t
Each test case consists of three lines. The first line contains an integer n between 1 and 100, inclusive, representing the number of plates. The second line contains a string s representing the initial state. If the i-th character of s is a, an apple is on the i-th plate from the left in the initial state; if it is b, a bananais on it. The third line contains a string t representing the target state. If the i-th character of t is a, an apple should be on the i-th plate from the left in the target state; if it is b, a banana should be on it. Both s and t consist only of a and b, and they both have length n. Strings s and t are not identical.
The end of the input is indicated by a line consisting only of a zero.

输出

For each test case, output yes in a line if there exists a sequence of 10 000 or less commands to the dogs that rearranges the initial state to the target state; otherwise, output no in a line. In addition, if such a sequence exists, output a string representing the command sequence in the next line. The string should consist of the characters A and B. Its i-th character being A means the i-th command is to Amy, while its being B means the command is to Bessie. If there are two or more such sequences, any of them is accepted.

样例输入

2
aa
bb
3
bba
bab
4
aaba
abaa
0

样例输出

no
yes
BA
yes
AB

提示

In the second test case of Sample Input 1, starting from the initial state bba, you first command Bessie. She replaces the leftmost banana with an apple, resulting in aba, and then she replaces the rightmost apple with a banana, resulting in abb. Next, you command Amy. She replaces the leftmost apple with a banana, resulting in bbb, and then she replaces the next banana with an apple, resulting in bab. This matches the target state.

题目大意：有两种操作，A是找到字符串中第一个出现的a和a之后第一个出现的b，将ab互换；B是找到字符串中第一个出现的b和b之后第一个出现的a，将ba互换。问能否使用不超过10000次A和B操作，使得字符串s变成字符串t。

思路：可以发现每次操作都是交换的操作，不会改变a和b的数量，所以如果两个字符串中a的数量不相等，那么一定是无法交换成功的，反之，如果不限制操作次数的话，是一定可以通过若干次交换将s变成t的。

但这个次数限制究竟会影响什么呢？我们先不管这个操作次数，由于每次交换都是找到最前面的a和b，为了不影响已经处理过的字符，我们从最后一位开始，比两个字符串的每一位，如果不同，就需要交换，如果当前位为'a'那我们就需要把'b'和'a'互换，不断进行操作B，直到将这一位换成正确的；反之，当前位为'b'那我们就不断进行操作A。经过这些操作后，可以发现我们最多只需要操作n^2次，就一定可以将s变成t，而字符串的长度最多是100，也就是最多10000次操作，我们就可以实现，所以这个次数的限制实际上是没有影响的，我们只需要判断两个字符串中a的数量是否相同，如若不同，直接输出no，否则，一定是yes，从最后一位开始比较，按照上面的方法执行操作AB即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<int,int> PII;
const int N=100010;
int n;
int op(string &s,char x,char y,int m,int cur,int ans){//从0到m，换到了都cur位，换x,y if(cur>m)return ans;int tt;for (int i=0;i<m;i++){if (s[i]==x){tt=i;break;}}for (int i=tt+1;i<m;i++){if (s[i]==y){swap(s[tt],s[i]);ans++;break;}}return op(s,x,y,m,cur+1,ans);
} 
void solve(int n){string s,t;cin>>s>>t;int cnt1=0,cnt2=0;for (int i=0;i<n;i++){if (s[i]=='a')cnt1++;if (t[i]=='a')cnt2++;}if (cnt1!=cnt2){cout<<"no\n";return ;}cout<<"yes\n";int ans;ans=op(s,'b','a',n,0,0);//cout<<ans<<' '<<s<<"\n";for (int i=0;i<ans;i++){cout<<"B";}for (int i=n-1;i>=0;i--){if (s[i]!=t[i]){if(s[i]=='a'){//把a移到前面去,换ba ans=op(s,'b','a',i+1,0,0);//cout<<ans<<' '<<s<<"\n";for (int i=0;i<ans;i++)cout<<"B";}else{ans=op(s,'a','b',i+1,0,0);//cout<<ans<<' '<<s<<"\n";for (int i=0;i<ans;i++)cout<<"A";}}}cout<<"\n";return ;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);while(cin>>n){if (n==0)return 0;solve(n);}
}