首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#13156

化学反应式 “化学反应式”是用元素符号表示化学反应的一种等式,等式左边给出参与反应的元素,右边给出反应的结果。例如 CH 4 +2O 2 = CO 2 + 2H…

化学反应式

“化学反应式”是用元素符号表示化学反应的一种等式,等式左边给出参与反应的元素,右边给出反应的结果。例如 CH4+2O2= CO2+ 2H2O 的意思是,参与反应的元素是甲烷和氧气,即 CH4和 O2,反应结果产生二氧化碳和水,即 CO2和 H2O。

现给定一些反应元素和结果,请你编写程序推出我们怎样才能得到这些结果。注意每种反应元素只能被用一次。为简单起见,我们将等式右边的所有元素都当成是一个结果。

时间限制:6000,内存限制:65536

输入

每个输入包含一个测试用例。每个测试用例先给出一个整数 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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;set&gt; #include &lt;map&gt; #include &lt;algorithm&gt; #include &lt;sstream&gt; #include &lt;cctype&gt; using namespace std; // 去除字符串前后空格 void trim(string &amp;str) {     if (str.empty()) return;     size_t first = str.find_first_not_of(' ');     size_t last = str.find_last_not_of(' ');     if (first == string::npos) {         str = "";         return;     }     str = str.substr(first, (last - first + 1)); } // 反应式结构体 struct Reaction {     vector&lt;string&gt; reactants; // 反应物列表     string prod;              // 产物     string raw;               // 原始字符串     Reaction(const string&amp; s) : raw(s) {         size_t pos = s.find(" -&gt; ");         if (pos == string::npos) {             return;         }         string leftStr = s.substr(0, pos);         string rightStr = s.substr(pos + 4);         trim(rightStr);         prod = rightStr;         // 解析反应物         stringstream ss(leftStr);         string token;         while (getline(ss, token, '+')) {             trim(token);             if (!token.empty()) {                 reactants.push_back(token);             }         }     } }; int main() {     int n;     cin &gt;&gt; n;     vector&lt;string&gt; initVec;     set&lt;string&gt; availableSet;     for (int i = 0; i &lt; n; i++) {         string x;         cin &gt;&gt; x;         initVec.push_back(x);         availableSet.insert(x);     }     int m;     cin &gt;&gt; m;     vector&lt;string&gt; targets;     set&lt;string&gt; targetSet;     for (int i = 0; i &lt; m; i++) {         string x;         cin &gt;&gt; x;         targets.push_back(x);         targetSet.insert(x);     }     int k;     cin &gt;&gt; k;     cin.ignore(); // 忽略换行符     map&lt;string, vector&lt;Reaction&gt;&gt; reactionsMap;     for (int i = 0; i &lt; k; i++) {         string s;         getline(cin, s);         Reaction reac(s);         if (targetSet.count(reac.prod)) {             reactionsMap[reac.prod].push_back(reac);         }     }     for (string target : targets) {         if (availableSet.find(target) != availableSet.end()) {             cout &lt;&lt; target &lt;&lt; " -&gt; " &lt;&lt; target &lt;&lt; endl;             availableSet.erase(target);         } else {             vector&lt;Reaction&gt;&amp; candidates = reactionsMap[target];             vector&lt;Reaction&gt; validReactions;             for (Reaction&amp; reac : candidates) {                 bool valid = true;                 for (string r : reac.reactants) {                     if (availableSet.find(r) == availableSet.end()) {                         valid = false;                         break;                     }                 }                 if (valid) {                     validReactions.push_back(reac);                 }             }             Reaction best = validReactions[0];             for (int i = 1; i &lt; validReactions.size(); i++) {                 if (validReactions[i].reactants &lt; best.reactants) {                     best = validReactions[i];                 }             }             cout &lt;&lt; best.raw &lt;&lt; endl;             for (string r : best.reactants) {                 availableSet.erase(r);             }         }     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。