Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 3033: 太鼓达人

题目链接

传送门

Description

  七夕祭上,assass_cannotin牵着Claire的手,在明亮的灯光和欢乐的气氛中愉快地穿行。这时,在前面忽然出现了一台太鼓达人机台,而在机台前坐着的是刚刚被精英队伍成员XLk、Poet_shy和lydrainbowcat拯救出来的的applepi。看到两人对太鼓达人产生了兴趣,applepi果断闪人,于是cl拿起鼓棒准备挑战。然而即使是在普通难度下,assass_cannotin的路人本性也充分地暴露了出来。一曲终了,不但没有过关,就连鼓都不灵了。Claire十分过意不去,决定帮助工作人员修鼓。
  鼓的主要元件是M个围成一圈的传感器。每个传感器都有开和关两种工作状态,分别用1和0表示。显然,从不同的位置出发沿顺时针方向连续检查K个传感器可以得到M个长度为K的01串。Claire知道这M个01串应该是互不相同的。而且鼓的设计很精密,M会取到可能的最大值。现在Claire已经了解到了K的值,他希望你求出M的值,并给出字典序最小的传感器排布方案。

Input

  一个整数K。
 

Output

 一个整数M和一个二进制串,由一个空格分隔。表示可能的最大的M,以及字典序最小的排布方案,字符0表示关,1表示开。你输出的串的第一个字和最后一个字是相邻的。

Sample Input

3

Sample Output

8 00010111

HINT

 得到的8个01串分别是000、001、010、101、011、111、110和100。注意前后是相邻的。长度为3的二进制串总共只有8种,所以M = 8一定是可能的最大值。

  对于全部测试点,2≤K≤11。

闲扯淡

assass_cannotin和Claire秀恩爱无耻
我跟我家珂朵莉秀恩爱了么
没有

题解

这道题实际上是将k-1位的二进制数看做点,k位的二进制数看成边,并且连接两个点的边就是将这两个点的权怼起来
像这样

(图片来自Clove_unique zyf2000学姐
然后每个点的入度和出度相等并且全部是偶点,是一个标准的欧拉图,所以只需要在这个图中找字典序最小的欧拉回路就行了
可以贪心地找字典序较小的边,然后实在不行了就回溯
这样的话时间复杂度我不大会…不过实测了一下是接近O(n+m)的吧

代码

10 Comments

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏