题解

题目解析

• 输入输出：第一行输入整数 $N$ 表示待判断数字的个数。接下来 $N$ 行，每行一个由数字 0-9 和大写字母 A-F 组成的字符串（不以 0 开头）。对每行输出 $4$ 个整数（空格分隔），分别表示该数是否可能是二进制、八进制、十进制、十六进制（$1$ 表示可能，$0$ 表示不可能）。
• 数据范围：$1 \le N \le 1000$，字符串长度不超过 $10$。
• 复杂度要求：字符串极短，$O(N \cdot |s|)$ 的线性扫描即可轻松满足 $1\text{s}$ 时限与 $128\text{MB}$ 内存限制。
• 算法知识点：字符串处理、字符比较、进制基础性质

思路解析

1. 核心判定依据：一个字符串能合法表示为 $K$ 进制数，当且仅当字符串中出现的最大字符（按 ASCII 值）不超过 $K$ 进制允许的最大数字符号。
   • 二进制：仅含 0,1，最大允许字符 '1'
   • 八进制：仅含 0-7，最大允许字符 '7'
   • 十进制：仅含 0-9，最大允许字符 '9'
   • 十六进制：含 0-9,A-F，最大允许字符 'F'
2. 提取关键字符：对每行字符串，使用 max_element 快速找到其中 ASCII 值最大的字符 max_ch。
3. 阈值比较：将 max_ch 依次与阈值串 "179F" 中的字符比较：
   • 若 max_ch <= '1'，则满足二进制要求（自然也满足其他三种）
   • 若 max_ch <= '7'，则满足八进制要求
   • 若 max_ch <= '9'，则满足十进制要求
   • 若 max_ch <= 'F'，则满足十六进制要求
   • 若 max_ch > 'F'（如出现 G 及以后字母），则四种进制均不可能

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        // 找出字符串中ASCII值最大的字符，决定该数最大"兼容"到多少进制
        char max_ch = *max_element(s.begin(), s.end());
        
        // "179F" 分别对应二进制、八进制、十进制、十六进制的最大允许字符阈值
        string temp = "179F";
        for (int i = 0; i < temp.size(); i++) {
            // 若max_ch不超过对应进制的最大字符，则该进制可能（输出1）
            if (max_ch <= temp[i]) cout << "1 ";
            else cout << "0 ";
        }
        cout << endl;
    }
    return 0;
}