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;
}