Hướng dẫn giải của Khối lượng phân tử


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.

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ập

Tác giả: Hiếu Nguyễn, phongpcbyl, nquang2909

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.

  1. 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.
  2. 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.

  1. Hàm parse() xử lý một phần của chuỗi và trả về khối lượng của phần đó.
  2. 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.
  3. 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.
  4. 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.
  5. 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

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.