CCF-CSP认证考试 202403-3 化学方程式配平 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202403-3 化学方程式配平

时间限制： 1.0 秒
空间限制： 512 MiB

题目背景

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

一个化学方程式，也叫化学反应方程式，是用化学式表示化学反应的式子。其等号左右两侧分别列举了化学反应的全部反应物和生成物。 每种物质都用其化学式表示。一个物质的化学式，列举了构成该物质的各元素的原子数目。例如，水的化学式是 ${\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}\to \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{array}{rlrl}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{array}$$
用矩阵的形式表示为：

$$\left(\begin{array}{cccc}2& 0& 1& 0\\ 3& 0& 0& 1\\ 12& 1& 3& 4\\ 0& 1& 0& 2\\ 0& 5& 3& 8\end{array}\right)\cdot \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right)=0$$

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

$$\left(\begin{array}{cccc}2& 0& 1& 0\\ 0& 1& -3& 4\\ 0& 0& -\frac{3}{2}& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)$$

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

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

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

样例1输入

6
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

样例1输出

Y
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\le n\le 10$，且化学式中各元素的原子个数不超过 $50$。

提示

• 对矩阵进行高斯消元的一种方法是：

  1. 考察矩阵的第一列上的元素：
     • 若全都为零，则对除去该列的子矩阵重复上述判断；
     • 若不全为零，则：
       1. 考察第一行第一列的元素：
          • 如果其为 0，则将该行与后面的某一个第一列非 0 的行交换，使第一行第一列的元素非 0；
       2. 令后续所有行减去第一行的适当倍数，使得后续所有行的第一列元素为 0；
  2. 对除去第一行第一列的子矩阵重复上述操作，直至不再余下子矩阵。

• 对系数矩阵高斯消元后，不全为 0 的行的数目即为系数矩阵的秩。

• 评测环境仅提供各语言的标准库，特别地，不提供任何线性代数库。

题解

先将每个物质的各个元素拆分开来。可以观察到每个物质的化学式中，都是按照元素和对应元素的个数的排列顺序，而元素都是英文字母，元素个数都是数字。

这样子可以先将元素与元素之间区分开来（即如果当前位为数字，下一位为字母，那么这两位之间必定是元素的分界线），然后再将元素名称和元素个数区分开来（对于区分好的元素，如果当前位为字母，下一位为数字，那么这两位之间必定是元素和个数的分界线）。

对于每个元素，可以使用 std::map 来为其设定编号（在系数矩阵中的行数，即对应题目中的第几个方程）。对于第 $i$ 个物质中，元素编号为 $j$ 的元素，将其个数存储在系数矩阵的第 $j$ 行第 $i$ 列。

系数矩阵构造完后，使用高斯消元的方法来求解行列式的秩，高斯消元的具体过程在提示中已经给出。

求出系数矩阵的秩后，判断秩 rank 和未知数个数（所涉及物质的数量）m 的关系，如果 rank < m，则化学方程式可以配平，输出 Y；否则，化学方程式无法配平，输出 N。

时间复杂度：$\mathcal{O}(n\cdot 40^3)$。

参考代码

/*
    Created by Pujx on 2024/5/8.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int _ = 1; _ <= n; _++) cin >> a[_]
#define cinstl(a) for (auto& _ : a) cin >> _
#define coutarr(a, n) for (int _ = 1; _ <= n; _++) cout << a[_] << " \n"[_ == n]
#define coutstl(a) for (const auto& _ : a) cout << _ << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#define eps 1e-8
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 50 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

double a[N][N];
int n, m, t, k, q;

int gauss(int n, int m) {
    int rnk = 0;
    for (int i = 1; i <= n; i++) {
        int t = rnk + 1;
        for (int j = rnk + 1; j <= n; j++) 
            if (a[j][i]) { t = j; break; }
        if (fabs(a[t][i]) < eps) continue;
        ++rnk;
        for (int j = i; j <= m; j++) swap(a[t][j], a[rnk][j]);
        for (int j = m; j >= i; j--) a[rnk][j] /= a[rnk][i];
        for (int j = rnk + 1; j <= n; j++)
            if (fabs(a[j][i]) > eps)
                for (int k = m; k >= i; k--)
                    a[j][k] -= a[rnk][k] * a[j][i];
    }
    return rnk;
}

void work() {
    cin >> n;
    vector<string> s(n);
    for (auto& ss : s) cin >> ss; 
    map<string, int> mp;
    int cnt = 0;
    memset(a, 0, sizeof(a));
    
    for (int i = 0; i < n; i++) {
        auto& ss = s[i];
        for (int l = 0, r = 0; l < ss.length(); r = l = r + 1) {
            auto isNum = [&] (char c) -> bool { return c >= '0' && c <= '9'; };
            while (r + 1 < ss.length() && !(isNum(ss[r]) && !isNum(ss[r + 1]))) r++;
            string cur = ss.substr(l, r - l + 1), elem;
            for (auto ch : cur) if (!isNum(ch)) elem += ch;
            int num = stoi(cur.substr(elem.length()));            
            int elemid = mp.count(elem) ? mp[elem] : (mp[elem] = ++cnt);
            a[elemid][i + 1] = num;
        }
    }
    int rnk = gauss(cnt, n);
    cout << "NY"[rnk < n] << endl;
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
4. "debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
5. ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。