Hướng dẫn giải của [Beginner Free Contest 09] DANCING
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
Đề yêu cầu đếm số chữ cái trong toàn bộ bài hát. Mỗi cụm từ A[i] có số chữ cái cố định, nên chỉ cần cộng đúng số lần mỗi cụm được hát.
Sub 1: Vét cạn - ~O(n^2)~, dùng khi ~n \le 5000~
Mô phỏng đúng hai vòng lặp của thuật toán: mỗi lần hát A[j] thì cộng số chữ cái của A[j] vào đáp số. Nếu chỉ nộp sub này: đúng 8/10 test.
Sub 2: Cộng dồn (prefix sum) - ~O(n)~
Đặt P là tổng số chữ cái của A[2] đến A[i]. Vòng i chỉ cần cộng thêm các câu cố định, A[1], chữ "and" (khi i > 1) và P. Đáp số có thể lên tới ~10^{11}~ nên dùng long long. Đúng 10/10 test.
Chương trình hoàn chỉnh
main đọc n và các cụm từ, đếm chữ cái. Nếu ~n \le 5000~ thì gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long L[100005]; // L[i] = so chu cai cua cum tu A[i]
long long TOP, FIX, ANDC; // TOP: 2 cau hat truoc vong lap; FIX: 2 cau trong vong lap; ANDC: chu cai cua "and"
// Dem so chu cai (a-z, A-Z) trong xau s
long long cnt(const string& s) {
long long c = 0;
for (char ch : s) if (isalpha((unsigned char)ch)) c++;
return c;
}
// Sub 1: vet can O(n^2) - mo phong dung vong lap, dung khi n <= 5000
void sub1() {
long long ans = TOP;
for (int i = 1; i <= n; i++) {
ans += FIX + L[1]; // "Hat A[1]" va cac cau co dinh
if (i > 1) ans += ANDC; // "Hat and"
for (int j = i; j >= 2; j--) // for j tu i den 2: hat A[j]
ans += L[j];
}
cout << ans << "\n";
}
// Sub 2: dung tong cong don (prefix sum) O(n) - dung cho n lon
void sub2() {
long long ans = TOP, P = 0; // P = L[2] + ... + L[i]
for (int i = 1; i <= n; i++) {
if (i >= 2) P += L[i];
ans += FIX + L[1] + (i > 1 ? ANDC : 0) + P;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
string line;
getline(cin, line); // bo phan con lai cua dong n
for (int i = 1; i <= n; i++) {
getline(cin, line);
L[i] = cnt(line);
}
TOP = cnt("Look at the animals, dancing, dancing,") + cnt("Look at the animals, dancing to the music.");
FIX = cnt("dancing, dancing,") + cnt("Look at the animals, dancing to the music.");
ANDC = cnt("and");
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận