题目

题目描述

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 10⁶$ | $\le 10$ |
| $9\sim 10$ | $\le 10⁶$ | $\le 10⁵$ |

对于全部测试数据满足：$2\le n\le 10⁶$，$1\le Q\le 10⁵$。

题解

题意

本题考察的是十进制转二进制和字符（或数字统计）
题目传送门

解析

首先，当时我看到这道题后，我变先写了一个10进制转2进制的程序，代码如下：

bool int_bin(int x){
    int t = x;
    string str = "";
    while (x > 0){
        if (x % 2 == 0)str += "0";
        else str += "1";
        x /= 2;
    }
  reverse(str.begin(),str.end());
}

不过经过思考第9行的反转，可以不用写，因为本题只不过是统计01出现的数量，可以省略。
统计01字符串的代码如下：

int ans0 = 0, ans1 = 0;
for (int i = 0;i < str.size();i ++){
    if (str[i] == '0') ans0 ++;
    else ans1 ++;
}

然后我就写了第一版代码：

#include<bits/stdc++.h>
using namespace std;
int s[1000005];
void int_bin(int x){
    int t = x;
    string str = "";
    while (x > 0){
        if (x % 2 == 0)str += "0";
        else str += "1";
        x /= 2;
    }
    int ans0 = 0, ans1 = 0;
    for (int i = 0;i < str.size();i ++){
        if (str[i] == '0') ans0 ++;
        else ans1 ++;
    }
    if (ans0 == ans1) s[t] = 1;
    else s[t] = 3;
    // cout << ans0 << ans1;
}
int main(){
    int q;
    cin >> q;
    while (q --){
        int n;
        cin >> n;
        for (int i = n;i >= 1;i --){
            // cout << s[i] << endl;
            if (s[i] == 0) {
                int_bin(i);
            }
            if (s[i] == 1) {
                cout << i << endl;
                break;
            }
        }
        
    }
    return 0;
}

提交后拿了80分，最后两个点TLE了，原来这段代码的时间复杂度是：O(q*N + N log N)，此时q的最大值只能是$7 \times 10⁴$,而题目最大值是$10⁵$，所以，我使用了预处理的思路，算法时间复杂度为：$O(N \log N + q)$,轻松通过

标程

#include<bits/stdc++.h>
using namespace std;
int s[1000005];
bool int_bin(int x){
    int t = x;
    string str = "";
    while (x > 0){
        if (x % 2 == 0)str += "0";
        else str += "1";
        x /= 2;
    }
    int ans0 = 0, ans1 = 0;
    for (int i = 0;i < str.size();i ++){
        if (str[i] == '0') ans0 ++;
        else ans1 ++;
    }
    if (ans0 == ans1) return true;
    return false;
    // cout << ans0 << ans1;
}
int main(){
    for (int i = 1;i <= 1000000;i ++){
        if (i == 1) s[1] = 1;
        else {
            if (int_bin(i) == true) s[i] = i;
            else s[i] = s[i - 1];
        }
    }
    int q;
    cin >> q;
    while (q --){
        int n;
        cin >> n;
        cout << s[n] << endl;
    }
    return 0;
}