OI题解｜Locked Calculator

浙理工2023新生赛｜Locked Calculator

---

🚀 题目浏览

【题目描述】

一个计算器上有 0,1,2,3,4,5,6,7,8,9,+,−,×,÷,= 这十五个按键。

现在所有的按键都被锁上了，给你一个非负整数 $n$ ，请问最少需要激活几个按键才能够打出这个数？

被激活的按键可以使用任意次。

【输入】

输入第一行包含一个整数 $T (1 \le T \le 10^3)$ ，代表测试组数。

随后 $T$ 行，每行包含一个非负整数 $n (0 \le n \le 10^9)$ 。

【输出】

输出 $T$ 行，代表第 $i$ 行包含第 $i$ 个测试点最少需要的按键数。

【输入样例】

3
0
123
1296

【输出样例】

1
3
3

【提示】

对于 0 ，可以直接使用按键 0 打出。

对于 123 ，可以直接使用按键 1,2,3 打出。

对于 1296 ，可以使用按键 6 和按键 × 打出 6×6×6×6 ，再使用按键 = 得到 1296 。

【原题链接】

https://acm.zstu.edu.cn/problem.php?id=4869

---

☘️ 题解分析

纯纯思维题。

只要发现用 1、+、= 能够合成全部数字即可。（【提示】的例子具有一定迷惑性）

---

🧑🏻‍💻 C++ 代码

手动模拟版 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;

// 获取组成x的数字总数（如1234 -> 4、3242 -> 3）
int d(int x) {
    if (x == 0) return 1;
    set<int> s;
    while (x) {
        s.insert(x % 10);
        x /= 10;
    }
    return s.size();
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        cin >> n;
        cout << min(3, d(n)) << endl;
    }

    return 0;
}