题目
题目描述
Z 落在了一个叫做 "后" 的世界里，这个世界里所有的数字都是以二进制表示的，Z 发现这个世界中的一些数字很特殊，如镜子一样，$0$ 透过镜子变成 $1$，$1$ 透过镜子变成 $0$。
准确地来说，被称为"镜"的数字需要满足在二进制下数码 $1$ 和 $0$ 的数量一样多。
"后"中"镜"太多了，现在请你在小于等于 $n$ 的正整数范围内找到最大那一个可以被称为 "镜" 的数字，输出其十进制表示。
输入格式
第一行一个整数 $Q$，表示询问次数。
接下来 $Q$ 行，每行一个整数 $n$，表示一次询问。
输出格式
$Q$ 行，每行一个整数，表示对应询问的答案。
代码登录后可见
代码登录后可见
数据范围与约定
| 测试点编号 | $n$ | $Q$ |
| :--------: | :--------: | :--------: |
| $1$ | $=10$ | $=1$ |
| $2\sim 3$ | $\le 10$ | $\le 10$ |
| $4\sim 8$ | $\le 106$ | $\le 10$ |
| $9\sim 10$ | $\le 106$ | $\le 105$ |
对于全部测试数据满足：$2\le n\le 106$，$1\le Q\le 105$。
题解
题意
本题考察的是十进制转二进制和字符（或数字统计）
题目传送门
解析
首先，当时我看到这道题后，我变先写了一个10进制转2进制的程序，代码如下：
代码登录后可见
不过经过思考第9行的反转，可以不用写，因为本题只不过是统计01出现的数量，可以省略。
统计01字符串的代码如下：
代码登录后可见
然后我就写了第一版代码：
代码登录后可见
提交后拿了80分，最后两个点TLE了，原来这段代码的时间复杂度是：O(q*N + N log N)，此时q的最大值只能是$7 \times 104$,而题目最大值是$105$，所以，我使用了预处理的思路，算法时间复杂度为：$O(N \log N + q)$,轻松通过
标程
代码登录后可见
