- 定义一个仅由(0,1)构成的十进制正数(A)是好的，当且仅当它转化成的二进制数(B)满足(A)是(B)的后缀。
- 求第(n)个好数。
- (nle10^4)
推性质+大力(BFS)
我们发现，给一个数加上一个新的最高位(10^k)，由于(2^k|10^k)，它不会影响到第(0sim k-1)位。
所以说，一个数加上一个新的最高位是好数，一个必要条件就是它的第(0sim k-1)位是好的。
因此我们可以写一个(BFS)，每轮将最高位数(l)加上(1)。
先枚举一下队列中每个数看一下不加(10^l)是否仍是好数，是的话就加入新的队列。（注意，这部分并不统计答案，因为好数不能有前导(0)，而没有前导(0)的我们已经算过答案了）
然后枚举一下队列中每个数看一下加上(10^l)是否能成为好数，是的话就加入新的队列且加入答案序列。
最终只要排除掉(0)，输出剩余序列的第(n)项即可。
代码：(O(n))
n=int(input())
q=[0]#初始队列中只有0
l=0#初始最高位为0
t=1#10^0=1
ans=[0]#初始答案序列中只有0
while len(ans)<=n:
nq=[]#清空新队列
for i in q:
if (i>>l&1)==0:#不加10^l是否仍是好数
nq.append(i)#加入新的队列
for i in q:
if ((i+t>>l)&1)==1:#加上10^l是否能成为好数
nq.append(i+t)#加入新的队列
ans.append(i+t)#加入答案序列
q=[]#清空BFS队列
for i in nq:
q.append(i)#把新队列中的元素转移
l+=1#最高位增加1
t*=10#10^l乘上10
print(ans[n])#输出答案序列第n项