题解 CF1501B 【Napoleon Cake】

posted on 2021-03-16 17:42:06 | under 题解 | source

题目可以转化一下：给一个长为 \(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;
}