P4029 [Code+#2] 化学狂暴 题解

这个题题面很长，非常考验读题能力。但只要读懂了，做起来还是比较简单的。

1. 题意概括

这道题其实就是给出 $n$ 个缺了一些元素的化学方程式，让我们补全，如果无解，就输出 No Solution。

2. 思路分析

首先，我们先定义两个数组 $a,b$。其中 $a_i$ 表示 = 左边的元素 $i$ 下标的总个数，$b_j$ 表示 = 右边的元素 $j$ 下标的总个数。

然后，我们输入化学方程式（$m$ 其实并不重要）。对于每个方程式，遍历方程式的每一个字符，如果是 ?，就记录下它在等号的左边还是右边。对于每个元素，判断每一个元素的后面是不是数字，如果不是数字，那么表示这个元素是“单一元素”且下标被省略，直接加一即可，否则加上这个元素后的那个数字。

接着，我们分两种情况：

1. 如果 ? 在 = 的右边，? 中元素 $i$ 的下标就等于左减右，即 $a_i-b_i$，如果下标为 $1$，要将其下标省略。

2. 如果 ? 在 = 的左边，? 中元素 $i$ 的下标就等于右减左，即 $b_i-a_i$，如果下标为 $1$，要将其下标省略。

最后，我们判断是否无解。当 ? 中的元素有下标为负数时，无解；当 ? 表示的物质超出钦钦草原世界化学学科的研究范围时，无解；如果 ? 没有表示的物质，也无解。对于无解的情况，输出 No Solution，否则，输出 ? 表示的物质。

3. AC 代码

AC 记录。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[31], b[31];  // a[i] 用来存储 = 左边的元素 i 下标的总个数，b[i] 用来存储 = 右边的元素 i 下标的总个数
string f(string s, int x){  
	bool l = 1;  // l = 1 表示当前在 = 左边，l = 0 表示当前在 = 右边
	int w = 0;  // w 表示 ? 在 = 哪一边
	for (int i = 0; i < s.size(); i++) {
		if (s[i] <= 'Z' && s[i] >= 'A') {
			if (s[i + 1] >= '0' && s[i + 1] <= '9') {  // 判断元素后有没有下标，如果有下标就元素下标的总个数加上元素后的下标
				if (l) {
					a[s[i] - 'A'] += s[i + 1] - '0';
				} else {
					b[s[i] - 'A'] += s[i + 1] - '0';
				}
			} else {  // 如果没有下标，就代表这个元素的下标省略了，直接加一即可
				if (l) {
					a[s[i] - 'A']++;
				} else {
					b[s[i] - 'A']++;
				}
			}
		}
		if (s[i] == '=') {  // 如果是 =，后面的数就在 = 右边，所以 l = 0
			l = 0;
		}
		if (s[i] == '?') {  // 如果是 ?，存储它在 = 的哪一边
			w = (l ? 1 : 0);
		}
	}
	if (w == 0) {  // 如果 ? 在 = 的右边
		for (int i = 0; i <= 26; i++) {
			if (a[i] < b[i]) return "No Solution";  // 当 = 右边的某个元素大于 = 左边同样的某个元素时，无解！
		}
		string tt = "";
		for (int i = 0; i <= 26; i++) {
			if (a[i] - b[i] > 9) return "No Solution";  // 当 ? 表示的物质超出钦钦草原世界化学学科的研究范围时，也无解
			else if (a[i] - b[i] > 0) {
				tt += (char)(i + 'A');
				if (a[i] - b[i] > 1) {
					tt += (char)(a[i] - b[i] + '0');
				}
			}
		}
		if (tt == "") return "No Solution";  // 如果 ? 没有表示的物质，那么无解
		return tt;
	} else {  // 如果 ? 在 = 的左边
		for (int i = 0; i <= 26; i++) {
			if (a[i] > b[i]) return "No Solution";  // 同上
		}
		string tt = "";
		for (int i = 0; i <= 26; i++) {
			if (b[i] - a[i] > 9) return "No Solution";
			else if (b[i] - a[i] > 0) {
				tt += (char)(i + 'A');
				if (b[i] - a[i] > 1) {
					tt += (char)(b[i] - a[i] + '0');
				}
			}
		}
		if (tt == "") return "No Solution";
		return tt;
	}
}
signed main(){
	int n, m;
	cin >> n >> m;
	while (n--) {
		memset(a, 0, sizeof(a));  // 初始化
		memset(b, 0, sizeof(b));
		string s;
		cin >> s;
		cout << f(s, m) << endl;
	}
	return 0;
}