专栏文章

CF2064D 题解

cchenxi2009
CF2064D题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miq8gx02
此快照首次捕获于
2025/12/04 00:40
3 个月前
此快照最后确认于
2025/12/04 00:40
3 个月前
查看原文

思路

考虑先按位分讨，手玩 0≤wi,x≤10\le w_i,x\le1，发现一个神奇的性质：xx 一定不能吃掉两个 wi=1w_i=1。因为 xx 初始最大是 11，吃掉一个就变成 00 了，所以吃不了第二个 11。
类比一下，把这个 0≤wi≤10\le w_i\le1 放在最高位上，就有一个结论：令 aa 为最大的整数使 2a≤x2^a\le x（也即 xx 的最高位），则 xx 只有能力吃一个 wi≥2aw_i\ge 2^a，因为吃掉它以后，x←x⊕wix\leftarrow x\oplus w_i，最高位就变成零了，aa 随之变小。
所以考虑按位从高位到低位、从右往左跳，对于 i=log⁡x,⋯ ,3,2,1i=\log x,\cdots,3,2,1，每次找当前位置左边最近的 wj≥2iw_j\ge2^i，如果 x≥2ix\ge2^i 那么它显然可以一路吃到 wjw_j 右边的，然后再判断是否能吃掉 wjw_j，吃掉之后肯定有 x<2ix<2^i，到碰到 wj>xw_j>x 或 xx 吃掉所有的史莱姆为止。
建议结合代码理解，时间复杂度 O((n+q)log⁡x)O((n+q)\log x)。
看官解学到一个函数 __lg(x)，可以取出 xx 最大的二进制位，返回值为最大的整数 aa 使得 x≥2ax\ge2^a，特别地，x=0x=0 时值为 −1-1。据说复杂度为常数。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int T,n,q,w[300000],s[300000],x,pre[300000][32],mxb,now,nxt;
int main(){
	scanf("%d",&T);
	while(T --){
		scanf("%d%d",&n,&q);
		for(int i = 1;i <= n;i ++) scanf("%d",&w[i]);
		for(int i = 1;i <= n;i ++) s[i] = s[i - 1] ^ w[i];
		for(int i = 1;i <= n;i ++){//pre_{i,j} 记录 w_{1,2,3,...,i} 中最靠右的 w_i>2^j 的位置 
			for(int j = 0;j <= __lg(w[i]);j ++) pre[i][j] = i;
			for(int j = __lg(w[i]) + 1;j < 31;j ++) pre[i][j] = pre[i - 1][j];
		}
		for(int i = 1;i <= q;i ++){
			scanf("%d",&x);
			now = n;//now 记录 x 现在面前还没吃掉的是哪一只史莱姆 
			for(int j = 30;~j;j --){
				if(x < 1 << j) continue;//x 比这一位小，跳过 
				nxt = pre[now][j];
				x ^= s[now] ^ s[nxt],now = nxt;//x 比这一位大，一路走吃掉 w_{nxt+1,...,now} 	
				if(!now || w[now] > x) break;//如果吃完了或吃不掉 w_now 就结束 
				x ^= w[now --];//吃掉 w_now 
			}
			printf("%d ",n - now);
		}
		printf("\n");
	}
	return 0;
}

评论

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

正在加载评论...