题解 CF1501B 【Napoleon Cake】

_caiji_ · 2021-03-16 17:42:06 · 题解

题目可以转化一下：给一个长为 n 的数组 a，请求出一个长为 n 的数组 b。要求若 a_i 不为 0，则 [b_{i-a_i+1},b_i] 这个区间要为 1。

知道这个题目意思就好办了。题目说 n\leq 2\times 10^5，暴力修改显然超时。我们可以用差分维护一下，每次给区间 [b_{i-a_i+1},b_i] 加 1，最后没被加到的就是 0，反之是 1。这样 O(1) 区间加，O(n) 递推求原数组，不会超时。如果不会差分可以看这里。

//封装一个模版，用起来更方便
class Difference{//difference差分
    private:
        int a[100010],n;
    public:
        void clear(int size){//由于是多测，要清空
            memset(a,0,sizeof a);
            n=size;
        }
        void add(int l,int r,int c=1){//区间加
            a[l]+=c,a[r+1]-=c;
        }
        void init(){//递推求原数组
            for(int i=1;i<=n;i++){
                a[i]+=a[i-1];
            }
        }
        int operator[](int x)const{//访问
            return a[x];    
        }
};
int n;
Difference a;
int mian(){
    scanf("%d",&n);
    a.clear(n);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x) a.add(max(1,i-x+1),i);
    }
    a.init();
    for(int i=1;i<=n;i++){
        printf("%d ",min(1,a[i]));
        //min(1,0)=0，min(1,非0数)=1，保证输出只有0和1
    }
    return puts(""),0;
}