CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

B. AB Flipping

老规矩，自己要模拟一遍样例，发现样例还不够，就自己构造样例，这样做着做着就会有思路。

分析：假如现在有这样一个字符串 BBBAABABBAAA。会发现前三个和后三个一定是不会被操作的，因为不会满足si = 'A'，si+1 = 'B'。然后自己模拟，会发现中间的所有位置一定会可以被操作。

#include<assert.h>
#include<cstdio>
#include<set>
#include<list>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<sstream>
#include<stack>
#include <utility>
#include<map>
#include <vector>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
//2147483647

//#define int long long
//#include <bits/stdc++.h>
typedef long long ll;
#include<iostream>
using namespace std;

const int N = 1e6 + 10;

void solve() {
	int n; cin >> n;
	string s; cin >> s;
	int sz = s.size();
	int cnt = 0;
	for (int i = 0; i < sz; i++) {
		if (s[i] == 'B') cnt++;
		else break;
	}
	for (int i = sz - 1; i >= 0; i--) {
		if (s[i] == 'A') cnt++;
		else break;
	}
	//cout << "答案：";
	cout << max(0, n - 1 - cnt) << endl;
}

signed main()
{
	int t; cin >> t;
	while (t--) {
		solve();
	}

	

	return 0;
}

C. Matching Arrays

Example

input

Copy

1 0

1 1

3 0

2 4 3

4 1 2

3 1

2 4 3

4 1 2

3 2

2 4 3

4 1 2

3 3

2 4 3

4 1 2

5 2

6 4 5 6 2

9 7 9 1 1

output

Copy

YES
2
NO
NO
YES
2 4 1
YES
4 1 2
NO
YES
1 9 9 7 1

分析：因为可以ai对应的bi是可以自己决定的，这代表原有的数组a，b的顺序不重要，只要在输出的时候知道ai对应的bi是什么即可。所以我们对a和b进行预排序，对a排降序，对b排升序。

我们贪心地想，如果1<=i<=x && ai>bi，i>x && ai<=bi，那么就一定YES。反之就是NO。

这样的话ai对应的bi就可以找到了，那么如何输出呢？因为刚刚对a排序，我们现在要“反排序”，使a变回原来的样子，该怎么做？

将a定义成结构体，其中有index存每个元素的原下标，再定义一个cmp用于“反排序“就行。

int b[N];
struct Node {
	int index;
	int val_a;
	int val_b;
 
}a[N];
 
bool cmp1(Node e1, Node e2) {
	return e1.val_a < e2.val_a;
}
bool cmp2(Node e1, Node e2) {
	return e1.index < e2.index;
}
 
void solve() {
	int n, x; cin >> n >> x;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].val_a;
		a[i].index = i;
	}
	for (int i = 1; i <= n; i++) cin >> b[i];
 
	sort(a + 1, a + 1 + n, cmp1);
	sort(b + 1, b + 1 + n);
 
	int f = 1;
	for (int i = 1; i <= x; i++) {
		if (a[n - x + i].val_a <= b[i]) {
			f = 0;
			break;
		}
		else {
			a[n - x + i].val_b = b[i];
		}
	}
 
	for (int i = 1; i <= n-x; i++) {
		if (a[i].val_a > b[x + i]) {
			f = 0;
			break;
		}
		else {
			a[i].val_b = b[x + i];
		}
	}
 
	sort(a + 1, a + 1 + n, cmp2);
	//cout << "答案：";
	if (!f) cout << "NO" << endl;
	else {
		cout << "YES" << endl;
		//cout << "答案：";
		for (int i = 1; i <= n; i++) {
			if (i != 1) cout << " ";
			cout << a[i].val_b;
		}
		cout << endl;
	}
 
}
 
 
 
signed main() {
	int t; cin >> t;
	while (t--) {
		solve();
 
	}
 
 
 
	return 0;
}