hihoCoder week 51-1-欧拉路·三 题目1 : 欧拉路·三 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho破解了一道又一道难题,终于来到了最后一关。只要打开眼前的宝箱就可以通关这个游戏了。 宝箱被一种奇怪的机关锁住: 这个机关是一个圆环,一共有2^N个区域,每个区域都可以改变颜色,在黑白两种颜色之间切换。 小Ho控制主角在周围探索了一下,果然又发现了一个纸片: 机关黑色的部分表示为1,白色的部分表示为0,逆时针连续N个区域表示一个二进制数。打开机关的条件是合理调整圆环黑白两种颜色的分布,使得机关能够表示0~2^N-1所有的数字。 我尝试了很多次,终究没有办法打开,只得在此写下机关破解之法。 ——By 无名的冒险者 小Ho:这什么意思啊? 小Hi:我给你举个例子,假如N=3,我们通过顺时针转动,可以使得正下方的3个区域表示为: 因为黑色表示为1,白色表示为0。则上面三个状态分别对应了二进制(001),(010),(101) 每转动一个区域,可以得到一个新的数字。一共可以转动2^N次,也就是2^N个数字。我们要调整黑白区域的位置,使得这2^N个数字恰好是0~2^N-1 小Ho:我懂了。若N=2,则将环上的黑白色块调整为”黑黑白白”,对应了”1100″。依次是”11″,”10″,”00″,”01″四个数字,正好是0~3。那么这个”黑黑白白”就可以打开机关了咯? 小Hi:我想应该是的。 小Ho:好像不是很难的样子,我来试试! 提示:有向图欧拉回路 输入 第1行:1个正整数,N。1≤N≤15 输出 第1行:1个长度为2^N的01串,表示一种符合要求的分布方案 样例输入 3 样例输出 00010111
本题是欧拉路的判定、无向图欧拉路的求解的更进一步,有向图欧拉路的求解。 在有向图中找欧拉路的算法和无向图中相同,还是Fleury算法,只不过这一题需要自己构造有向图。构造的方法详见题目提示,我一开始根据
对于任意两个点,如果点i,点j满足点i的后n-2个数字和点j的前n-2个数字相同,则我们连接有向边(i,j)。这句话来构造的,略显麻烦。因为
而我们构造的图,由构造方法可以知道对于任意一个点,其入度一定为2,出度一定为2。所以它必定存在欧拉回路。所以对于每一个点,它有且只有两个出度,我们只需要求出这两个出度即可,不需要0~n-1一个一个点判断。用二进制表示,对于一个特定的点