P8160 [JOI 2022 Final] 星际蛋糕 (Intercastellar) 题解
gzlinzy
2022-02-18 22:56:18
平时求一个正整数 $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;
}
```