专栏文章

P9495 「SFCOI-3」进行一个魔的除 I

EEuphoricStar
P9495题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjxgv9
此快照首次捕获于
2025/12/02 03:38
3 个月前
此快照最后确认于
2025/12/02 03:38
3 个月前
查看原文
完全不想思考怎么办？
打个表，通过惊人的注意力可以观察出先后手的操作策略。
设 a−1=an+2=1a_{-1} = a_{n + 2} = 1，a0=an+1=0a_0 = a_{n + 1} = 0。
先手的操作策略是：
  • 若存在两个相邻 11，就选择任意一对相邻 11；
  • 否则，若存在 ai=1a_i = 1 满足 ii 的前一个 11 或后一个 11 的下标奇偶性跟 ii 相等，就选择 ii 变成 00；
  • 否则任意选择一个 11 变成 00。
后手的操作策略是：
  • 对于一个 ai=0a_i = 0，设 [l1,r1][l_1, r_1] 为 ii 左侧最靠右的极长 11 连续段，满足 r1−l1+1r_1 - l_1 + 1 为奇数，设 [l2,r2][l_2, r_2] 为 ii 右侧最靠左的极长 11 连续段，满足 r2−l2+1r_2 - l_2 + 1 为奇数，若 ii 和 r1r_1 奇偶性相同且 i≤l2−2i \le l_2 - 2，就称 ii 是好的；
  • 优先选择好的位置变成 11，若好的位置不足 33 个则选完好的位置后任意选一些 00 变成 11。
直接模拟可以获得 O(n2)O(n^2) 的做法。树状数组维护一些东西的前驱后继加速模拟，时间复杂度 O(nlog⁡n)O(n \log n)，需要卡常。
代码
不建议参考。
CPP
#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;
}
这个做法注意力要求极高，代码实现和调试极其困难，在考场上不可能用这个做法通过，所以大家当看个乐子就行。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...