CF2110E Melody 题解

这……这种问题，我当然知道，我……我可不是要说给你听的，我只是觉得你不知道的话太可怜了……对，就是这样……所以给我认认真真的记住！

题意要求任意两个连续的声音仅在音量或仅在音高上不同，且任意三个连续的声音不能在音量或在音高上相同。

通过这个信息我们可以知道，若第 $i$ 个声音和第 $i+1$ 个声音在音高上相同，那么第 $i+1$ 个声音和第 $i+2$ 个声音一定在音量上相同。

所以所有相邻的声音组一定构成一个“音量相同”和“音高相同”交错的序列。

考虑将每一个声音抽象成一个连接自身音高和自身音量的一条边，这个时候我们发现我们要求的整个声音序列构成一个欧拉路径。

这个时候直接将音量和音高进行一个离散化然后做二分图无向图欧拉路径就可以了。

找不到代码了。