CF1254&&CF1255 总结

div2 A

猪逼题。。

div2 B

如果题面不改的话还是有点难想的,但是改了后就很啥b了。。

div2 C

其实也很好写,但是那天我太困了。。

首先我们可以很方便地确定起点,然后我们注意到对于原来的序列 (a_{i-1},a_i,a_{i+1}),若前两个及其前面部分已确定,那么 (a_{i+1}) 就可以确定,所以求出 (a_1,a_2) 然后顺着遍历一遍就行了。。

div1 A

也很啥b的题,就是简单贪心就行了。。

div1 B

首先可以求出 sum。

(sum=1),一定无解。

然后可能最优的 k 一定是 sum 的约数且肯定是质数,所以我们可以对 sum 分解质因数然后来求对于一个 k 的答案。

我们可以注意到,在满足条件的情况下,所有的前缀和也都是被 k 整除的,于是我们可以扫一遍,对于一个位置 i,当前前缀和为 s (取模后),那么若 s 不被 k 整除,要 s 被 k 整除,那么可以把 s 向后移 s 或 从后面拿 k-s 个,然后更新答案即可。

div1 C

好像是交互加计算几何。。

这几天学了再做。

div1 D

有点意思。。

考虑对于一个操作一,看看 v 对于那些 x 有什么贡献。。

首先,若 x 不为 v 的子树,那么如果 r 在 v 的子树内,则对 x 有 (frac{sz[v]}{n} imes d) 的贡献。。

然后,如果 x 为 v 的子树,那么如果 r 不在 x 的为 v 儿子的祖先 y 的子树内,那么对于 x 有 (frac{n-sz[y]}{n} imes d) 的贡献。

当然,对于 v 本身一定2会有 d 的贡献。

然后对于情况一和三都好求,用树状数组在 dfn 上维护一下就行了,但是对于情况二,由于每次 y 都是不同的,当然我们可以暴力更新,但这样复杂度是不对的。。

那么我们考虑存一部分信息到节点,每次查询再更新答案。

考虑重链剖分,每次都更新重儿子所在子树,然后每次跳链更新答案。这样就将 (O(nlog n)) 修改 + (O(log n)) 查询变为了 (O(log n)) 修改 + (O(log n)) 查询。。

这种优化维护树上信息的问题还是要经常考虑树链剖分的。。

div1 E

我题都看不懂,等题解多了再写吧。。

原文地址:https://www.cnblogs.com/Hikigaya/p/11907778.html