牛客练习赛97 题解

前言

打得不错？

你发现这 $77$ 题基本上全是套路题，所以并不很困难。

下面是口胡题解。

代码分开到了 $77$ 篇题解。

思路

A

直接分奇偶贪心排序，然后判断即可。

B

对于一个 $ll$，显然和它对应有贡献的 $rr$ 必定满足

直接扫描线+线段树即可。

（听说有高妙贪心写法？）

C

反悔贪心即可。

D

直接树形 dp，记录当根节点颜色假如已经被确定时的两种方案对应方案数即可。

E

一个结论是一段区间可行当且仅当其总石子个数是偶数且最多者不超过总数一半。

笛卡尔树上启发式合并即可。

（听说数据水，乱搞也能过。）

F

LCT 板子，不多说了。

复杂度是可以均摊的。

G

嘴了一个预处理枚举答案位置，然后用卷积得到询问答案的做法。

由于文化课作业来不及了所以没写，所以这个做法可能是假的。

$10^{6}10^6$，这怎么 MTT？

QAQ。

$10^{6}10^6$ MTT 这咋过了？

迷惑。

后记

现在是 2022.3.11，我把 G 题实现了一下，赛时口胡做法确实没假。

但这个 G 题属实迷惑到我了......虽说似乎有不用卷积的写法？

这场 E 题质量还不错，可惜数据造水了。