P8160 [JOI 2022 Final] 星际蛋糕 (Intercastellar) 题解

平时求一个正整数 x 除以 2 的余数，我们可以使用 x%2，也可以使用 x&1，而后者其实是取 x 在二进制表示中最靠右的一位。因此我们发现在二进制下，如果最靠右一位为 0，则这个数为偶数。所以，一个数在二进制下末尾 0 的个数即为这个数能被 2 整除的次数。

我们知道，lowbit 函数可取一个数二进制表达式中最低位的1所对应的值。

#define lowbit(y) y&-y

例如，数 10 的二进制表达为 1010，那么此函数返回值为 1010 从右往左数第一个 1 出现的位置，即 2^1=2。我们发现，此时的 2 正好为长度为 10 的蛋糕被分出的块数。所以我们只要利用 lowbit 函数计算出每块蛋糕被分成的块数，并用前缀和记录切到第 i 块蛋糕时当前蛋糕的总数即可。

由于每次询问的 x_j 单调不减，所以我们可以用上次询问时的总块数继续查询此次询问。

代码：

#include<bits/stdc++.h>
#define int long long
#define lowbit(y) y&-y
using namespace std;
int n,a[200005],lb[200005],f[200005],t,x,i=1;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        lb[i]=lowbit(a[i]);
        f[i]=f[i-1]+lb[i];
    }
    cin>>t;
    while(t--){
        cin>>x;
        for(;i<=n;i++){
            if(f[i]>=x){
                cout<<a[i]/lb[i]<<endl;
                break;
            }
        }
    }
    return 0;
}