CF2064D 题解

chenxi2009 · 2025-02-17 15:53:42 · 题解

思路

考虑先按位分讨，手玩 0\le w_i,x\le1，发现一个神奇的性质：x 一定不能吃掉两个 w_i=1。因为 x 初始最大是 1，吃掉一个就变成 0 了，所以吃不了第二个 1。

类比一下，把这个 0\le w_i\le1 放在最高位上，就有一个结论：令 a 为最大的整数使 2^a\le x（也即 x 的最高位），则 x 只有能力吃一个 w_i\ge 2^a，因为吃掉它以后，x\leftarrow x\oplus w_i，最高位就变成零了，a 随之变小。

所以考虑按位从高位到低位、从右往左跳，对于 i=\log x,\cdots,3,2,1，每次找当前位置左边最近的 w_j\ge2^i，如果 x\ge2^i 那么它显然可以一路吃到 w_j 右边的，然后再判断是否能吃掉 w_j，吃掉之后肯定有 x<2^i，到碰到 w_j>x 或 x 吃掉所有的史莱姆为止。

建议结合代码理解，时间复杂度 O((n+q)\log x)。

看官解学到一个函数 __lg(x)，可以取出 x 最大的二进制位，返回值为最大的整数 a 使得 x\ge2^a，特别地，x=0 时值为 -1。据说复杂度为常数。

代码

#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;
}