打的稀烂，但是还是上分了（
A
考虑对值域做一个后缀和。若某一个后缀和的值是奇数那么先手就可以获胜。否则就不可以获胜。
（我才不会告诉你我这题吃了一次罚时的）
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mysqrt(int x) {
int l = 0, r = x + 10, best = -1;
while (l <= r) {
int mid = l + r >> 1;
if ((__int128)(mid) * (__int128)(mid) <= x)
best = mid, l = mid + 1;
else
r = mid - 1;
}
return best;
}
const int N = 500100;
int n;
int a[N], box[N];
signed main() {
int T;
cin >> T;
while (T--) {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]), box[i] = 0;
for (int i = 1 ;i <= n; ++i)
++box[a[i]];
if (box[n] & 1) {
puts("YES");
continue;
}
for (int i = n - 1; i; --i) {
box[i] += box[i - 1];
if (box[i] & 1) {
puts("YES");
goto ee;
}
}
puts("NO");
ee:;
}
return 0;
}
B
构造。因为 \(a_i\in\lbrace-1,1\rbrace\)，所以可以考虑简单一些的构造：
- 对于 \(i\in [1,y)\)，考虑从后往前交替构造 \(-1,1\)，这样可以满足比 \(y\) 要小的位置的后缀和不会大于 \(y\) 位置的后缀和。
- 对于 \(i\in [y,x]\)， 考虑全部构造 \(1\)。
- 对于 \(i\in (x,n]\)，考虑正着构造 \(1,-1\)，这样可以满足比 \(x\) 要大的位置的前缀和不会大于 \(x\) 位置的前缀和。
证明显然。时间复杂度为 \(O(n)\)。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mysqrt(int x) {
int l = 0, r = x + 10, best = -1;
while (l <= r) {
int mid = l + r >> 1;
if ((__int128)(mid) * (__int128)(mid) <= x)
best = mid, l = mid + 1;
else
r = mid - 1;
}
return best;
}
const int N = 500100;
int n;
int a[N], box[N];
signed main() {
int T;
cin >> T;
while (T--) {
int n, x, y;
scanf("%lld%lld%lld", &n, &x, &y);
int idx = 0;
for (int i = y - 1; i; --i) {
++idx;
if (idx & 1) a[i] = -1;
else a[i] = 1;
}
for (int i = y; i <= x; ++i) {
a[i] = 1;
}
idx = 0;
for (int i = x + 1; i <= n; ++i) {
++idx;
if (idx & 1) a[i] = -1;
else a[i] = 1;
}
for (int i = 1; i <= n; ++i)
printf("%lld ", a[i]);
puts("");
}
return 0;
}
C
奇怪的结论。容易发现执行 \(\text{MAD}\) 函数至少一次之后函数的值一定单调不减，然后可以发现，如果每一个数的出现次数不为 \(1\)，那么可以一遍前缀和快速的算出答案（此时 \(b\) 数组的变化是每一次从后面删除一个字符）。
问题在于如何让 \(b\) 数组每一个数的出现次数都不为 \(1\)。手玩小样例之后发现在经过不超过 \(20\) 次操作之后一定可以满足这个条件。所以暴力迭代即可。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mysqrt(int x) {
int l = 0, r = x + 10, best = -1;
while (l <= r) {
int mid = l + r >> 1;
if ((__int128)(mid) * (__int128)(mid) <= x)
best = mid, l = mid + 1;
else
r = mid - 1;
}
return best;
}
const int N = 500100;
int n;
int a[N], box[N], b[N], s[N];
signed main() {
int T;
cin >> T;
while (T--) {
int n;
scanf("%lld", &n);
int now = 0, sum = 0;
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]), box[i] = 0, sum += a[i];
for (int _ = 0; _ < 20; ++_) {
for (int i = 1; i <= n; ++i)
box[i] = 0;
now = 0;
for (int i = 1; i <= n; ++i) {
++box[a[i]];
if (box[a[i]] >= 2 && now < a[i])
now = a[i];
b[i] = now;
}
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + b[i], a[i] = b[i];
// cout << _ << ": ";
// for (int i = 1; i <= n; ++i)
// cout << b[i] << ' '; cout << '\n';
sum += s[n];
}
int p = 1, rig = n;
while (p <= rig) {
set<int> se;
se.insert(b[p]);
while (p < rig && (!se.count(b[p + 1]) || b[p] == 0))
++p, se.insert(b[p]);
--rig;
// cout << "qwq " << p << ' ' << rig << ' ' << sum << '\n';
sum += s[rig] - s[p - 1];
}
printf("%lld\n", sum);
}
return 0;
}
D
分类讨论。
容易发现 \(a_i=0\) 的地方已经全部染成白色，也就是将需要染色的区间一分为二。\(a_i>4\) 的区间直接染一行一定比染 \(2\times 2\) 方格要优秀。\(n=1\) 则分类讨论 \(a_1\) 的值为 \(1\) 还是 \(0\) 即可。问题在于 \(a_i\in\lbrace1,2,3,4\rbrace\) 的情况。
容易发现如果对于一段极大的区间 \([l,r]\)，则若 \(\max\limits_{i=l}^r a_i\le 2\)，则此时只需要染 \(\lceil\frac{r-l+1}{2}\rceil\) 次 \(2\times 2\) 就可以满足条件。然后如果出现类似于样例第二个点（中间 \(3\)，\(4\)，边上 \(1\)，\(2\)，长度为偶数）的情况，此时只需要染 \(r-l\) 次色即可。
然后随便 dp 一下，设 \(f_i\) 表示染色前 \(i\) 行最少需要染色几次。然后直接根据分类讨论的情况 dp 即可。时间复杂度为 \(O(n\log n)\)（ST 表）或者 \(O(n\log^2n)\)（线段树）。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mysqrt(int x) {
int l = 0, r = x + 10, best = -1;
while (l <= r) {
int mid = l + r >> 1;
if ((__int128)(mid) * (__int128)(mid) <= x)
best = mid, l = mid + 1;
else
r = mid - 1;
}
return best;
}
const int N = 500100;
int n, f[N][20], g[N][20], a[N], F[N];
int askmin(int l, int r) {
int p = __lg(r - l + 1);
return min(f[l][p], f[r - (1ll << p) + 1][p]);
}
int askmax(int l, int r) {
int p = __lg(r - l + 1);
return max(g[l][p], g[r - (1ll << p) + 1][p]);
}
signed main() {
int T;
cin >> T;
while (T--) {
int n;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]), f[i][0] = g[i][0] = a[i];
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= n - (1ll << i) + 1; ++j) {
f[j][i] = min(f[j][i - 1], f[j + (1ll << (i - 1))][i - 1]);
g[j][i] = max(g[j][i - 1], g[j + (1ll << (i - 1))][i - 1]);
}
F[0] = 0;
for (int i = 1; i <= n; i++) {
if (a[i]) {
F[i] = F[i - 1] + 1;
if (a[i] <= 2) {
int l = 1, r = i - 1, best = -1;
while (l <= r) {
int mid = l + r >> 1;
if (askmin(mid, i - 1) <= 2)
l = mid + 1, best = mid;
else
r = mid - 1;
}
if (best != -1 && askmax(best, i) <= 4 && ~(i - best + 1) & 1)
F[i] = min(F[i], F[best - 1] + (i - best + 1) - 1);
}
} else F[i] = F[i - 1];
}
printf("%lld\n", F[n]);
}
return 0;
}