题意翻译

给定一个整数 $x$（$1 \le x \le 1000$）。要求找到最小的非负整数 $y$，使得 $x$ 和 $y$ 的十进制表示中至少有一个相同的数字。
例如：$x=96$，$y=6$ 满足条件（都有数字 $6$），且没有更小的 $y$ 满足条件。

关键观察

• 任何多位数 $y$（即 $y \ge 10$）必然有一个最高位数字 $d$（$1 \le d \le 9$）或者某个数位上的数字 $d$。
  如果 $d$ 出现在 $x$ 中，那么一位数 $d$ 本身就满足条件，且 $d < y$。
• 因此，最优的 $y$ 必定是一位数（即 $0 \le y \le 9$）。
• 我们只需要找出 $x$ 的十进制表示中包含的最小数字（$0$ 到 $9$），将其作为 $y$ 输出即可。

算法步骤

对每个测试用例：

1. 读入整数 $x$。
2. 提取 $x$ 的每一位数字，用一个布尔数组 has[0..9] 记录哪些数字出现过。
3. 从 $0$ 到 $9$ 遍历，找到第一个 has[d] == true 的数字，输出该数字。

复杂度分析

• 每个 $x$ 最多有 $4$ 位（因为 $x \le 1000$），提取数字 $O(\log x)$。
• 查找最小数字最多检查 $10$ 次。
• 总复杂度 $O(t \cdot \log x)$，$t \le 1000$，完全可行。

正确性证明

• 充分性：若 $d$ 是 $x$ 的某一位数字，则 $y=d$ 与 $x$ 共享数字 $d$，因此满足条件。
• 最小性：假设存在更小的非负整数 $y' < d$ 满足条件。由于 $d$ 是 $x$ 中出现的最小数字，任何小于 $d$ 的非负整数只能由比 $d$ 更小的数字组成（如 $0,1,\dots,d-1$ 以及它们的组合）。但这些数字都没有在 $x$ 中出现过（因为 $d$ 是最小出现数字），因此 $y'$ 不可能与 $x$ 有公共数字。矛盾。故 $d$ 是最小的可行 $y$。

代码实现

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

void solve() {
    int x;
    cin >> x;
    bool has[10] = {false};
    // 提取每一位
    int tmp = x;
    while (tmp > 0) {
        has[tmp % 10] = true;
        tmp /= 10;
    }
    // 找最小出现的数字
    for (int d = 0; d <= 9; ++d) {
        if (has[d]) {
            cout << d << '\n';
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

示例验证

输入：

5
6
96
78
122
696

• $x=6$：数字 $\{6\}$，最小为 $6$，输出 $6$。
• $x=96$：数字 $\{9,6\}$，最小为 $6$，输出 $6$。
• $x=78$：数字 $\{7,8\}$，最小为 $7$，输出 $7$。
• $x=122$：数字 $\{1,2\}$，最小为 $1$，输出 $1$。
• $x=696$：数字 $\{6,9\}$，最小为 $6$，输出 $6$。

与题目示例输出完全一致。