化学方程式配平

GitHub跳转原题关系图 Canvas 关系图返回列表

解析每种物质的元素计数，建立元素-物质矩阵并用高斯消元判断其秩是否小于未知数个数。

OJ: shumeng

题目 ID: CSP202403C

难度:普及+/提高-

标签:字符串解析线性代数高斯消元

日期: 2026-07-31 16:21

形式化题目

给定 $m$ 种物质的化学式（已去掉括号，只含连续小写字母元素名和其后数字），把每种物质看作方程同一侧的未知系数，判断对应的齐次线性方程组

AX = 0

是否存在非零解。存在则输出 Y，否则输出 N。

其中 $A$ 是元素-物质计数矩阵， $A[i][j]$ 表示第 $j$ 种物质中元素 $i$ 的原子个数。

思路

问题的数学本质： $AX = 0$ 有非零解当且仅当 $\operatorname{rank}(A) < m$ （未知数个数）。所以核心工作只有两步：把化学式转成矩阵，再求矩阵的秩。

解析化学式

化学式只含连续小写字母和数字，例如 al2s3o12 表示 al 有 2 个、s 有 3 个、o 有 12 个。从左到右扫描：读出一串小写字母得到元素名，再读出一串数字得到原子个数，存入 map<元素, 个数>。

构造矩阵

每种出现的元素对应一行，每种物质对应一列。用 map<string, int> 给元素分配行号，把每种物质的原子个数填入对应行列。

高斯消元求秩

对矩阵做列主元高斯消元：每一列找一个绝对值最大的非零元素作主元，换到当前行并用它消去下方各行；找不到非零主元的列跳过。消元后非零行数就是矩阵的秩。

判断标准：秩小于物质个数 $m$ 时方程组有自由变量，存在非零解，输出 Y。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50;

int substance_count;          // 一个方程中物质的个数（矩阵列数）
int element_count;            // 一个方程中出现的元素种类数（矩阵行数）
map<string, int> element_id;  // 元素名称 -> 矩阵行号
long double matrix[MAXN][MAXN]; // matrix[i][j]：第 j 个物质中含元素 i 的原子个数

// 解析化学式：连续小写字母为元素名，其后紧跟的数字为该元素的原子个数
map<string, int> parse_formula(const string &formula) {
    map<string, int> result;
    int position = 0;
    while (position < (int)formula.size()) {
        string element;
        while (position < (int)formula.size()
                && 'a' <= formula[position] && formula[position] <= 'z') {
            element += formula[position++];
        }
        int number = 0;
        while (position < (int)formula.size()
                && '0' <= formula[position] && formula[position] <= '9') {
            number = number * 10 + formula[position++] - '0';
        }
        result[element] = number;
    }
    return result;
}

// 读入一个方程的各个物质，构造元素-物质计数矩阵
void read_equation() {
    cin >> substance_count;
    element_id.clear();
    memset(matrix, 0, sizeof(matrix));

    for (int column = 0; column < substance_count; column++) {
        string formula;
        cin >> formula;
        map<string, int> counts = parse_formula(formula);
        for (map<string, int>::iterator it = counts.begin(); it != counts.end(); ++it) {
            int row;
            if (element_id.count(it->first)) {
                row = element_id[it->first];
            } else {
                row = (int)element_id.size();
                element_id[it->first] = row;
            }
            matrix[row][column] = it->second;
        }
    }
    element_count = (int)element_id.size();
}

// 高斯消元（列主元）求矩阵的秩，返回非零行数
int matrix_rank() {
    int rank = 0;
    for (int column = 0; column < substance_count && rank < element_count; column++) {
        // 在当前列选择绝对值最大的行作为主元，提高数值稳定性
        int pivot = rank;
        for (int row = rank + 1; row < element_count; row++) {
            if (fabsl(matrix[row][column]) > fabsl(matrix[pivot][column])) pivot = row;
        }
        // 主元为 0 说明该列已是自由列，直接跳过
        if (fabsl(matrix[pivot][column]) < 1e-12L) continue;

        // 把主元行换到当前行
        for (int j = column; j < substance_count; j++) {
            swap(matrix[pivot][j], matrix[rank][j]);
        }
        // 用当前行消去下面各行的当前列
        for (int row = rank + 1; row < element_count; row++) {
            if (fabsl(matrix[row][column]) < 1e-12L) continue;
            long double ratio = matrix[row][column] / matrix[rank][column];
            for (int j = column; j < substance_count; j++) {
                matrix[row][j] -= ratio * matrix[rank][j];
            }
        }
        rank++;
    }
    return rank;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int equation_count;
    cin >> equation_count;
    while (equation_count--) {
        read_equation();
        // 齐次方程组 AX=0 有非零解当且仅当矩阵秩小于未知数个数
        cout << (matrix_rank() < substance_count ? 'Y' : 'N') << '\n';
    }

    return 0;
}

复杂度

设一个方程中物质个数为 $m$ ，涉及的元素种类数为 $e$ （ $m, e \le 40$ ）。

时间：解析每个化学式为 $O(\text{公式长度})$ ；高斯消元 $O(e \cdot m \cdot \min(e, m))$ 。
空间：元素-物质矩阵大小为 $e \times m$ ，空间复杂度 $O(em)$ 。

总结

这道题把化学背景完全剥离后就是一个线性代数问题：判断齐次方程组是否存在非零解等价于比较矩阵秩与未知数个数。难点在于把化学式干净地转成计数矩阵，以及数值消元时选择绝对值最大的主元来保证精度。

题目来自第 33 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

近日来，西西艾弗岛化学研究中心的研究员们向岛上的初中学生开展了化学科普活动。在活动中发现，初学化学的同学们十分苦恼于正确配平化学方程式。而还有一些同学，则提出了一些稀奇古怪的方程式，让研究员们帮忙配平。在配平之前，研究员们需要先判断这个方程式是否能够配平。

一个化学方程式，也叫化学反应方程式，是用化学式表示化学反应的式子。其等号左右两侧分别列举了化学反应的全部反应物和生成物。每种物质都用其化学式表示。一个物质的化学式，列举了构成该物质的各元素的原子数目。例如，水的化学式是 $\text{H}_2\text{O}$ ，表示水分子中含有两个氢原子和一个氧原子。化学方程式中每种物质的化学式前面都有一个系数，表示参与反应或生成的物质的相对数目比例。例如，方程式 $2\text{H}_2 + \text{O}_2 = 2\text{H}_2\text{O}$ 表示二分子氢气和一分子氧气反应生成二分子水。我们称一个化学方程式是配平的，是指该方程式中的反应物和生成物中，各元素原子总数目相等。例如上述方程式中，左侧氢原子、氧原子的总数目分别为 $4$ 和 $2$ ，右侧氢原子、氧原子的总数目分别为 $4$ 和 $2$ ，因此该方程式是配平的。

题目描述

为了配平一个化学方程式，我们可以令方程式中各物质的系数为未知数，然后针对涉及的每一种元素，列出关于系数的方程，形成一个齐次线性方程组。然后求解这个方程组，得到各物质的系数。这样，我们就把化学方程式配平的问题，转化为了求解齐次线性方程组的问题。如果方程组没有非零解，那么这个方程式是不可以配平的。反之，如果方程组有非零解，我们就可能得到一个配平的方程式。当然，最终得到的方程式仍然需要结合化学知识进行检验，对此我们不再进一步考虑，仅考虑非零解的存在。

例如要配平化学方程式： $\text{Al}_2(\text{S}\text{O}_4)_3 + \text{N}\text{H}_3\cdot\text{H}_2\text{O} \rightarrow \text{Al}(\text{O}\text{H})_3 + (\text{N}\text{H}_4)_2\text{S}\text{O}_4$

首先假定所有物质在方程的同一侧，即不考虑哪个是反应物，哪个是生成物，分别设这些物质的系数为 $x_1, x_2, x_3, x_4$ ，则可以针对出现的各个元素，列出如下的方程组：

\begin{align} 2x_1 + 0x_2 + x_3 + 0x_4 &= 0 && \text{Al} \\ 3x_1 + 0x_2 + 0x_3 + x_4 &= 0 && \text{S} \\ 12x_1 + x_2 + 3x_3 + 4x_4 &=0 && \text{O} \\ 0x_1 + x_2 + 0x_3 + 2x_4 &=0 && \text{N} \\ 0x_1 + 5x_2 + 3x_3 + 8x_4 &=0 && \text{H} \\ \end{align}

用矩阵的形式表示为：

\begin{pmatrix} 2 & 0 & 1 & 0 \\ 3 & 0 & 0 & 1 \\ 12 & 1 & 3 & 4 \\ 0 & 1 & 0 & 2 \\ 0 & 5 & 3 & 8 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \mathbf{0}

对系数矩阵实施高斯消元，得到系数矩阵的一个行阶梯形式：

\begin{pmatrix} 2 & 0 & 1 & 0 \\ 0 & 1 & -3 & 4 \\ 0 & 0 & -{3\over2} & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}

由此可见，系数矩阵的秩为 3。根据线性代数的知识，我们知道，齐次线性方程组 $\mathbf{A}\mathbf{X} = \mathbf{0}$ 的解空间的维数等于其未知数个数减去系数矩阵的秩 $\text{rank} (\mathbf{A})$ 。而要让方程式配平，即要求方程组存在非零解，那么就需要让解空间的维数大于 $0$ ，即系数矩阵的秩小于未知数个数。因此，我们可以通过判断系数矩阵的秩是否小于未知数个数，来判断方程式是否可以配平。如果可以配平，则可以通过解的符号来判断反应物和生成物的位置。

本题中，我们将给出一些化学方程式，请你按照上述方法判断它们是否可以配平。为了便于程序处理，我们用到的化学式，会被化简为只包含小写字母和数字的字符串，不包含括号。其中连续的字母表示一种元素，随后的数字表示原子个数。原子个数为 1 时不省略数字；一个化学式中包含的元素不重复。例如，上述方程式中的化学式可以化简为 al2s3o12、n1h5o1、al1o3h3、n2h8s1o4。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$ ，表示需要判断的化学方程式的个数。

接下来的 $n$ 行，每行描述了一个需要被配平的化学方程式。包含空格分隔的一个正整数和全部涉及物质的化学式。其中，正整数 $m$ 表示方程式中的物质；随后的 $m$ 个字符串，依次给出方程式中的反应物的化学式和生成物的化学式。

输出格式

输出到标准输出。

输出包含 $n$ 行，每行包含字母 Y 或 N，表示按题设方法，所给待配平化学方程式能否配平。

input1

1
2
3
4
5
6
76
2 o2 o3
3 c1o1 c1o2 o2
2 n2o4 n1o2
4 cu1 h1n1o3 cu1n2o6 h2o1
4 al2s3o12 n1h5o1 al1o3h3 n2h8s1o4
4 c1o1 c1o2 o2 h2o1

output1

1
2
3
4
5
6Y
Y
Y
N
Y
Y

样例 1 解释

输入中给出了 5 个待配平的化学方程式，其中各方程式的配平情况为：

$3\text{O}_2 = 2\text{O}_3$
$2\text{C}\text{O} + \text{O}_2 = 2\text{C}\text{O}_2$
$\text{N}_2\text{O}_4 = 2\text{N}\text{O}_2$
因为缺少生成物 $\text{N}\text{O}$ 或 $\text{N}\text{O}_2$ ，所以不可以配平
$\text{Al}_2(\text{S}\text{O}_4)_3 + 6\text{N}\text{H}_3\cdot\text{H}_2\text{O} = 2\text{Al}(\text{O}\text{H})_3 + 3(\text{N}\text{H}_4)_2\text{S}\text{O}_4$
$2\text{C}\text{O} + \text{O}_2 = 2\text{C}\text{O}_2$ ，本方程式对应的线性方程组求解后，得到 $\text{H}_2\text{O}$ 的系数为 0，说明其未参与反应，属多余的物质。在这种情况下，由于对应的线性方程组存在非零解，所以我们仍然认为这个方程式是可以配平的。

子任务

对于 $20\%$ 的数据，每个方程中物质的个数不超过 $2$ ，每个方程中涉及的全部元素不超过 $2$ 种；

对于 $60\%$ 的数据，每个方程中物质的个数不超过 $3$ ，每个方程中涉及的全部元素不超过 $3$ 种；

对于 $100\%$ 的数据，每个方程中物质的个数不超过 $40$ ，每个方程中涉及的全部元素不超过 $40$ 种；且有 $1 \leq n \leq 10$ ，且化学式中各元素的原子个数不超过 $50$ 。

提示

对矩阵进行高斯消元的一种方法是：
1. 考察矩阵的第一列上的元素：
  - 若全都为零，则对除去该列的子矩阵重复上述判断；
  - 若不全为零，则：
    1. 考察第一行第一列的元素：
      - 如果其为 0，则将该行与后面的某一个第一列非 0 的行交换，使第一行第一列的元素非 0；
    2. 令后续所有行减去第一行的适当倍数，使得后续所有行的第一列元素为 0；
2. 对除去第一行第一列的子矩阵重复上述操作，直至不再余下子矩阵。
对系数矩阵高斯消元后，不全为 0 的行的数目即为系数矩阵的秩。
评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库。