codechef Killing Monsters
题目大意:大厨正在玩一个打怪兽的小游戏。游戏中初始时有 n 只怪兽排成一排，从左到右编号为 0 ∼ n − 1。第 i 只怪兽的初始血量为 hi，当怪兽的血量小于等于 0 时，这只怪兽就挂了。 大厨要进行 q 次操作。每次操作中，大厨会选择两个整数 x 和 y，并向下标 k 满足 k&x = k 的怪兽开炮（此处 & 代表按位与操作）。被炮弹打到的怪兽会掉 y 点血。 请告诉大厨，在他每次操作后，还有多少怪兽活着。
做法：考虑把操作分块
预处理每一块中下标为i的要扣的血量。
然后对于某一个下标i，暴力从第一块开始跑，跑到第一个血量不够的块，然后再在那个块里暴力地跑。
看它到哪一个位子血量刚好用完，然后那个x位子ans[x]–.（ans是差分数组，表示从x到最后都少了一个怪兽）
最后累加输出答案即可。
代码：
#include<bits/stdc++.h>
#define N 300005
#define M 605
#define int long long
using namespace std;
int n,m,num,block,limit,len;
int a[N],x[N],y[N],f[M][N],l[N],r[N],ans[N];
inline int gt(int x){return (x-1)/block+1;}
signed main(){
scanf("%lld",&n);limit=1;
for (;limit<n;limit<<=1) len++;limit--;
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
scanf("%lld",&m);block=(int)sqrt(m);
num=m/block;if (m%block) num++;
for (int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;
for (int i=1;i<=m;i++){
scanf("%lld%lld",&x[i],&y[i]);
x[i]&=limit;f[gt(i)][x[i]]+=y[i];
}
for (int i=1;i<=num;i++)
for (int k=0;k<len;k++)
for (int j=0;j<=limit;j++)
if (j>>k&1) f[i][j^(1<<k)]+=f[i][j];//枚举j，显然(j^(1<<k))&j==j,那么j扣的血(j^(1<<k))肯定也会扣(相当于枚举题目里的下标k)
ans[1]=n;
for (int i=1;i<=n;i++){
int j=1;
for (;j<=num&&a[i]>f[j][i-1];j++) a[i]-=f[j][i-1];
if (j>num) continue;
for (j=l[j];j<=m;j++) if ((x[j]&(i-1))==i-1){
if (a[i]>y[j]) a[i]-=y[j];
else break;
}
ans[j]--;
}
for (int i=1;i<=m;i++)
ans[i]+=ans[i-1],printf("%lld\n",ans[i]);
return 0;
}
版权声明：本文为ckr1225原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。