题解：CF585D Lizard Era: Beginning

lsd110504lsd · 2025-07-20 14:53:05 · 题解

我们发现每个数有三种状态，直接搜是 3^n 级别的，不能接受。但是我们发现 是可以接受的,因此我们尝试折半搜索。

我们先枚举前⼀半的状态，再枚举后⼀半的状态。 枚举时可以⽤三进制状压。考虑合并时如何处理三组数之和相等的限制。

我们在记录状态时不妨同时记录上 B-A 和 C-B 的值，这样如果后⼀半的 B-A 和前⼀半的 B-A 和为 0，后⼀半的 C-B 与前⼀半的 C-B 和也为 0，那么这两个状态合并之后就是相等的。因此搜索前⼀半时我们只需要⽤⼀个 map 存储下来前⼀半的 (B-A,C-B) 以及 其对应的 A 的值，在搜索后⼀半时直接在 map ⾥查找 (A-B,B-C) 即可。