Hướng dẫn giải của Xâu đối xứng
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
Cho xâu S chỉ gồm chữ cái thường, độ dài tới 10^6. Tìm số ký tự ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp lại thành một xâu đối xứng. Đề đọc từ CAU4.INP và ghi ra CAU4.OUT.
Sub 1: Đếm tần suất bằng quét lại xâu — ~O(n^2)~
Với mỗi ký tự ở lần xuất hiện đầu tiên, quét cả xâu để đếm số lần xuất hiện, rồi đếm số chữ cái có số lần lẻ. Đáp án là max(0, số chữ lẻ − 1). Đạt 16/16 test trong bộ test chấm.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU4.INP", "r")) { freopen("CAU4.INP", "r", stdin); freopen("CAU4.OUT", "w", stdout); }
string s;
cin >> s;
int n = s.size();
// Sub 1: voi moi ki tu lan dau xuat hien, dem so lan xuat hien bang cach quet ca xau (O(n^2))
int odd = 0;
for (int i = 0; i < n; i++) {
bool first = true;
for (int j = 0; j < i; j++) if (s[j] == s[i]) { first = false; break; }
if (!first) continue;
int cnt = 0;
for (int j = 0; j < n; j++) if (s[j] == s[i]) cnt++;
if (cnt % 2 == 1) odd++;
}
// Chi can giu lai nhieu nhat 1 chu cai co so lan le, nen bo (odd - 1) ki tu
cout << max(0, odd - 1) << endl;
return 0;
}
Sub 2: Mảng tần suất 26 chữ — ~O(n)~
Xâu đối xứng cho phép tối đa một chữ cái có số lần lẻ (đặt ở giữa). Vì vậy mỗi chữ có số lần lẻ dư ra đúng một ký tự cần bỏ, trừ một chữ được giữ lại. Đếm tần suất bằng mảng 26 phần tử rồi đếm số chữ lẻ. Đạt 16/16 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU4.INP", "r")) { freopen("CAU4.INP", "r", stdin); freopen("CAU4.OUT", "w", stdout); }
string s;
cin >> s;
long long freq[26] = {0};
for (char c : s) freq[c - 'a']++;
// Dem so chu cai co so lan xuat hien le
int odd = 0;
for (int c = 0; c < 26; c++) if (freq[c] % 2 == 1) odd++;
// Xau doi xung chi cho phep toi da 1 chu cai co so lan le (o giua), nen bo (odd - 1) ki tu
cout << max(0, odd - 1) << endl;
return 0;
}
Bình luận