Giả sử ta có số nguyên n, ta phải tìm số lượng số nguyên dương ≤ n mà có ít nhất một chữ số xuất hiện nhiều hơn một lần.
Ví dụ: n = 200, đầu ra = 38.
Để giải quyết, ta làm theo các bước:
- Định nghĩa mảng a.
- for x := n; x != 0; x /= 10: thêm x % 10 vào a.
- Đảo ngược mảng a.
- ret := n.
- for w := 1, d := 1; w < a.size(); ++w:
- d := d * min(9, 10 - w + 1).
- ret := ret - d.
- Định nghĩa hàm go() không tham số.
- b := (1 << 10) - 1.
- for i := 0; i < a.size(); ++i:
- for d := (i < 1); d < a[i]; ++d:
- ret := ret - x.
- Nếu ((1 << a[i]) & b) != 0: b ^= (1 << a[i]).
- Ngược lại: return.
- for d := (i < 1); d < a[i]; ++d:
- ret--.
- Gọi go().
- Trả về ret.
Xem triển khai dưới đây:
Ví dụ
#include <bits/stdc++.h> using namespace std; int solve(int n) { vector<int> a; for (int x = n; x; x /= 10) a.push_back(x % 10); reverse(a.begin(), a.end()); int ret = n; for (int w = 1, d = 1; w < a.size(); ++w) { d *= min(9, 10 - w + 1); ret -= d; } auto go = [&]() { int b = (1 << 10) - 1; for (int i = 0; i < a.size(); ++i) { for (int d = (i < 1); d < a[i]; ++d) { int x = 0; if ((1 << d) & b) ++x; for (int j = i + 1; j < a.size(); ++j) x *= 10 - j; ret -= x; } if ((1 << a[i]) & b) b ^= (1 << a[i]); else return; } --ret; }; go(); return ret; } int main(){ cout << solve(200) << endl; return 0; }
Đầu vào
200
Đầu ra
38