Lời giải kì thi HSG9 môn tin học thành phố Đà Nẵng năm 2023
Sau đây là lời giải kì thi HSG9 môn tin học thành phố Đà Nẵng năm 2023
Link nộp bài: LQDOJ
Bài 1: Ước thực sự lớn nhất (UTSLN)
🏷️Tags: Divisor
Ý tưởng
Xét hết các số trong đoạn từ $1 \to (x - 1)$, những số nào là ước của $x$ thì tìm giá trị lớn nhất trong những số đó.
Tối ưu thuật toán
Nhận thấy rằng thuật toán ở trên sẽ có độ phức tạp là $O(x)$, đối với subtask $2$ và $3$ thì thuật toán này sẽ không thỏa mãn. Vì vậy chúng ta sẽ cải tiến thuật toán như sau:
- Giả sử viết được $x$ dưới dạng $x = i \times j$ với $i \le j$ thì giá trị lớn nhất của $i$ là $\sqrt{x}$. Khi đó, giá trị $j$ bằng $\frac{x}{i}$, và chắc chắn cả $i$ và $j$ đều là ước của $x$. Vì vậy chỉ cần xét $i$ thì chúng ta có thể xét được $j$.
- Độ phức tạp thuật toán từ $O(x) \to O(\sqrt{x})$.
Code
Time: $O(\sqrt{x})$.
Algo: Divisor.
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
long long ans = 1;
cin >> n;
for (long long i = 2; i <= sqrt(n); i ++) {
if (n % i == 0) ans = max(ans, max(i, n / i));
}
cout << ans;
}
Bài 2: Đếm kí tự (DEMKT)
🏷️Tags: String, Brute Force
Thuật toán
- Đếm số lần xuất hiện của mỗi kí tự trong xâu $S$.
- Lưu các kí tự phân biệt trong xâu $S$ vào trong tập hợp $A$.
- Đếm số lượng kí tự có số lần xuất hiện $\geq 2$ trong tập hợp $A$.
Code
Time: $O|S|$ $\log$ $|S|)$.
Algo: String, Brute Froce.
#include <bits/stdc++.h>
using namespace std;
set<char> st;
long long cnt[1000];
long long ans = 0;
int main() {
string s;
getline(cin, s);
for (int i = 0; i < s.size(); i ++) cnt[s[i]] ++, st.insert(s[i]);
for(auto it = st.begin(); it != st.end(); ++ it) {
if (cnt[*it] >= 2) ans ++;
}
cout << ans;
}
Bài 3: Số nguyên tố đối xứng (NTDX)
🏷️Tags: Backtracking, Prime
Ý tưởng
Đệ quy để tạo số và kiểm tra xem số đó có phải là số nguyên tố đối xứng hay không.
Tối ưu thuật toán
Nhận xét: Một số có chiều dài $n$ là số đối xứng nếu đoạn từ $1 \to (n / 2)$ $=$ đoạn từ $(n - n / 2 + 1) \to n$ (đảo ngược).
Vì vậy ta chỉ cần đệ quy để tạo nửa đầu của số(gọi là $s$) và xét chiều dài chẵn lẻ của số đó.
- Nếu chiều dài là chẵn thì số đó được tạo ra bằng $\overline{\rm sz}$ (với $z$ là đảo ngược của $s$)
- Nếu chiều dài là lẻ thì số đó được tạo ra bằng $\overline{\rm smz}$ (với $z$ là đảo ngược của $s$, $m$ là số nằm trong đoạn từ $0 \to 9$.
Code
Time: $O(9^{|x - 1| / 2}.\frac{sqrt(x)}{6})$.
Algo: Backtracking, Prime
#include <bits/stdc++.h>
using namespace std;
long long x;
long long ans = 0;
long long isprime(long long a) { // Kiểm tra số nguyên tố
if (a < 2) return 0;
if (a == 2 || a == 3) return 1;
if (a % 2 == 0 || a % 3 == 0) return 0;
for (int j = 5; j <= sqrt(a); j += 6) {
if (a % j == 0 || a % (j + 2) == 0) return 0;
}
return 1;
}
long long pow10(long long n) {
long long s = 1;
for (int i = 1; i <= n; i ++) s *= 10;
return s;
}
void calc(int i, long long s, int n) { // Tạo số và kiểm tra
if (i <= n / 2) { // Chỉ tạo nửa đầu số
for (int j = 0; j <= 9; j ++) {
if (j == 0) {
if (i != 1) calc(i + 1, s * 10 + j, n); // Không tính trường hợp số 0 ở đầu
} else calc(i + 1, s * 10 + j, n);
}
} else {
long long z;
string g = to_string(s);
reverse(g.begin(), g.end()); // nửa cuối
istringstream(g) >> z;
long long ss = s;
if (n % 2 == 0) { // Trường hợp chiều dài chẵn
ss = ss * pow10(n / 2) + z;
if (isprime(ss) && ss < x && ss > 10) ans ++;
} else { // Trường hợp chiều dài lẻ
for(int j = 0; j <= 9; j ++) {
long long sss = ss;
sss = (sss * 10 + j) * pow10(n / 2) + z;
if (isprime(sss) && sss < x && sss > 10) ans ++;
}
}
}
}
int main () {
freopen("NTDX.INP", "r", stdin);
freopen("NTDX.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> x;
long long n = to_string(x - 1).size();
for (int i = 2; i <= n; i ++) calc(1, 0, i); // Tạo số với chiều dài i
cout << ans;
}
Bài 4: Tổng của các hoán vị (THV)
🏷️Tags: Backtracking, Math
Thuật toán
Hướng quay lui
- Liệt kê những hoán vị bằng quay lui và tính tổng của những hoán vị đó.
- Liệt kê hoán vị: blog.luyencode.net
Code
Time: $O(n.n!)$.
Algo: Backtracking.
#include <bits/stdc++.h>
using namespace std;
long long a[20];
bool used[1000];
long long n, ans = 0;
string x;
long long get() { // Tạo số
if (a[0] == 0) return 0; // Trường hợp số 0 ở đầu
long long res = 0;
for (int i = 0; i < x.size(); i ++) res = res * 10 + a[i];
return res;
}
void solve (int pos) { // Sinh hoán vị
for (int i = 0; i < x.size(); i ++) {
if (!used[x[i]]) {
a[pos] = x[i] - 48;
used[x[i]] = true;
if (pos == x.size() - 1) ans += get();
else solve(pos + 1);
used[x[i]] = 0;
}
}
}
int main () {
freopen("THV.INP", "r", stdin);
freopen("THV.OUT", "w", stdout);
cin >> x;
sort(x.begin(), x.end());
solve(0);
cout << ans;
}
Hướng toán học
Kí hiệu $X$ là tập hợp tất cả số tự nhiên gồm n chữ số khác nhau đôi một lập từ $n$ chữ số của $n$.
Xét $x = \overline{\rm a_1a_2a_3…a_n}$ $\in X$
Hoán vị đang xét là $\overline{\rm a_1a_2a_3…a_n}$ thì $\overline{\rm a_1a_2a_3…a_{n - 1}}$ sẽ có $(n - 1)!$ hoán vị $\Rightarrow$ có $(n - 1)!$ số có chữ số hàng đơn vị là $a_n$ với mỗi $a_n \in X$.
$\Rightarrow$ Vậy công thức tổng tất cả chữ số hàng đơn vị của các phần tử $a \in X$ là:
$$ (a_1 + a_2 + a_3 + … a_n).(n - 1)! $$
Lập luận tương tự, ta tính được tổng tất cả các chữ số hàng chục, hàng trăm, … với các phần tử $a \in X$.
Code
Time: $O(n ^ 2)$.
Algo: Math.
#include <bits/stdc++.h>
using namespace std;
string x;
long long solve (string x) {
long long ans = 0;
long long cnt = 1;
for (int i = 1; i < x.size(); i ++) cnt *= i;
for (int i = 0; i < x.size(); i ++) {
for (int j = 0; j < x.size(); j ++) ans += (x[i] - 48) * pow(10, j) * cnt;
}
return ans;
}
int main () {
freopen("THV.INP", "r", stdin);
freopen("THV.OUT", "w", stdout);
cin >> x;
sort(x.begin(), x.end());
if (x[0] == '0') cout << solve(x) - solve(x.substr(1, x.size() - 1)); // Trường hợp có chữ số 0
else cout << solve(x); // Trường hợp không có chữ số 0
}