CF997解题报告

A

每次翻转还是区间反转都是减少一段连续0的区间,最后一次必须使用区间反转操作,前面的那个小选哪个即可。

B

先转化题意,先全部选1,那么题目就变成了用4,9,49拼成的不同自然数之和。

考虑一个可达的数字,我们只在最小步数到达他的方案进行统计,这样可以不重不漏(如果同步数,49越多越好)。

肯定到后面是不停选49最优,我们把0~48这些到达这个余数的最小步数算出来,然后剩下的步数就可以选择填几个49。

C

直接被MYY秒掉,我只能膜拜。

分成两个部分:至少有1行相同,在没有行相同的情况下有列相同。

行相同直接随便容斥一下即可。

列相同行不同的情况在容斥的时候也要分两种情况考虑。

一种是钦定的​列颜色不同,那么后面的颜色可以随便填。

一种是钦定的​列颜色相同,那么注意后面随便填的位置还要保证行不能相同。

D

总是想出较难的一部分不会较简单的一部分,不愧是我。

第一棵树是列坐标不变,变行坐标;第二颗树相反。所以应该挺容易发现两棵树是独立的。

我们现在要做的就是把两棵树上长度小于等于​的环的个数然后乘上组合出卷积就是答案。

好像这玩意用生成函数挺好做的样子,这里先留个坑,讲一下点分治​的做法。

对于每一个分治中心统计经过它的环的个数。

设​表示第​个点,第一次到达当前分治中心,步数为​的方案数,​表示第​个点,若干次到达当前分治中心,步数为​的方案数。由于路径逆过来方案数不变,所以把​和​卷起来就是第​个点经过当前分治中心的方案数(对于分治中心直接取​)

总复杂度​

E

线段树+单调栈。

一些比较显然的性质,如果一个区间的​等于其长度,那么就是答案。

把询问离线,扫右端点,然后用分别维护大的单调栈和小的单调栈。

我们考虑对于每一个左端点维护一下到当前右端点的​,这玩意肯定是大于等于0的,当其为0时有贡献,经典套路对于区间维护最小值的个数。

每次向右移动的时候,把所有值​,然后插入值,改变最大栈和最小栈,区间修改权值。

这样我们就可以对于单个右端点处理出所有左端点的贡献了,现在要对于左端点求前缀和。

可以打一个历史统计标记,表示当前的贡献已经被记录了若干次,​的时候把节点之前为0的时候的贡献加上(就是历史统计次数乘上最小值个数)。

怎么看是否最小值恰好为0呢?不能直接看当前数组的​,因为可能贡献是在前几个右端点产生的。

上代码更好理解。

void addti(int x,int t){sum[x]+=1ll*t*num[x]; ti[x]+=t;}
void pushdown(int x){
       if(tag[x]){
           tag[x<<1]+=tag[x]; mi[x<<1]+=tag[x];
           tag[x<<1|1]+=tag[x]; mi[x<<1|1]+=tag[x];
           tag[x]=0;
      }
       if(ti[x]){
           if(mi[x<<1]==mi[x]) addti(x<<1,ti[x]);
           if(mi[x<<1|1]==mi[x]) addti(x<<1|1,ti[x]);
           ti[x]=0;
      }
  }

想一下父亲有标记且有答案贡献的前提:父亲底下有最小值为0。而如果没有​的话,底下的最小值分布一定是没有变的,所以只要最小值和父亲的一样就说明有0的贡献。

利用归纳法,只要说明根节点的最小值恒为0就可以直接用​来​历史标记。

这是显然的,因为枚举到的当前右端点答案一定是0。

上一篇:Java Map集合笔记 && 49. 字母异位词分组


下一篇:Unregistering JMX-exposed beans on shutdown & while singletons of this factory are in destruction 解决