【比赛】ARC136｜220227
time: 2022-02-27 22:08:13
tags:
- 比赛 比赛/ARC
A - A ? BB
考虑一些贪心的事实：
- 如果有连着的
BB，换成A显然更优 - 如果有连着的
BA，可以换成AB更优 - 如果连着的是其他字符，不管最优
#include
using namespace std;
int n;
deque s;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
char c;
for(int i = 1; i <= n; i++) {
cin >> c;
s.push_back(c);
}
while(!s.empty()) {
if(s.size() > 1) {
char p = *s.begin(), q = *(next(s.begin()));
if(p == 'B' && q == 'A') {
s.pop_front(), s.pop_front();
s.push_front('B'), s.push_front('A');
} else if(p == 'B' && q == 'B') {
s.pop_front(), s.pop_front();
s.push_front('A');
}
}
cout << s.front();
s.pop_front();
}
return 0;
}
B - Triple Shift
Des
给定长度为 \(n\) 的数组 \(A\) 和 \(B\)，每次可以选定 \(A\) 中连续的三个数，然后把三个数 \((x,y,z)\) 换为 \((z,x,y)\)。问能不能经过若干次操作把 \(A\) 成 \(B\).
Sol
怎么又是这种交换 + 逆序对题，USACO 铜组才考。
发现是把一个数隔着前面的一个数往前调（三元组前调？），调换之后一定不会改变逆序对的奇偶性。所以直接统计逆序对个数，奇数就不行，偶数就行。
但是你会发现有相等的元素。如果越过了一个相等的元素，那么逆序对个数的奇偶性可能会改变？考虑给相等的元素强行定一个排名，然后如果逆序对个数是奇数的话，就交换两个相等的元素，逆序对个数就会变成偶数。所以只要存在相等的元素就一定有解。
My Code
#include
using namespace std;
const int N = 5005;
int n, p[N], oa[N];
struct wtf {
int v, id;
} a[N], b[N];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i].v, a[i].id = i, oa[i] = a[i].v;
for(int i = 1; i <= n; i++) cin >> b[i].v, b[i].id = i;
auto cmp = [&](wtf x, wtf y) {
return x.v < y.v;
};
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
for(int i = 1; i <= n; i++) {
if(a[i].v != b[i].v) {
cout << "No\n";
return 0;
}
}
for(int i = 1; i <= n; i++)
p[a[i].id] = b[i].id;
int tot = 0;
for(int i = 1; i <= n; i++) {
debug(i, p[i]);
for(int j = i + 1; j <= n; j++) {
if(oa[i] == oa[j]) {
cout << "Yes\n";
return 0;
}
if(p[i] > p[j]) ++tot;
}
}
if(tot & 1) cout << "No\n";
else cout << "Yes\n";
return 0;
}
C - Circular Addition
Des
环上排着 \(n\) 个数 \(a_i\)，每次可以选择任意一个区间，把区间内的数都减一。问把所有数都减成 \(0\) 需要的最小操作次数。
\(n\le 2\times 10^5\)
Sol
考场上想了个把积木大赛 套进去的假做法，亏惨了。
正解比较妙，不如考场多弄几个样例猜结论。
考虑差分数组 \(b_i=a_i-a_{(i-1+n)\bmod\ n}\)（\(a\) 数组下标从 0 开始），然后设 \(M=\max a_i\)，\(D=\sum b_i[b_i>0]\) 那么答案等于 \(\max(M,D)\)。
首先答案至少需要这个数量的操作，因为每次最多把最大值减少一，\(\sum b_i\) 减少二，而 \(\sum b_i[b_i>0]=\frac {\sum b_i}{2}\).
然后证可以在这个数量内操作完毕。
首先考虑 \(M>D\) 的情况，可以证明的是这种情况下不存在 \(a_i=0\)，因为考虑到 \(0,\dots,M,\dots,0\) 的这个环会使得 \(M\le D\)，矛盾了。于是就可以不断给所有数减一直到 \(M=D\).
然后考虑 \(M
最后考虑 \(M= D\) 的情况。如果只有一个 \(M\)，选择最大的包含 \(M\) 的区间减一就能让 \(M,D\) 同时减一。如果有多个 \(M\)，则一定不存在 \(a_i=0\) 的情况（考虑 \(0,\dots,M\dots,0\) 仍然可以得证）。所以可以选择一个最大的包含所有 \(M\) 的区间减一，也能让 \(M,D\) 同时减一。
这样就完成证明了，时间复杂度 \(O(n)\).
My Code
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
ll ans;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
ll M = 0, D = 0;
vector a;
for(int i = 1, t; i <= n; i++) {
cin >> t;
a.emplace_back(t);
M = max(M, (ll)t);
}
for(int i = 0; i < (int)a.size(); i++)
D += abs(a[i] - a[(i - 1 + n) % n]);
D /= 2;
cout << max(M, D) << '\n';
return 0;
}
D - Without Carry
Des
给定 \(n\le 10^6\) 个数，求使得 \(a_i+a_j\) 做竖式加法不进位，且 \(i
Sol
考场上觉得比 C 题简单但是不会做，以为是容斥结果不行。然后想到可能是一个多维的前缀和，但是不会构建，卒。
可以看一下 CF 讨论里某好心人教的高维前缀和构建方法 。我就不写了。
设 \(L=\log_{10}V\)，复杂度是 \(O(nL+L\cdot 10^L)\)。
#include
using namespace std;
#define rep(i, j, k) for(int i = j; i <= k; i++)
const int N = 1e6 + 5;
int n, a[N], p[10];
int s[11][11][11][11][11][11];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
for(int x = a[i], j = 1; j <= 6; j++, x /= 10) p[j] = x % 10 + 1;
++s[p[1]][p[2]][p[3]][p[4]][p[5]][p[6]];
}
rep(w, 1, 6)
rep(i1, 1, 10)
rep(i2, 1, 10)
rep(i3, 1, 10)
rep(i4, 1, 10)
rep(i5, 1, 10)
rep(i6, 1, 10)
s[i1][i2][i3][i4][i5][i6] += s[i1 - (w == 1)][i2 - (w == 2)][i3 - (w == 3)][i4 - (w == 4)][i5 - (w == 5)][i6 - (w == 6)];
long long ans = 0;
for(int i = 1; i <= n; i++) {
bool flag = true;
for(int x = a[i], j = 1; j <= 6; j++, x /= 10) p[j] = x % 10, flag &= (p[j] < 5);
ans += s[10 - p[1]][10 - p[2]][10 - p[3]][10 - p[4]][10 - p[5]][10 - p[6]];
ans -= flag;
}
ans /= 2;
cout << ans << '\n';
return 0;
}