Hướng dẫn giải của Khối lượng phân tử
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , ,
Editorial for stmass: Khối lượng phân tử
Hiểu bài toán
Bài toán yêu cầu tính khối lượng phân tử của một hợp chất hữu cơ dựa trên công thức phân tử được biểu diễn dưới dạng chuỗi ký tự. Khối lượng nguyên tử của các nguyên tố là C=12, H=1, O=16. Công thức có thể chứa các nhóm được đặt trong dấu ngoặc đơn và có thể đi kèm số lặp (2-9) ngay sau đó. Ví dụ: (CO2H)3 có nghĩa là khối CO2H được lặp 3 lần. Chuỗi công thức có thể lồng nhau nhiều cấp.
Mục tiêu: Đọc chuỗi, tính tổng khối lượng của tất cả các nguyên tố, áp dụng số lặp cho các nhóm trong ngoặc, và trả về kết quả là một số nguyên dương.
Các cách tiếp cận
Cách Sử dụng Stack (Duyệt tuần tự)
#include <stdio.h>
#include <string.h>
int stack[10005];
char s[10005];
int top;
void push(int val) {
stack[++top] = val;
}
int pop() {
return stack[top--];
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%s", s);
top = -1;
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] == 'C') push(12);
else if (s[i] == 'H') push(1);
else if (s[i] == 'O') push(16);
else if (s[i] == '(') push(-1); // Dấu hiệu cho dấu ngoặc mở
else if (s[i] == ')') {
int sum = 0;
// Cộng dồn các giá trị trong nhóm cho tới khi gặp dấu ngoặc mở
while (top != -1 && stack[top] != -1) {
sum += stack[top];
pop();
}
pop(); // Bỏ dấu ngoặc mở (-1)
push(sum); // Đặt tổng của nhóm vào stack
}
else if (s[i] >= '2' && s[i] <= '9') {
int multiplier = s[i] - '0';
int val = pop();
push(val * multiplier);
}
}
int total = 0;
while (top != -1) {
total += stack[top--];
}
printf("%d\n", total);
}
return 0;
}
- Time Complexity: O(N) với N là độ dài chuỗi đầu vào.
- Space Complexity: O(N) (kích thước stack phụ thuộc độ sâu lồng nhau).
Cách tiếp cận này sử dụng Stack để mô phỏng quá trình tính toán.
- Duyệt từng ký tự của chuỗi:
- Nếu là nguyên tố (C, H, O): Đẩy khối lượng tương ứng vào stack.
- Nếu là '(': Đẩy một giá trị đặc biệt (ví dụ -1) vào stack để đánh dấu.
- Nếu là ')': Thực hiện vòng lặp để lấy các giá trị ra khỏi stack cộng dồn lại cho đến khi gặp giá trị đánh dấu '('. Sau đó đẩy tổng của nhóm đó vào lại stack.
- Nếu là số (2-9): Lấy giá trị cuối cùng trong stack (vừa là một nguyên tố hoặc một nhóm đã tính), nhân với số đó và đẩy lại vào stack.
- Sau khi duyệt hết chuỗi, các giá trị còn lại trong stack là các thành phần độc lập (các nguyên tố hoặc các nhóm đã tính xong). Cộng chúng lại để得到 kết quả cuối cùng. Ưu điểm: Logic rõ ràng, xử lý được các trường hợp phức tạp và lồng nhau.
Cách Quy hoạch động / Đệ quy có nhớ (Recursive Parsing)
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
string s;
int idx;
int parse() {
int current_mass = 0;
while (idx < s.length()) {
if (s[idx] == '(') {
idx++;
int group_mass = parse(); // Gọi đệ quy cho nội dung trong ngoặc
// Sau khi return, idx đang ở ký tự ngay sau ngoặc đóng
if (idx < s.length() && isdigit(s[idx])) {
group_mass *= (s[idx] - '0');
idx++;
}
current_mass += group_mass;
} else if (s[idx] == ')') {
idx++; // Bỏ qua dấu ngoặc đóng để trả về
return current_mass;
} else if (isdigit(s[idx])) {
// Xử lý số lặp dính vào nguyên tố trước đó (thường đã xử lý trong phần gọi trước đó)
// Hoặc xử lý nếu số xuất hiện đơn lẻ (theo đề bài là sai cú pháp, nhưng code cần mạnh)
idx++;
} else {
// Là nguyên tố
int val = 0;
if (s[idx] == 'C') val = 12;
else if (s[idx] == 'H') val = 1;
else if (s[idx] == 'O') val = 16;
idx++;
// Kiểm tra số lặp ngay sau nguyên tố
if (idx < s.length() && isdigit(s[idx])) {
val *= (s[idx] - '0');
idx++;
}
current_mass += val;
}
}
return current_mass;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> s;
idx = 0;
cout << parse() << endl;
}
return 0;
}
- Time Complexity: O(N) với N là độ dài chuỗi.
- Space Complexity: O(D) với D là độ sâu đệ quy tối đa.
Sử dụng đệ quy để xử lý cấu trúc phân cấp của công thức.
- Hàm
parse()xử lý một phần của chuỗi và trả về khối lượng của phần đó. - Khi gặp '(': Gọi đệ quy
parse()để tính toán nội dung bên trong. Sau khi nhận kết quả, kiểm tra ký tự tiếp theo có phải là số không để nhân. - Khi gặp ký tự thường (nguyên tố): Tính giá trị, kiểm tra số lặp theo sau và cộng vào tổng của khối hiện tại.
- Khi gặp ')': Dừng vòng lặp và trả về tổng đã tính được cho khối (hoặc phần nội dung) hiện tại.
- Kết quả cuối cùng là giá trị trả về của lần gọi
parse()đầu tiên. Cách này cũng xử lý tốt các trường hợp lồng nhau nhưng đòi hỏi phải quản lý chỉ số chuỗi (index) cẩn thận.
Cách Xử lý chuỗi trực tiếp (Duyệt và tính toán)
#include <stdio.h>
#include <string.h>
long long tinh(char *s, int *i) {
long long sum = 0;
while (s[*i]) {
if (s[*i] == ')') {
(*i)++; // Bỏ qua dấu ngoặc đóng
return sum;
}
if (s[*i] == '(') {
(*i)++;
long long inner = tinh(s, i); // Gọi đệ quy
// Sau khi return, i đang ở số lặp hoặc ký tự tiếp theo
if (s[*i] >= '2' && s[*i] <= '9') {
inner *= (s[*i] - '0');
(*i)++;
}
sum += inner;
continue;
}
long long current = 0;
if (s[*i] == 'C') current = 12;
else if (s[*i] == 'H') current = 1;
else if (s[*i] == 'O') current = 16;
(*i)++;
if (s[*i] >= '2' && s[*i] <= '9') {
current *= (s[*i] - '0');
(*i)++;
}
sum += current;
}
return sum;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
char s[1001];
scanf("%s", s);
int idx = 0;
printf("%lld\n", tinh(s, &idx));
}
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(D)
Đây là biến thể của phương pháp đệ quy, tập trung vào việc xử lý chuỗi trực tiếp bằng con trỏ hoặc chỉ số. Logic tương tự như Approach 2, nhưng được tối ưu hóa để xử lý luồng dữ liệu tuần tự.
- Duyệt chuỗi, khi gặp '(': thực hiện đệ quy để tính giá trị bên trong.
- Khi gặp nguyên tố: đọc giá trị và số nhân theo sau (nếu có).
- Khi gặp ')': kết thúc đệ quy. Phương pháp này hiệu quả về mặt code length và trực quan hóa cấu trúc cây của công thức.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N) với N là độ dài chuỗi đầu vào. | O(N) (kích thước stack phụ thuộc độ sâu lồng nhau). | Sử dụng Stack (Duyệt tuần tự) |
| 2 | O(N) với N là độ dài chuỗi. | O(D) với D là độ sâu đệ quy tối đa. | Quy hoạch động / Đệ quy có nhớ (Recursive Parsing) |
| 3 | O(N) | O(D) | Xử lý chuỗi trực tiếp (Duyệt và tính toán) |
Bài học kinh nghiệm
- Cấu trúc công thức có tính phân cấp rõ ràng (nhóm lồng trong nhóm), điều này gợi ý việc sử dụng Stack (LIFO) hoặc Đệ quy (Recursive).
- Số lặp (2-9) luôn đi liền sau một đơn vị (nguyên tố hoặc một nhóm đã được đóng dấu ngoặc), nên ta có thể nhân ngay khi gặp số đó.
- Đề bài giới hạn độ dài 1000, nên giải thuật O(N) là hoàn toàn đủ.
Lỗi thường gặp
- Bỏ qua các số lặp có thể xuất hiện ở nhiều cấp độ (ví dụ: (C2H5)3).
- Xử lý sai thứ tự tính toán trong Stack (phải cộng dồn các phần tử bên trong ngoặc trước khi nhân với số lặp).
- Quên xử lý các ký tự không phải là số, C, H, O, ngoặc (trong khi input khá chuẩn, nhưng code nên mạnh mẽ).
Bình luận