专栏文章

题解：P11754 [COCI 2024/2025 #5] 绘图 / Crtež

__ayaka_
P11754题解参与者 7已保存评论 7

文章操作

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

当前评论
7 条
当前快照
1 份
快照标识符
@miptajnd
此快照首次捕获于
2025/12/03 17:35
3 个月前
此快照最后确认于
2025/12/03 17:35
3 个月前
查看原文

思路

我在做完这道题后想出了一个更好理解的推结论过程，所以这里附出更简单的版本。至于更丑陋的考场版本有兴趣可以看看。
答案显然是每一段连续的 00 的情况相乘后的答案，因此先只考虑连续的 00。因为显然对一个位置进行操作 22 后，直到其左边第一个非 00 数，之间的所有数全部会被染成一种颜色，不好讨论，考虑从左到右来进行操作。
随后，不难发现，对于一个已经被选择为 00 的点，即使这个点被后面的一次操作 22 染上色了，这也仍然只是一种情况，可推出对于每一个点，有进行操作 11，进行操作 22，以及不操作三种情况，可得如果有 nn 个连续的 00，总情况为 3n3^n。
然后我们的问题就变成了如何求出每次询问里序列 aa 中 00 的数量。不难想到离散化后使用线段树维护即可，因为不是此题重点就不细说了。
时间复杂度 O(qlog⁡n)O(q\log n)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll (k<<1)
#define rr (k<<1|1)
#define mid ((l+r)>>1)
const int mod = 1e9 + 7;
int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
struct que {
	int l, r;
} p[1000005];
map <int, int> mp;
int num[1000005], cnt, ls[1000005], un;
struct tree {
	int l, r, lazy, num, sum;
} t[4000005];
int n, q;
inline void pushup(int k) {
	t[k].num = t[ll].num + t[rr].num;
}
void build(int k, int l, int r) {
	t[k].l = l;
	t[k].r = r;
	if (l == r) {
		t[k].num = num[l];
		t[k].sum = num[l];
		return ;
	}
	build(ll, l, mid);
	build(rr, mid + 1, r);
	pushup(k);
	t[k].sum = t[ll].sum + t[rr].sum;
	return ;
}
inline void pushdown(int k) {
	if (t[k].lazy) {
		t[ll].lazy ^= 1;
		t[rr].lazy ^= 1;
		t[ll].num = t[ll].sum - t[ll].num;
		t[rr].num = t[rr].sum - t[rr].num;
		t[k].lazy = 0;
	}
}
void update(int k, int l, int r) {
	if (t[k].r < l || t[k].l > r) return ;
	if (t[k].r <= r && t[k].l >= l) {
		t[k].lazy ^= 1;
		t[k].num = t[k].sum - t[k].num;
		return ;
	}
	pushdown(k);
	update(ll, l, r);
	update(rr, l, r);
	pushup(k);
	return ;
}
signed main() {
	cin >> n >> q;
	for (int i = 1; i <= q; i++) {
		cin >> p[i].l >> p[i].r;
		ls[i * 2 - 1] = p[i].l, ls[i * 2] = p[i].r;
	}
	sort(ls + 1, ls + q * 2 + 1);
	un = unique(ls + 1, ls + q * 2 + 1) - ls - 1;
	for (int i = 1; i <= un; i++) {
		num[i * 2 - 1] = ls[i] - ls[i - 1] - 1;
		num[i * 2] = 1;
		mp[ls[i]] = i * 2;
	}
	num[un * 2 + 1] = n - ls[un];//num 数组保存的是这一个新点存储了几个点 
	build(1, 1, un * 2 + 1); 
	for (int i = 1; i <= q; i++) {
		p[i].l = mp[p[i].l];
		p[i].r = mp[p[i].r];
		update(1, p[i].l, p[i].r);
		cout << qpow(3, t[1].num) % mod << "\n";
	}
	return 0;
//}

关于更多

这里附考场思路：
首先只考虑对一段连续的 00 做操作 22 的情况。操作 22 也就是把从一个点到其左边第一个非 00 数前的所有数染上同一个颜色。接下来，我们对于每个数就有了“染了色”和“未染色”两种情况。根据题面给出的“等价”的概念，我们不用在意这个染色具体是哪种颜色，只需要知道这一段的颜色与其他所有颜色都不同就好了。
接下来对这个情况进行简单的讨论：
  • 当有 11 个 00 时，显然对于第 11 个数有两种选择：染色或不染。
  • 当有 22 个 00 时，对于第 22 个数，前一个数未被染色的情况有 11 个，此时这一个数也只能不染色，因为按照操作 22 的定义，不可能存在两段染了色的段中间有一段未染色的情况。因此前一个数未染色而这一个数未染色的情况有一种；而前一个数被染色的情况有 11 种，那这个点有三种选择：染前一个点的颜色，染新的颜色，不染。最后总情况为 44 种，这个点未被染色的有 22 种，被染色的有 22 种。
  • 当有 33 个 00 时，根据上一种情况可得前一个数未染色可推出的情况有 1×2=21\times 2=2 种，而前一个数被染色的情况有 3×2=63\times 2=6 种，总情况有 88 种，这个点未被染色的有 44 种，被染色的有 44 种。
接着根据这个规律，显然可得有 nn 个 00 时，总情况有 2n2^n 种。
接下来，我们加入第 11 种操作。可以将第 11 种操作看作是把一段连续的 00 拆成几个部分，显然若添加了 xx 个 −1-1，则总情况为 2n−x2^{n-x} 种。可得总情况为：
∑i=0n(ni)×2i\sum^n_{i=0} \binom{n}{i}\times 2^i
根据牛顿二项式定理（或者打一点表出来看）可得此式为 3n3^n。随后可得结论。

评论

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

正在加载评论...