主要思路
首先，不考虑原问题，只考虑最优策略，显然是当前能匹配的串越长越好。所以可以考虑二分答案，算当前拼接次数下能拼出来的最长的串，再将其与 \(n\) 进行比较。
Continue reading →首先，不考虑原问题，只考虑最优策略，显然是当前能匹配的串越长越好。所以可以考虑二分答案，算当前拼接次数下能拼出来的最长的串，再将其与 \(n\) 进行比较。
Continue reading →刚开始以为是搞\(\log n\)个基底点，然后双向边上面做事情，最后发现找图上最小环的复杂度非常的高。所以 GG。
正解考虑把问题的规模进行缩小：也就是把一些答案预先特判掉。比如说，如果某一个位上有超过三个点连接，那么环的大小就可以被确定为是\(3\)，也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。
再考虑剩下的情况。此时，\(n\)已经缩小了很多，所以我们暴力建图，用 Floyd 跑最小环即可。
真的是玄妙重重。
我们先思考正常的暴力搜索：枚举每一次按下的颜色，然后检查继续更新。考虑用 IDA* 优化这个过程，首先估值函数就是剩下的颜色个数，因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。