专栏文章

CF2089B2 Canteen (Hard Version) 题解

SStayAlone9.29Hz
CF2089B2题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mipp9ala
此快照首次捕获于
2025/12/03 15:42
3 个月前
此快照最后确认于
2025/12/03 15:42
3 个月前
查看原文
嗯？这不是模拟题吗？
一个纯模拟做法，无法从 Easy Version 导出。
时间复杂度 O(n2w)\mathcal O(\frac{n^2}{w})，但是跑得很快！
当一个 aia_i 变成 00 之后，称之为无效；当一个 bib_i 变成 00 之后，称之为无效。可以发现，每一次操作只有 ai,bia_i,b_i 均有效才有意义，每一次有意义的操作之后，要么 aia_i 变得无效，要么 bib_i 变得无效。
最初共 2n2n 个有效元素，每次有效操作减少一个有效元素，只要能找到每一轮的有效操作，时间复杂度就是对的。
考虑用两个 bitset 分别维护 aia_i 和 bib_i 的有效状态，每一轮对 aia_i 的 bitset 右移，再将两个 bitset 按位与，就找到了有效操作的位置！
通过模拟，可以得知每一轮 aia_i 的减少量，那么原问题就迎刃而解了。
这里手写 bitset，减少每个有效操作的代价是 O(w)\mathcal O(w)，因为要枚举其所在的 unsigned long long。总时间复杂度 O(n2w+wn)\mathcal O(\frac{n^2}{w}+wn)，ww 取 n\sqrt n 最优，在线求一个 n\sqrt n 位机。
由于一些原因，这里 w=64w=64。
CPP
int n, a[MAXN], b[MAXN], tim, mx;
ull W, k, S, Sn;
 
struct {
	ull val[3200];
	
	il int query(int i) {
		return val[i >> 6] >> (i & 63) & 1;
	}
	
	il void change(int i) {
		val[i >> 6] ^= 1ull << (i & 63);
	}
	
	il void right() {
		int p = query(n - 1);
		rep2(i, mx, 1) {
			val[i] <<= 1;
			val[i] |= val[i - 1] >> 63;
		} val[0] <<= 1; val[0] |= p;
	}
	
	il void init() {
		rep1(i, 0, mx) val[i] = -1;
	}
} bal, cas;
 
il void find() {
	rep1(i, 0, mx) if (W = (bal.val[i] & cas.val[i])) {
		int pre = i << 6;
		rep1(j, 0, 63) if (W >> j & 1) {
			int x = pre + j, y = x < tim ? x - tim + n : x - tim, t = min(b[x], a[y]);
			if (x >= n) break;
			Sn += t;
			if (!(a[y] -= t)) bal.change(x);
			if (!(b[x] -= t)) cas.change(x);
		}
	}
}
 
il void solve() {
	read(n, k); mx = n - 1 >> 6; bal.init(); cas.init(); tim = S = Sn = 0;
	rer(i, 0, n - 1, a), S += a[i]; rer(i, 0, n - 1, b);
	if (k >= S) return puts("0"), void();
	while (true) {
		find(), ++tim;
		if (Sn + k >= S) return printf("%d\n", tim), void();
		bal.right();
	}
}
 
int main() {
	for (int T = read(); T--; ) solve();
	return 0;
}

评论

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

正在加载评论...