Hướng dẫn giải của [200 đề thầy Đức] Bài 74: Số có các chữ số phân biệt
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho đoạn $[l, r]$ với $r \le 10^5$, tìm số nguyên dương nhỏ nhất trong đoạn có các chữ số đôi một khác nhau, nếu không có thì in $-1$.
Sub 1: Vét cạn từng số, kiểm tra bằng sắp xếp — ~O(n \cdot d \log d)~
Thử lần lượt các số $x = l, l+1, \dots, r$. Với mỗi số, đổi ra chuỗi, sắp xếp các chữ số; nếu có hai chữ số liền nhau giống nhau thì số đó không hợp lệ. Gặp số hợp lệ đầu tiên thì in ra và dừng. Đạt 21/21 test. Với $r \le 10^5$, $d \le 6$ nên vẫn chạy nhanh.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long l, r;
cin >> l >> r;
// Vét cạn: thử từng số x từ l đến r, đổi ra chuỗi, sắp xếp các chữ số rồi
// kiểm tra hai chữ số liền nhau có trùng nhau không.
for (long long x = l; x <= r; x++) {
string s = to_string(x);
sort(s.begin(), s.end());
bool distinct = true;
for (size_t i = 1; i < s.size(); i++)
if (s[i] == s[i - 1]) { distinct = false; break; }
if (distinct) {
cout << x << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}
Sub 2: Đánh dấu chữ số bằng bit — ~O(n \cdot d)~
Vẫn duyệt từ $l$ đến $r$ và dừng ở số đầu tiên thỏa mãn, nhưng thay việc sắp xếp bằng một bit mask 10 bit: mỗi chữ số $c$ được đánh dấu bằng bit thứ $c$. Nếu gặp chữ số đã được đánh dấu thì dừng kiểm tra số đó ngay.
Ví dụ $121, 130$: $121$ có chữ số $1$ lặp, $122$ lặp, ..., $123$ có các chữ số khác nhau nên in $123$. Ví dụ $98766, 100000$: mọi số trong đoạn đều có chữ số lặp, in $-1$.
Bẫy cần chú ý: số $0$ (không có trong đoạn vì $l \ge 1$) và việc dừng sớm ngay khi tìm được số đầu tiên.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long l, r;
cin >> l >> r;
// Duyệt x từ l đến r. Dùng bit mask đánh dấu các chữ số đã xuất hiện:
// nếu một chữ số bị đánh dấu rồi thì số đó có chữ số trùng.
for (long long x = l; x <= r; x++) {
int mask = 0;
long long y = x;
bool distinct = true;
while (y > 0) {
int digit = y % 10;
if (mask >> digit & 1) { distinct = false; break; }
mask |= 1 << digit;
y /= 10;
}
if (distinct) {
cout << x << "\n";
return 0; // tìm được số nhỏ nhất đầu tiên thì dừng
}
}
cout << -1 << "\n";
return 0;
}
Bình luận