题解 AT3871 【[AGC021E] Ball Eat Chameleons】

这道题方案数不同是颜色序列不同，那么我们就可以思考什么样的颜色序列可以在最优策略下完成全部的染色。 不妨先观察一个变色龙变为红色的条件： - 吃的红球数大于蓝球 - 吃的红球数等于蓝球且最后一次吃的是蓝球 第一个操作染红一个变色龙需要至少多一个红球，对先后顺序没有任何要求；第二个操作则不用数量差，染红一条要先一个红后一个蓝，很容易让人想到括号匹配。于是我们思考一下，如果颜色序列已知，我们的最优策略是什么。（下面令红球为`(`，蓝球为`)`） 由于数量差的喂法不讲究顺序，所以我们肯定先贪心地括号匹配，最后剩下的再用 $2$ 红 $1$ 蓝的方法喂就可以了。不难发现，这样成功的条件是： 匹配数+红球数-蓝球数 $\ge n$。而对匹配数有要求可以转化为限制失配数，折线法即可。 然而，变色龙染色的规则并不是括号匹配，对于红球数等于蓝球数的变色龙，只要最后一个放蓝球就可以了，例如 `())(()`、`)(()` 也能让一条变色龙变红，但是不难发现这样子也要用至少一个匹配，所以只让匹配的括号去用第二种方法染色是不劣的。 但是上面的做法的先决条件是 $红球数 > 蓝球数$ ，否则我们是无法使用第一种操作的。如果红球数等于蓝球数，不仅要满足匹配数 $\ge n$ ，还要求最后一个括号必须是 `)`，那么我们令蓝球数减一后按上面的方法做就好了。 代码很丑就不放了（