Hướng dẫn giải của Số độc lập (đề TP.HCM 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Tìm số độc lập nhỏ nhất lớn hơn X (chữ số đôi một khác nhau).
Sub 1: Vét cạn, ~O(M)~ với M là khoảng cách tới đáp án
Thử lần lượt X+1, X+2, ... và kiểm tra chữ số đôi một khác nhau. Nếu chỉ nộp sub này: đúng 50/50 test.
Sub 2: Xây dựng trực tiếp, ~O(\log X)~
Giữ tiền tố dài nhất của Y = X+1 có chữ số khác nhau; tại vị trí kế tiếp chọn chữ số lớn hơn nhỏ nhất chưa xuất hiện, rồi điền phần còn lại bằng các chữ số nhỏ nhất còn lại. Bẫy: đáp án có thể nhiều hơn số chữ số của X.
Chương trình hoàn chỉnh
main đọc X; X ≤ 10^4 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long X;
// Kiem tra cac chu so cua x co doi mot khac nhau khong (dung bitmask 10 chu so)
bool distinctDigits(long long x) {
int seen = 0;
while (x > 0) {
int d = x % 10;
if (seen >> d & 1) return false;
seen |= 1 << d;
x /= 10;
}
return true;
}
// Sub 1: vet can. Thu lan luot X+1, X+2, ... cho den khi gap so co chu so doi mot khac nhau
void sub1() {
long long y = X + 1;
while (!distinctDigits(y)) y++;
cout << y << "\n";
}
// Sub 2: xay dung truc tiep. Gọi s la X+1. Neu s da co cac chu so khac nhau thi dap an la s.
// Nguoc lai, giu tien to dai nhat co chu so khac nhau, tai vi tri ke tiep chon chu so lon hon
// nho nhat chua xuat hien trong tien to, roi dien phan con lai bang cac chu so nho nhat con lai.
void sub2() {
string s = to_string(X + 1);
int L = s.size();
// mask[p] = tap chu so cua tien to do dai p; pref = do dai tien to dai nhat co chu so khac nhau
vector<int> mask(L + 1, 0);
int pref = 0;
for (int p = 1; p <= L; p++) {
int d = s[p - 1] - '0';
if (mask[p - 1] >> d & 1) break;
mask[p] = mask[p - 1] | (1 << d);
pref = p;
}
if (pref == L) {
cout << s << "\n";
return;
}
// Thu giu tien to dai nhat truoc (cho ket qua nho nhat)
for (int p = pref; p >= 0; p--) {
int cur = s[p] - '0';
for (int c = cur + 1; c <= 9; c++) {
if (mask[p] >> c & 1) continue;
string res = s.substr(0, p) + char('0' + c);
int m = mask[p] | (1 << c);
for (int d = 0; d <= 9 && (int)res.size() < L; d++)
if (!(m >> d & 1)) {
res += char('0' + d);
m |= 1 << d;
}
cout << res << "\n";
return;
}
}
// Khong con cach nao voi L chu so: dap an co L+1 chu so, chu so dau nho nhat la 1
string res = "1";
int m = 1 << 1;
for (int d = 0; d <= 9 && (int)res.size() < L + 1; d++)
if (!(m >> d & 1)) {
res += char('0' + d);
m |= 1 << d;
}
cout << res << "\n";
}
int main() {
freopen("sodoclap.inp", "r", stdin);
freopen("sodoclap.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> X;
if (X <= 10000) sub1(); // X nho: thu lan luot cung nhanh
else sub2(); // X lon: xay dung truc tiep
return 0;
}
Bình luận