A
容易发现若 \(S\) 串中 \(s_i\) 为特殊字符，则令 \(s_i=s_{i+1}\)，此时 \(s_i\neq s_{i-1}\)。则找到一个 \(j\) 满足 \(s_i=s_{i+1}=s_{i+2}=\ldots=s_j\neq s_{j+1}\)，则 \(s_j\) 也一定为特殊字符。
所以若 \(2\mid n\) 则构造 \(\frac{n}{2}\) 个 AAB，否则必然无解。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
if (n & 1)
cout << "NO\n";
else {
cout << "YES\n";
for (int i = 1; i <= n / 2; i++)
cout << "AAB";
cout << '\n';
}
}
return 0;
}
B
考虑贪心。
首先若原序列 \(a\) 就已经单调不降，那么就已经满足条件。
否则考虑按照下标从小到大来贪心。若一个数拆分成两个数之后和她前面的所有数构成了单调不降，那么就拆分；否则就不拆分。
最后判断一下拆分完之后的序列是否单调不降即可。时间复杂度为 \(O(n)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
int a[N];
signed main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
if (is_sorted(a + 1, a + n + 1))
cout << "YES\n";
else {
vector<int> arr;
for (int i = 1; i <= n; i++) {
int x = a[i] / 10, y = a[i] % 10;
if (x <= y && (arr.empty() || arr.back() <= x))
arr.push_back(x), arr.push_back(y);
else
arr.push_back(a[i]);
}
if (is_sorted(arr.begin(), arr.end()))
cout << "YES\n";
else
cout << "NO\n";
}
}
return 0;
}