P9495 「SFCOI-3」进行一个魔的除 I
EuphoricStar · · 题解
完全不想思考怎么办？
打个表，通过惊人的注意力可以观察出先后手的操作策略。
设
先手的操作策略是：
- 若存在两个相邻
1 ，就选择任意一对相邻1 ； - 否则，若存在
a_i = 1 满足i 的前一个1 或后一个1 的下标奇偶性跟i 相等，就选择i 变成0 ； - 否则任意选择一个
1 变成0 。
后手的操作策略是：
- 对于一个
a_i = 0 ，设[l_1, r_1] 为i 左侧最靠右的极长1 连续段，满足r_1 - l_1 + 1 为奇数，设[l_2, r_2] 为i 右侧最靠左的极长1 连续段，满足r_2 - l_2 + 1 为奇数，若i 和r_1 奇偶性相同且i \le l_2 - 2 ，就称i 是好的； - 优先选择好的位置变成
1 ，若好的位置不足3 个则选完好的位置后任意选一些0 变成1 。
直接模拟可以获得
:::info[代码] 不建议参考。
#include <bits/stdc++.h>
#define int unsigned
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
namespace IO {
const int maxn = 1 << 20;
char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;
inline char gc() {
return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
}
template<typename T = int>
inline T read() {
char c = gc();
T x = 0;
bool f = 0;
while (c < '0' || c > '9') {
f |= (c == '-');
c = gc();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = gc();
}
return f ? ~(x - 1) : x;
}
inline int reads(char *s) {
char c = gc();
int len = 0;
while (isspace(c)) {
c = gc();
}
while (!isspace(c) && c != -1) {
s[len++] = c;
c = gc();
}
return len;
}
inline void flush() {
fwrite(obuf, 1, oS - obuf, stdout);
oS = obuf;
}
struct Flusher {
~Flusher() {
flush();
}
} AutoFlush;
inline void pc(char ch) {
if (oS == obuf + maxn) {
flush();
}
*oS++ = ch;
}
template<typename T>
inline void write(T x) {
static char stk[64], *tp = stk;
if (x < 0) {
x = ~(x - 1);
pc('-');
}
do {
*tp++ = x % 10;
x /= 10;
} while (x);
while (tp != stk) {
pc((*--tp) | 48);
}
}
template<typename T>
inline void writesp(T x) {
write(x);
pc(' ');
}
template<typename T>
inline void writeln(T x) {
write(x);
pc('\n');
}
}
using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;
const int maxn = 1000100;
int n, a[maxn], pre[maxn], nxt[maxn], pr[maxn], nx[maxn], stk[maxn];
int stk1[maxn * 10], stk2[maxn * 10], stk3[maxn * 10], stk4[maxn * 10], top1, top2, top3, top4;
bool vis[maxn];
struct BIT {
int n, c[maxn];
inline void init(int _n) {
n = _n;
for (int i = 0; i <= n; ++i) {
c[i] = 0;
}
}
inline void update(int x, int d) {
for (int i = x; i <= n; i += (i & (-i))) {
c[i] += d;
}
}
inline int query(int x) {
int res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
inline int kth(int k) {
if (!k) {
return 0;
}
int s = 0, p = 0;
(p + 524288 <= n && s + c[p + 524288] < k) ? (s += c[p += 524288]) : 0;
(p + 262144 <= n && s + c[p + 262144] < k) ? (s += c[p += 262144]) : 0;
(p + 131072 <= n && s + c[p + 131072] < k) ? (s += c[p += 131072]) : 0;
(p + 65536 <= n && s + c[p + 65536] < k) ? (s += c[p += 65536]) : 0;
(p + 32768 <= n && s + c[p + 32768] < k) ? (s += c[p += 32768]) : 0;
(p + 16384 <= n && s + c[p + 16384] < k) ? (s += c[p += 16384]) : 0;
(p + 8192 <= n && s + c[p + 8192] < k) ? (s += c[p += 8192]) : 0;
(p + 4096 <= n && s + c[p + 4096] < k) ? (s += c[p += 4096]) : 0;
(p + 2048 <= n && s + c[p + 2048] < k) ? (s += c[p += 2048]) : 0;
(p + 1024 <= n && s + c[p + 1024] < k) ? (s += c[p += 1024]) : 0;
(p + 512 <= n && s + c[p + 512] < k) ? (s += c[p += 512]) : 0;
(p + 256 <= n && s + c[p + 256] < k) ? (s += c[p += 256]) : 0;
(p + 128 <= n && s + c[p + 128] < k) ? (s += c[p += 128]) : 0;
(p + 64 <= n && s + c[p + 64] < k) ? (s += c[p += 64]) : 0;
(p + 32 <= n && s + c[p + 32] < k) ? (s += c[p += 32]) : 0;
(p + 16 <= n && s + c[p + 16] < k) ? (s += c[p += 16]) : 0;
(p + 8 <= n && s + c[p + 8] < k) ? (s += c[p += 8]) : 0;
(p + 4 <= n && s + c[p + 4] < k) ? (s += c[p += 4]) : 0;
(p + 2 <= n && s + c[p + 2] < k) ? (s += c[p += 2]) : 0;
(p + 1 <= n && s + c[p + 1] < k) ? (s += c[p += 1]) : 0;
return p + 1;
}
inline int prev(int x) {
int t = query(x);
return t == 1 ? 0 : kth(t - 1);
}
inline int next(int x) {
int t = query(x);
return kth(t + 1);
}
} T1, T2, T3, T4, T5;
void solve() {
n = read();
for (int i = 0; i <= n + 1; ++i) {
pre[i] = nxt[i] = pr[i] = nx[i] = 0;
vis[i] = 0;
}
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
a[0] = a[n + 1] = 0;
top1 = top2 = top3 = top4 = 0;
T1.init(n);
T2.init(n);
T3.init(n + 1);
T4.init(n);
T5.init(n);
int lst = 0, cnt = 0, lst2 = 0, lst3 = 0;
nx[0] = n + 1;
for (int i = 1; i <= n; ++i) {
if (a[i]) {
++cnt;
T1.update(i, 1);
pre[i] = lst;
nxt[i] = n + 1;
if (lst) {
nxt[lst] = i;
if (i - lst == 1) {
stk1[++top1] = lst;
}
if ((i - lst) % 2 == 0) {
stk2[++top2] = lst;
}
}
lst = i;
} else {
T2.update(i, 1);
if (i & 1) {
T4.update(i, 1);
} else {
T5.update(i, 1);
}
stk4[++top4] = i;
pre[i] = lst2;
nxt[i] = n + 1;
if (lst2) {
nxt[lst2] = i;
}
if ((i - lst2) % 2 == 0) {
T3.update(i, 1);
pr[i] = lst3;
nx[i] = n + 1;
nx[lst3] = i;
stk3[++top3] = lst3;
vis[lst3] = 1;
lst3 = i;
}
lst2 = i;
}
}
T3.update(n + 1, 1);
pr[n + 1] = lst3;
nx[n + 1] = n + 2;
nx[lst3] = n + 1;
stk3[++top3] = lst3;
vis[lst3] = 1;
auto add = [&](int i) -> void {
if (i == n + 1) {
int j = pr[i];
if (!vis[j]) {
stk3[++top3] = j;
vis[j] = 1;
}
return;
}
T3.update(i, 1);
int t = T3.query(i);
int j = T3.kth(t - 1), k = T3.kth(t + 1);
pr[i] = j;
nx[i] = k;
nx[j] = i;
if (!vis[j]) {
stk3[++top3] = j;
vis[j] = 1;
}
if (!vis[i]) {
stk3[++top3] = i;
vis[i] = 1;
}
pr[k] = i;
};
auto del = [&](int i) -> void {
if (i == n + 1) {
int j = pr[i];
if (!vis[j]) {
stk3[++top3] = j;
vis[j] = 1;
}
return;
}
T3.update(i, -1);
int j = pr[i], k = nx[i];
nx[j] = k;
if (!vis[j]) {
stk3[++top3] = j;
vis[j] = 1;
}
pr[k] = j;
pr[i] = nx[i] = 0;
};
auto set0 = [&](int i) -> void {
if (!a[i]) {
return;
}
--cnt;
a[i] = 0;
stk4[++top4] = i;
int j = pre[i], k = nxt[i];
T1.update(i, -1);
if (i & 1) {
T4.update(i, 1);
} else {
T5.update(i, 1);
}
if (j) {
nxt[j] = k;
}
if (k <= n) {
pre[k] = j;
}
if (j && k <= n) {
if (k - j == 1) {
stk1[++top1] = j;
}
if ((k - j) % 2 == 0) {
stk2[++top2] = j;
}
}
T2.update(i, 1);
int t = T2.query(i);
j = k = -1;
for (int p = i - 1; p >= 0 && p >= i - 3; --p) {
if (!a[p]) {
j = p;
break;
}
}
if ((signed)j == -1) {
j = T2.kth(t - 1);
}
for (int p = i + 1; p <= n + 1 && p <= i + 3; ++p) {
if (!a[p]) {
k = p;
break;
}
}
if ((signed)k == -1) {
k = T2.kth(t + 1);
}
pre[i] = j;
nxt[i] = k;
nxt[j] = i;
pre[k] = i;
int d = 0;
if ((k - j) % 2 == 0) {
--d;
}
if ((k - i) % 2 == 0) {
++d;
}
if (d == 1) {
add(k);
} else if ((signed)d == -1) {
del(k);
}
if ((i - j) % 2 == 0) {
add(i);
}
};
auto set1 = [&](int i) -> void {
if (a[i]) {
return;
}
++cnt;
a[i] = 1;
T1.update(i, 1);
T2.update(i, -1);
if (i & 1) {
T4.update(i, -1);
} else {
T5.update(i, -1);
}
int j = pre[i], k = nxt[i];
nxt[j] = k;
if ((i - j) % 2 == 0) {
del(i);
}
pre[k] = j;
int d = 0;
if ((k - i) % 2 == 0) {
--d;
}
if ((k - j) % 2 == 0) {
++d;
}
if (d == 1) {
add(k);
} else if ((signed)d == -1) {
del(k);
}
int t = T1.query(i);
j = k = -1;
for (int p = i - 1; p >= 0 && p >= i - 3; --p) {
if (a[p]) {
j = p;
break;
}
}
if ((signed)j == -1) {
j = T1.kth(t - 1);
}
for (int p = i + 1; p <= n + 1 && p <= i + 3; ++p) {
if (a[p]) {
k = p;
break;
}
}
if ((signed)k == -1) {
k = T1.kth(t + 1);
}
pre[i] = j;
nxt[i] = k;
if (j) {
nxt[j] = i;
if (i - j == 1) {
stk1[++top1] = j;
}
if ((i - j) % 2 == 0) {
stk2[++top2] = j;
}
}
if (k <= n) {
pre[k] = i;
if (k - i == 1) {
stk1[++top1] = i;
}
if ((k - i) % 2 == 0) {
stk2[++top2] = i;
}
}
};
int ans = 0, o = 1;
while (1) {
if (cnt == n) {
writeln(ans);
return;
}
if (o) {
if (!cnt) {
o ^= 1;
continue;
}
while (top1) {
int i = stk1[top1];
if (a[i] && a[i + 1]) {
break;
} else {
--top1;
}
}
if (top1) {
int p = stk1[top1];
set0(p);
set0(p + 1);
} else {
int x = T1.kth(1);
if (x & 1) {
set0(x);
} else {
x = T1.kth(cnt);
if ((n - x) % 2 == 0) {
set0(x);
} else {
while (top2) {
int i = stk2[top2];
if (a[i] && (nxt[i] - i) % 2 == 0) {
break;
} else {
--top2;
}
}
if (top2) {
x = stk2[top2];
}
set0(x);
}
}
}
} else {
++ans;
int k = 0;
while (top3 && k < 3) {
int i = stk3[top3--];
vis[i] = 0;
if (i == n + 1) {
continue;
}
if (!a[i] && nx[i]) {
int j = pre[nx[i]];
if (nx[i] >= n + 1) {
j = n + 1;
}
if (i >= j) {
continue;
}
if ((i + 1) & 1) {
int p = T4.query(i) + 1, q = T4.query(j - 1);
while (k < 3 && p <= q) {
int t = T4.kth(p);
if ((nxt[t] - t) % 2 == 0) {
break;
}
stk[++k] = t;
++p;
}
} else {
int p = T5.query(i) + 1, q = T5.query(j - 1);
while (k < 3 && p <= q) {
int t = T5.kth(p);
if ((nxt[t] - t) % 2 == 0) {
break;
}
stk[++k] = t;
++p;
}
}
}
}
for (int i = 1; i <= k; ++i) {
set1(stk[i]);
}
while (top4 && k < 3) {
int i = stk4[top4--];
if (!a[i]) {
set1(i);
++k;
}
}
}
o ^= 1;
}
}
signed main() {
int T = read();
while (T--) {
solve();
}
return 0;
}
:::
这个做法注意力要求极高，代码实现和调试极其困难，在考场上不可能用这个做法通过，所以大家当看个乐子就行。