Hướng dẫn giải của ĐỐI XỨNG (CỤM BN1)
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
Đếm số đối xứng (đọc xuôi và ngược giống nhau) trong đoạn [1; N] với N <= 10^6. Đọc từ DOIXUNG.INP, ghi ra DOIXUNG.OUT.
Sub 1: Đổi sang xâu rồi so sánh với xâu đảo ngược — ~O(N log N)~
Với mỗi x từ 1 đến N, đổi x thành xâu, đảo xâu và so sánh. Đúng và đủ nhanh với N <= 10^6.
Kết quả chấm: đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DOIXUNG.INP", "r")) {
freopen("DOIXUNG.INP", "r", stdin);
freopen("DOIXUNG.OUT", "w", stdout);
}
long long n;
cin >> n;
long long cnt = 0;
// Vet can: voi moi x, doi x thanh chuoi roi kiem tra doc xuoi va doc nguoc
for (long long x = 1; x <= n; x++) {
string s = to_string(x);
string r = s;
reverse(r.begin(), r.end());
if (s == r) cnt++;
}
cout << cnt << endl;
return 0;
}
Sub 2: Đảo số bằng phép chia lấy dư — ~O(N log N)~
Đảo số x bằng cách lấy chữ số cuối: r = r*10 + x mod 10, rồi x là đối xứng khi r = x. Không dùng xâu.
Kết quả chấm: đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
// Dao nguoc so x bang phep chia lay du (khong dung chuoi)
long long daoSo(long long x) {
long long r = 0;
while (x > 0) {
r = r * 10 + x % 10;
x /= 10;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DOIXUNG.INP", "r")) {
freopen("DOIXUNG.INP", "r", stdin);
freopen("DOIXUNG.OUT", "w", stdout);
}
long long n;
cin >> n;
long long cnt = 0;
for (long long x = 1; x <= n; x++)
if (daoSo(x) == x) cnt++; // so doi xung khi dao nguoc bang chinh no
cout << cnt << endl;
return 0;
}
Bình luận