A25066. 化学反应式
题目描述
化学反应式
题目描述
“化学反应式”是用元素符号表示化学反应的一种等式，等式左边给出参与反应的元素，右边给出反应的结果。例如 CH4+2O2= CO2+ 2H2O 的意思是，参与反应的元素是甲烷和氧气，即 CH4和 O2，反应结果产生二氧化碳和水，即 CO2和 H2O。
现给定一些反应元素和结果，请你编写程序推出我们怎样才能得到这些结果。注意每种反应元素只能被用一次。为简单起见，我们将等式右边的所有元素都当成是一个结果。
输入
每个输入包含一个测试用例。每个测试用例先给出一个整数 N（2 ≤ N ≤ 20），随后给出 N 个不同的反应元素的编号。
第二行给出一个整数 M（1 ≤ M ≤ 10），随后给出 M 个不同的结果编号。所有编号都是一个 2 位数字。
随后给出正整数 K（≤ 50），接下来 K 行，每行给出一个化学反应式，格式为： reactant_1 + reactant_2 + ... + reactant_n -> product 其中所有的反应元素（reactant）编号都是不同的，并且按升序排列。
注意：题目保证以下规则
（1）一套反应元素不会产生多个不同的结果，即诸如 01 + 02 -> 03 且 01 + 02 -> 04 这种情况保证不会出现；
（2）一个反应元素不会同时还是等式右边的结果元素，除非等式左边只有这一个元素。例如 01 -> 01 总是成立的（无论这个等式是否给出），但 01 + 02 -> 01 是不可能的；
（3）对于列出的等式中的每个结果，得到它的反应方法不会超过 5 种。
输出
输出用给定的反应元素产生所有给定结果的化学反应式。注意每种反应元素只能被用一次。 每个反应式占一行，格式与输入格式相同。顺序必须与输入中的结果编号顺序一致。
对顺序产生的每个结果，如果反应方法不唯一，输出反应元素的最小序列 —— 序列 { a1, … , am} 比 { b1, … , bn} 小的意思是：存在 1 ≤ i ≤ min(m, n) 使得 aj= bj对所有 j < i 成立，且有 ai< bi。 题目保证至少存在一个解。
样例输入
8 09 05 03 04 02 01 16 10
3 08 03 04
6
03 + 09 -> 08
02 + 08 -> 04
02 + 04 -> 03
01 + 05 -> 03
01 + 09 + 16 -> 03
02 + 03 + 05 -> 08样例输出
02 + 03 + 05 -> 08
01 + 09 + 16 -> 03
04 -> 04参考答案
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct Reaction {
vector<int> reactants;
int product;
};
int main() {
int N, M, K;
cin >> N;
vector<int> reactants(N);
for (int i = 0; i < N; ++i) {
cin >> reactants[i];
}
cin >> M;
vector<int> products(M);
for (int i = 0; i < M; ++i) {
cin >> products[i];
}
cin >> K;
vector<Reaction> reactions(K);
for (int i = 0; i < K; ++i) {
string s;
while (cin >> s && s != "->") {
if (s != "+") {
reactions[i].reactants.push_back(stoi(s));
}
}
cin >> reactions[i].product;
}
vector<bool> used(100, false); // 记录反应元素是否被使用
vector<vector<int>> resultReactions(M);
for (int i = 0; i < M; ++i) {
int targetProduct = products[i];
vector<vector<int>> candidates;
for (const auto& reaction : reactions) {
if (reaction.product == targetProduct) {
bool canUse = true;
for (int reactant : reaction.reactants) {
if (used[reactant]) {
canUse = false;
break;
}
}
if (canUse) {
candidates.push_back(reaction.reactants);
}
}
}
if (!candidates.empty()) {
sort(candidates.begin(), candidates.end());
for (int reactant : candidates[0]) {
used[reactant] = true;
}
resultReactions[i] = candidates[0];
}
}
for (int i = 0; i < M; ++i) {
for (size_t j = 0; j < resultReactions[i].size(); ++j) {
if (j != 0) cout << " + ";
cout << resultReactions[i][j];
}
cout << " -> " << products[i] << endl;
}
return 0;
}