CodeChef Killing Monsters

题目链接https://www.codechef.com/problems/MONSTER

题意http://www.codechef.com/download/translated/JAN18/mandarin/MONSTER.pdf

思路:每次暴力算不可取,考虑将攻击一块块考虑,对于每一块我们计算出对每个怪兽的总的攻击量,这个直接高维前缀和即可求得,然后再遍历每个怪兽,如果这个怪兽还存活而且被击杀,我们就暴力遍历这个块找到是什么时候被击杀的,因为暴力遍历只会有n次,每次遍历\sqrt n的长度,所以时间复杂度是O(n\sqrt n)的,而外部是一块块统计,每次遍历,所以时间复杂度大概是O(n\sqrt n logn)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=3e5+10;
struct Query{int x,y;}q[N];
ll h[N],f[N];
int n,i,j,k,mask,len,Q,sz,res[N],block[N];
void cal(int idx){
    int L=(idx-1)*sz+1,R=min(idx*sz,Q);
    for (int i=0;i<=mask;++i) f[i]=0;
    for (int i=L;i<=R;++i) f[q[i].x]+=q[i].y; 
    for (int i=0;i<len;++i){
        for (int status=0;status<(1<<len);++status){
            if (!(status&(1<<i))) f[status]+=f[status|(1<<i)];
        }
    }
}
int main(){
    read(n);
    for(mask=1;mask<n;mask<<=1)len++;mask--; 
    for (i=0;i<n;++i) read(h[i]);
    read(Q),sz=sqrt(Q+0.5);
    for (i=1;i<=Q;++i){
        read(q[i].x),read(q[i].y);
        q[i].x&=mask;
        block[i]=(i-1)/sz+1;
    }
    for (i=1;i<=(Q-1)/sz+1;++i){
        cal(i);
        for (j=0;j<n;++j)if(h[j]>0){
            h[j]-=f[j];
            if (h[j]<=0){
                h[j]+=f[j];
                for (k=(i-1)*sz+1;k<=min(i*sz,Q);++k){
                    if ((j&q[k].x)==j){//careful
                        h[j]-=q[k].y;
                        if (h[j]<=0){
                            res[k]++;
                            break;
                        }
                    }
                }
            }
        }
    }
    for (i=1;i<=Q;++i){
        res[i]+=res[i-1];
        printf("%d\n",n-res[i]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注