题解：P13274 [NOI2025] 三目运算符

场外奶龙想了 1h 写了 40min（应该不止），给我糖丸了兄弟。

首先发现

s_i

只和

s_{i - 1}, s_{i - 2}

有关，于是考虑

n = 3

，发现 110,101 时最后一位会改变。考虑更大的情况，110 的 border 为零看上去似乎互相影响没有那么大，考虑 101 的重复出现，比如 1010101010101，这样第一次就会全部变成 1000000000000，很好处理。

考虑 110，这似乎有点难，比如 110 后面跟着很多个 0，那么最后把它变好需要操作 0 的数目次，再比如 11010101，最后操作也是不断把第一个 0 变成 1。通过不断地手玩，打个暴力，我们发现一个惊天大秘密，最后它会变成全部是 1 的状态，而且似乎第一个 0 会每次不断向右移动一个，直到出去。于是我们大胆猜测，长度为

n

形如 110...... 串的答案其实就是

(n - 2)

。这很好证明。

考虑归纳法，对于

n = 3

，显然操作一次即可，对于

n > 3

，我们只考虑

(n - 1)

次操作那么就会出现

(n - 1)

个 1 最后跟着一个 0。如果

(n+1)

是 1，那么这个 1 会变成一个 0，第

n

个数会变成 1，最后三个仍然是 110。如果第

(n+1)

是 0 那么最后三个就显然是 110。

如果在这个 110 前面增加一段前缀使得它改变了呢？其实不会的，因为开头的 1 变了并不影响这一段第

n

次操作后会最后出现一个 110，中间的 1 则显然不可能改变。

然后你发现这道题找到出现最早的 110 位置和有没有出现过 101 就做完了。线段树即可。

CPP

#include <bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N = 4e5, inf = 8e5;
il int ls(int x) {
	return 2 * x;
}
il int rs(int x) {
	return 2 * x + 1;
}
int p101[N * 4 + 10], p010[N * 4 + 10], p110[N * 4 + 10], p001[N * 4 + 10];//最早出现位置
int pre[N * 4 + 10], suf[N * 4 + 10];//这个节点最开始两个和最后两个（可能只有 1 个要特判）
int tag[N * 4 + 10];

il bool check1(int x, int y, int z) {
	return ((x % 2) * 4 + y == z);
}
il bool check2(int x, int y, int z) {
	return (x * 2 + y / 2 == z);
}
il void push_up(int now, int s, int t) {
	int mid = (s + t) >> 1;
	if(t - s + 1 == 2)
		pre[now] = suf[now] = pre[ls(now)] * 2 + pre[rs(now)];
	else if(t - s + 1 == 3)
		pre[now] = pre[ls(now)], suf[now] = (pre[ls(now)] % 2) * 2 + suf[rs(now)];
	else pre[now] = pre[ls(now)], suf[now] = suf[rs(now)];

	p110[now] = min(p110[ls(now)], p110[rs(now)]);
	p101[now] = min(p101[ls(now)], p101[rs(now)]);
	p001[now] = min(p001[ls(now)], p001[rs(now)]);
	p010[now] = min(p010[ls(now)], p010[rs(now)]);
	if(t - s + 1 >= 4) {
		if(check1(suf[ls(now)], pre[rs(now)], 6)) p110[now] = min(p110[now], mid);
		if(check2(suf[ls(now)], pre[rs(now)], 6)) p110[now] = min(p110[now], mid - 1);
		if(check1(suf[ls(now)], pre[rs(now)], 5)) p101[now] = min(p101[now], mid);
		if(check2(suf[ls(now)], pre[rs(now)], 5)) p101[now] = min(p101[now], mid - 1);
		if(check1(suf[ls(now)], pre[rs(now)], 1)) p001[now] = min(p001[now], mid);
		if(check2(suf[ls(now)], pre[rs(now)], 1)) p001[now] = min(p001[now], mid - 1);
		if(check1(suf[ls(now)], pre[rs(now)], 2)) p010[now] = min(p010[now], mid);
		if(check2(suf[ls(now)], pre[rs(now)], 2)) p010[now] = min(p010[now], mid - 1);
	}
	else if(t - s + 1 == 3) {
		int r = pre[ls(now)] * 2 + suf[rs(now)];
		if(r == 6) p110[now] = min(p110[now], mid - 1);
		if(r == 5) p101[now] = min(p101[now], mid - 1);
		if(r == 1) p001[now] = min(p001[now], mid - 1);
		if(r == 2) p010[now] = min(p010[now], mid - 1);
	}
}
il void push_tag(int now, int s, int t) {
	if(t - s + 1 == 1) pre[now] = 1 - pre[now], suf[now] = 1 - suf[now];
	else pre[now] = 3 - pre[now], suf[now] = 3 - suf[now];

	tag[now] ^= 1;
	swap(p101[now], p010[now]);
	swap(p001[now], p110[now]);
} 
il void push_down(int now, int s, int t) {
	if(tag[now]) {
		int mid = (s + t) >> 1;
		push_tag(ls(now), s, mid);
		push_tag(rs(now), mid + 1, t);
		tag[now] = 0;
	}
}

int a[N + 10], n, m;
void build(int l, int r, int now) {
	tag[now] = 0;
	p101[now] = p110[now] = p010[now] = p001[now] = inf;
	pre[now] = suf[now] = 0;
	if(l == r) {
		pre[now] = suf[now] = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(l, mid, ls(now));
	build(mid + 1, r, rs(now));
	push_up(now, l, r);
}
void upd(int ql, int qr, int s, int t, int now) {
	if(ql <= s && t <= qr) {
		push_tag(now, s, t);
		return ;
	}
	int mid = (s + t) >> 1;
	push_down(now, s, t);
	if(ql <= mid) upd(ql, qr, s, mid, ls(now));
	if(qr > mid) upd(ql, qr, mid + 1, t, rs(now));
	push_up(now, s, t);
}
il int qry() {
	int ans = 0;
	if(p101[1] != inf) ans = 1;
	ans = max(ans, n - p110[1] - 1);
	return ans;
}

void init() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		char ch; cin >> ch;
		a[i] = ch - '0';
	}
	build(1, n, 1);

	ll ans = 0;
	ans ^= qry();
	for(int i = 1, l, r; i <= m; i++) {
		cin >> l >> r;
		upd(l, r, 1, n, 1);
		ans ^= (1ll * (i + 1) * 1ll * qry());
	}
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int c, T; cin >> c >> T;
	while(T--) init();
}

题解：P13274 [NOI2025] 三目运算符

文章操作

相关推荐

评论

题解：P13274 [NOI2025] 三目运算符