A - A ↔ BB

题意

给出一串由A,B,C组成的字符串，遇到以下两种情况时
当出现A时，将A替换为BB
当出现BB时，将BB替换为A

思路

直接用stack来模拟

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6;
char str[N], ans[N];
stack<char> stk;
int main(){
	int N;
	cin >> N;
	scanf("%s", str);
	int num = 0, cntB = 0;
	stk.push(str[0]);
	for(int i = 1; i < N; i ++) {
		//cout << stk.top() << endl;
		if(str[i] == 'B') {
			//cout << 1 << endl;
			if(stk.top() == 'B') {
				stk.pop();
				stk.push('A');
			}
			else {
				stk.push('B');
			}
		}
		else if(str[i] == 'A'){
			if(stk.top() == 'B') {
				stk.pop();
				stk.push('A');
				stk.push('B');
			}
			else {
				stk.push('A');
			}
		}
		else stk.push(str[i]);
	}
	while(stk.size()) {
		ans[num ++] = stk.top();
		stk.pop();
	}
	for(int i = num - 1; i >= 0; i --) {
		printf("%c", ans[i]);
	}
	cout << endl;
	
	
	
	return 0;
} 

B - Triple Shift

题意

给出序列A和B
能进行任意次以下操作：
将Ai,Ai+1,Ai+2中的Ai+2移到最前面,变为Ai+2,Ai,Ai+1
问能否通过这样的操作构成B序列

思路

对于每个B中出现的数的次数肯定要与A中出现的数的次数对应，用桶来存出现次数，如果不相等那一定不能转换为B序列。
当A中有相同数字的时候，会发现序列的顺序就不再固定了，所以必定可以转换为B序列（这里证明我证不出来，但是推几次会发现任意有相同的都可以转变成我们要的B序列）
一般情况就是通过逐位模拟，找到我们要的数字，移到当前位来

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N], b[N], ta[N], tb[N];
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		ta[a[i]] ++;
	}
	for(int i = 1; i <= n; i ++) {
		cin >> b[i];
		tb[b[i]] ++;
	}
	bool flag = true;
	for(int i = 1; i <= 5000; i ++) {
		if(ta[i] != tb[i]) {
			flag = false;
			cout << "No" << endl;
			return 0;
		}
		if (ta[i] > 1) 
    	{
    		cout << "Yes\n";
     		return 0;
   		}
	}
	flag = false;
	int x = a[1], y = a[2], z = a[3];
	int cnt = 0;
	for(int i = 1; i <= n - 2; i ++) {
		x = a[i], y = a[i + 1], z = a[i + 2];
		cnt = 0;
		for(int j = i; j <= n; j ++) {
			if(a[j] == b[i]) {
				cnt = j;	
				break;
			}
		}
		while(cnt - i > 1) {
			swap(a[cnt], a[cnt - 2]);
			swap(a[cnt], a[cnt - 1]);
			cnt -= 2;
		}
		if(cnt - i == 1) {
			swap(a[cnt], a[cnt - 1]);
			swap(a[cnt], a[cnt + 1]);
		}
	}
 	if(a[n] == b[n] && a[n - 1] == b[n - 1]) {
 		cout << "Yes" << endl;
	 }
	 else cout << "No" << endl;
	 
	return 0;
}

剩下题目待补。。。