LTC_1A - Nén xâu
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, JavaScript, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Để tiết kiệm bộ nhớ khi lưu trữ, người ta thường sử dụng các thuật toán nén trước khi lưu và tiến hành giải nén trước khi sử dụng. Đối với văn bản, có một thuật toán gọi là "Run-Length Encoding".
- Ví dụ xâu "aaabcccc" sẽ được mã hoá thành "a3b1c4"
Xem hình dưới đây để hiểu rõ hơn về thuật toán này:
Hiếu mới được mẹ mua cho 1 con Macbook Pro M2 có dung lượng 1TB SSD. Tuy nhiên, cậu cảm thấy việc lưu tài liệu mà không nén sẽ có thể sẽ khiến máy tính phải tiêu thụ nhiều năng lượng hơn. Do đó, bạn hãy giúp Hiếu viết 1 chương trình cho phép nén các chuỗi của bạn ấy theo thuật toán "Run-Length Encoding" nhé.
Input
- Dòng đầu tiên là số nguyên ~T~, là Số lượng chuỗi Hiếu cần bạn giúp
- T dòng tiếp theo, mỗi dòng là một chuỗi ký tự ~S~
Output
- In ra ~T~ dòng, mỗi dòng là chuỗi đã mã hoá tương ứng.
Sample
Input #1
2
a
aaabcccc
Output #1
a1
a3b1c4
Giới hạn
- ~0 < T \le 20~
- Các chuỗi cần mã hoá ~S~ có độ dài không quá ~1000~ và chỉ bao gồm các chữ cái ~a-z~ trong bảng chữ cái tiếng Anh.
Bình luận
int main() { int t; cin>>t; cin.ignore(); while(t--){ int cnt[256] = {0}; string s; getline(cin, s); for(int i = 0; i < s.size(); i++) { cnt[s[i]]++; } for(int i = 0; i < 256; i++) { if(cnt[i] != 0) { cout << char(i) << cnt[i]; } } cout << endl; } return 0; }
gius e voi, ko biet em sai cai gi
Thử trường hợp aabca chưa bạn?