CF2145

下个月要打 ICPC Nanjing 了，从今天开始每天加训一场 CF。

后面要从 div2 逐渐过渡到 div1 了。

最近 div2 都只能做四五个题，感觉还是应该往 AK 的方向冲。

CF 题目的特点是角度灵活，注重 key point，所以思考的时候不能太死板，要多从不同角度考虑，从小细节入手。

这里记录一些有助于想到做法的 tips。

vp 的时候 A-E 场切了，但是 D 和 E 都卡了一小会。

D 的话其实题目中给出的定义有一个指向性很明确的反向转化，但是我一开始还是想直接大力构造。。感觉大力构造想一下发现做不出来就要考虑重新转化了。

E 是题意和思路都很明确，但是数据结构实现的时候想糖了，还以为要维护前缀 max 的 min 才能二分来着。实际上应该先走直觉才对吧。

F 是很有意思的题目，找到方向了其实非常简单。可以找到所有本质不同的状态进行转移，倍增优化之后就做完了。感觉这个题还是方向大于思路的一个典型，鼓励选手不要死磕一个角度，而是尝试更灵活的思路吧。

G 是更加吃脑电波的计数。我的理解思路是反着操作，这样不用考虑有没有被覆盖的事情了，染色可以直接等价于删除一行/列。注意到除了第一种颜色以外，其它颜色都可以随意调换顺序进行删除，且每一种删除顺序一一对应一种染色方案。这样我们直接枚举最后剩下什么即可，按照这个算 value 也是容易的，除了第一种颜色是 $\min(a,b)$ 以外每种颜色都要染 $a+b$ 次。枚举 $a,b$ 之后将剩余的行和列分配给 $k-1$ 种颜色使得它们的行和列非空即可，发现不考虑颜色区别就是第二类斯特林数，再乘上 $(k-1)!$ 就是正确答案。

这个题还是比较要求我们避免被无关信息和约束干扰，从题目要求的东西入手，考虑最终的做法的 pattern，反推到做法本身；另外对于 complex/dirty 的部分，如果没有明显的思路就应该考虑转化了，不然只会浪费时间。