Hướng dẫn giải của Kim tự tháp (đề HSG 9 Phú Thọ 2015-2016)
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 gồm chữ cái in hoa, số tầng k và ký tự c. Kim tự tháp được điền các ký tự của S lặp vòng từ trái sang phải, tầng thứ i có i ô. Cần đếm số lần c xuất hiện ở tầng k. Đề dùng file KTT.INP và KTT.OUT.
Sub 1: Duyệt trực tiếp các ô của tầng k — ~O(k)~, dùng khi ~k \le 10^5~
Tầng k gồm các ô có thứ tự từ k(k-1)/2 + 1 đến k(k+1)/2. Ô thứ p nhận ký tự S[(p-1) mod |S|]. Duyệt đủ k ô và đếm.
Nếu chỉ nộp sub này: đúng 18/20 test (các test k lớn bị quá giờ).
Sub 2: Công thức theo chu kỳ — ~O(|S|)~
Đếm số lần c trong các vị trí [0, x) bằng cách: số chu kỳ đầy đủ nhân số lần c trong một chu kỳ, cộng phần lẻ. Đáp số là hàm đếm tại k(k+1)/2 trừ đi tại k(k-1)/2. Bẫy: k(k+1)/2 có thể đến khoảng 5·10^17, dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc S, k, c từ KTT.INP. Nếu k <= 10^5 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
string S;
long long k;
char c;
int m; // do dai S
// Sub 1: duyet truc tiep cac o cua tang k. Tang k gom cac o thu tu k(k-1)/2+1 .. k(k+1)/2,
// o thu p duoc dien ky tu S[(p-1) mod m]. Dung khi k <= 10^5.
void sub1() {
long long start = k * (k - 1) / 2; // so o truoc tang k (0-based)
long long cnt = 0;
for (long long j = start; j < start + k; j++)
if (S[j % m] == c) cnt++;
cout << cnt << "\n";
}
// Sub 2: dem so lan c trong tien to dai x theo chu ky m — O(m)
long long countPrefix(long long x) { // so o trong [0, x) co ky tu c
long long cntc = 0;
for (char ch : S) if (ch == c) cntc++;
long long full = x / m, rem = x % m;
long long res = full * cntc;
for (long long i = 0; i < rem; i++)
if (S[i] == c) res++;
return res;
}
void sub2() {
long long lo = k * (k - 1) / 2;
long long hi = k * (k + 1) / 2;
cout << countPrefix(hi) - countPrefix(lo) << "\n";
}
int main() {
freopen("KTT.INP", "r", stdin);
freopen("KTT.OUT", "w", stdout);
cin >> S >> k >> c;
m = (int)S.size();
if (k <= 100000) sub1();
else sub2();
return 0;
}
Bình luận