CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
基本情况
A题花了快半小时，做出来了但是不如正解。
B题又是老毛病，一条路走到黑，爆搜打出来超时就死命想剪枝和记忆化，没想过换方法（觉得贪心不可行）。
A - Jagged Swaps
我的解法
没啥好说的，纯模拟。看到 \(n \leq 10\) 知道能过。
但是细节上出了一些问题导致快半小时才做出来。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[15];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
bool is_right = true, is_wrong = false;
for (int i = 1 ; i <= n; i++)
{
cin >> a[i];
if (a[i] < a[i - 1])
{
is_right = false;
}
if (a[i] == a[i - 1])
{
is_wrong = true;
}
}
if (is_right)
{
cout << "YES" << endl;
continue;
}
if (is_wrong)
{
cout << "NO" << endl;
continue;
}
bool toDo = false;
bool is_solve = true;
do
{
is_solve = true;
toDo = false;
for (int i = 2; i <= n - 1; i++)
{
if (a[i] > a[i + 1])
{
if (a[i] > a[i - 1])
{
toDo = true;
swap(a[i], a[i + 1]);
}
}
}
for (int i = 2; i <= n; i++)
{
if (a[i] < a[i - 1] || a[i] == a[i - 1])
{
is_solve = false;
}
}
}
while (toDo);
if (!is_solve)
{
cout << "NO" << endl;
}
else
{
cout << "YES" << endl;
}
}
return 0;
}
更优解法
Observe that since we are only allowed to choose \(i \ge 2\) to swap \(a_i\) and \(a_{i+1}\), it means that \(a_1\) cannot be modified by the operation. Hence, \(a_1 = 1\) must hold. In fact, we can prove that as long as \(a_1 = 1\), we will be able to sort the array.
Consider the largest element of the array. Let its index be \(i\). Our objective is to move \(a_i\) to the end of the array. If \(i=n\), it means that the largest element is already at the end. Otherwise, since \(a_i\) is the largest element, this means that $a_{i−1}<a_i $ and \(a_i > a_{i + 1}\). Hence, we can do an operation on index \(i\) and move the largest element one step closer to the end.
We repeatedly do the operation until we finally move the largest element to the end of the array. Then, we can pretend that the largest element does not exist and do the same algorithm for the prefix of size \(n−1\). Hence, we will able to sort the array by doing this repeatedly.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vi;
int main() {
int t;
cin >> t;
while (t --> 0) {
int n;
cin >> n;
vi arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (arr[0] == 1) {
cout << "YES";
} else {
cout << "NO";
}
cout << '\n';
}
}
B - AB Flipping
我的解法，搜索加剪枝，疯狂TLE。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x7fffffffffffffff
#define re register
using namespace std;
using ll = long long;
inline void Swap(int &a, int &b)
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
return;
}
const int N = 2e5 + 10;
int n;
int a[N];
bool vis[N];
ll ans = -INF;
inline bool check(int a, int b)
{
return a == 65 && b == 66;
}
inline void dfs(ll now)
{
if (now < ans)
{
return;
}
ans = now;
for (re int i = 1; i <= n - 1; i++)
{
if (check(a[i], a[i + 1]) && !vis[i])
{
Swap(a[i], a[i + 1]);
vis[i] = true;
dfs(now + 1);
Swap(a[i], a[i + 1]);
vis[i] = false;
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
ans = -INF;
char ch;
getchar();
for (re int i = 1; i <= n; i++)
{
ch = getchar();
a[i] = ch;
}
dfs(0);
ans = (ans == -INF) ? 0 : ans;
printf("%lld\n", ans);
}
return 0;
}
正确解法
If the string consists of only \(\texttt{A}\) or only \(\texttt{B}\), no operations can be done and hence the answer is \(0\).
Otherwise, let \(x\) be the smallest index where \(s_x=\texttt{A}\) and \(y\) be the largest index where \(s_y=\texttt{B}\)
If \(x>y\), this means that the string is of the form \(s=\texttt{B}\ldots\texttt{BA}\ldots\texttt{A}\) Since all the \(\texttt{B}\) are before the \(\texttt{A}\), no operation can be done and hence the answer is also \(0\).
Now, we are left with the case where \(x<y\). Note that \(s[1,x-1] = \texttt{B}\ldots\texttt{B}\) and \(s[y+1,n] = \texttt{A}\ldots\texttt{A}\) by definition. Since the operation moves \(\texttt{A}\) to the right and \(\texttt{B}\) to the left, this means that \(s[1,x - 1]\) will always consist of all \(\texttt{B}\) and \(s[y + 1, n]\) will always consist of all \(\texttt{A}\). Hence, no operation can be done from index \(1\) to \(x−1\) as well as from index \(y\) to \(n−1\).
The remaining indices where an operation could possibly be done are from \(x\) to \(y−1\). In fact, it can be proven that all \(y−x\) operations can be done if their order is chosen optimally.
Let array \(b\) store the indices of \(s\) between \(x\) and \(y\) that contain \(\texttt{B}\) in increasing order. In other words, \(x < b_1 < b_2 < \ldots < b_k = y\) and \(b_i = \texttt{B}\), where \(k\) is the number of occurences of \(\texttt{B}\) between \(x\) and \(y\). For convenience, we let \(b_0=x\). Then, we do the operations in the following order:
It can be seen that the above ordering does operation on all indices between \(x\) and \(y−1\). To see why all of the operations are valid, we look at each row separately. Each row starts with \(b_i−1\), which is valid as \(s_{b_i} = \texttt{B}\) and \(s_{b_i - 1} = \texttt{A}\) (assuming that it is not the last operation of the row). Then, the following operations in the same row move \(\texttt{A}\) to the left until position \(b_{i - 1}\). To see why the last operation of the row is valid as well, even though \(s_{b_{i - 1}}\) might be equal to \(\texttt{B}\) initially by definition, either \(i=1\) which means that \(s_{b_0} = s_x = \texttt{A}\), or an operation was done on index \(b_{i - 1} - 1\) in the previous row which moved \(\texttt{A}\) to index \(b_{i - 1} - 1\). Hence, all operations are valid.
#include <bits/stdc++.h>
using namespace std;
char s[200005];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc, n; cin >> tc;
while (tc--) {
cin >> n; s[n + 1] = 'C';
for (int i = 1; i <= n; ++i) cin >> s[i];
int pt1 = 1, pt2 = 1, ans = 0;
while (s[pt1] == 'B') ++pt1, ++pt2;
while (pt1 <= n) {
int cntA = 0, cntB = 0;
while (s[pt2] == 'A') ++pt2, ++cntA;
while (s[pt2] == 'B') ++pt2, ++cntB;
if (s[pt2 - 1] == 'B') ans += pt2 - pt1 - 1;
if (cntB) pt1 = pt2 - 1;
else break;
}
cout << ans << '\n';
}
}