关于c++:PAT甲级2020年冬季考试-74-Chemical-Equation

7-4 Chemical Equation (30 分)

A chemical equation is the symbolic representation of a chemical reaction in the form of symbols and formulae, wherein the reactant entities are given on the left-hand side and the product entities on the right-hand side. For example, $$CH_4+2O_2=CO_2+2H_2O$$

means that the reactants in this chemical reaction are methane and oxygen: CH4 and O​2, and the products of this reaction are carbon dioxide and water: CO2 and H2O.

Given a set of reactants and products, you are supposed to tell that in which way we can obtain these products, provided that each reactant can be used only once. For the sake of simplicity, we will consider all the entities on the right-hand side of the equation as one single product.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤20), followed by N distinct indices of reactants. The second line gives an integer M (1≤M≤10), followed by M distinct indices of products. The index of an entity is a 2-digit number.

Then a positive integer K (≤50) is given, followed by K lines of equations, in the format:

$$
reactant_1 + reactant_2 + … + reactant_n -> product
$$

where all the reactants are distinct and are in increasing order of their indices.

Note: It is guaranteed that

• one set of reactants will not produce two or more different products, i.e. situation like 01 + 02 -> 03 and 01 + 02 -> 04 is impossible;
• a reactant cannot be its product unless it is the only one on the left-hand side, i.e. 01 -> 01 is always true (no matter the equation is given or not), but 01 + 02 -> 01 is impossible; and
• there are never more than 5 different ways of obtaining a product given in the equations list.

Output Specification:

For each case, print the equations that use the given reactants to obtain all the given products. Note that each reactant can be used only once.

Each equation occupies a line, in the same format as we see in the inputs. The equations must be print in the same order as the products given in the input. For each product in order, if the solution is not unique, always print the one with the smallest sequence of reactants — A sequence $${a_1,⋯,a_​m}$$ is said to be smaller than another sequence $${b_1 ,⋯,b​_n} $$if there exists $$1≤i≤min(m,n)$$ so that $$a_j​​ =b_j \;\; for \;\;all\;\; j<i, and\;\; ai​​ <bi.$$

It is guaranteed that at least one solution exists.

Sample Input:

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

Sample Output:

02 + 03 + 05 -> 08
01 + 09 + 16 -> 03
04 -> 04

题目要求

题目粗心

给定 n 个反应物，m 个生成物和 k 个化学反应方程式。要求依据反应物和化学方程式输入能够取得生成物的化学方程式，生成规定如下：

• 1、一组反应物只会生成一种 product
• 2、除了 pro->pro 的状况，一个化学方程式是不可能呈现反应物中存在生成物的状况
• 3、对于有多个生成的化学式输入字典序最小的那个。
• 4、每一种反应物只能应用一次

算法思路

此题如同只能应用深度优先遍从来解决，起因在于须要将所有的生成物进行生成，并且题目保障肯定存在一个解。那么应用贪婪算法取每一次取得以后生成物字典序最小的有可能会导致前面的生成物无奈生成的状况。为了不便进行搜寻咱们应用构造体 Equation 来封装咱们须要的数据，这里将算法的过程分为预处理和 DFS。

• 数据结构：

struct Equation {
    string equation;
    vector<int> reacts;
    int prod{};

    friend bool operator<(const Equation &a, const Equation &b) {return a.equation < b.equation;}
};
unordered_map<int, bool> reactants;// 标记以后反应物是否能够应用
unordered_map<int, set<Equation>> products;// 依据 product 建设到所有生成该生成物的 Equation 汇合

vector<int> pro;// 所有须要生成的生成物编号
vector<string> ans;// 所有的后果汇合

数据的预处理

首先在输出所有反应物的时候标记 reactants[index] = true，在输出生成物的时候须要建设 product->product 这样的方程式增加到 products 汇合中，并同时标记以后成物为反应物。最初在输出每一行的化学方程式的时候应用 process 函数进行解决，将其封装为一个 Equation，并增加到 products 汇合中。

DFS

咱们应用输出的生成物数组 pro 的下标来代表以后搜寻的地位，起始为 0，终止地位为 m -1，DFS(proCur,proEnd)的含意为数组 [proCur,proEnd-1] 的生成物是否能够被生成，如果能够返回 true, 否则返回 false。那么原问题的解就是 DFS(0,m)。那么递归边界和递归体别离为：

• 递归边界：当咱们以后遍历的下标为 m 的时候阐明遍历结束，取得了一组解，间接返回 true。
• 递归体：首先遍历以后生成物 pro[proCur]的所有化学方程式，判断以后的方程是是否能够应用，如果能够，先标记以后化学方程式的生成物全副曾经应用，并将方程式增加到 ans 数组中，而后进行下一层递归，判断 proCur + 1 以及后续的生成物是否能够被生成，如果为 true，阐明从 proCur 地位到数组开端的所有生成物都能够被生成，返回 true。否则阐明后续生成物生成失败，须要回溯，先将所有的反应物标记为未应用，而后 ans 弹出之前增加的方程式。

留神点

• 1、这里应用 DFS 次要是因为须要生成所有的生成物，一个都不能落下，所以贪婪算法不可用，测试点 1 和 5 考查该点。
• 2、每一个查问的生成物都能够生成 product->product 的化学方程式，须要人为增加该式子到汇合中。

提交后果

AC 代码

#include<cstdio>
#include<vector>
#include<iostream>
#include<unordered_map>
#include <set>
#include <string>

using namespace std;

struct Equation {
    string equation;
    vector<int> reacts;
    int prod{};

    friend bool operator<(const Equation &a, const Equation &b) {return a.equation < b.equation;}
};

unordered_map<int, bool> reactants;// 标记以后反应物是否能够应用
unordered_map<int, set<Equation>> products;// 依据 product 建设到所有生成该生成物的 Equation 汇合

vector<int> pro;// 所有须要生成的生成物编号
vector<string> ans;// 所有的后果汇合

// 将 s 封装为一个 Equation
void process(const string &s) {int n = s.size();
    if (n == 0) {return;}
    Equation e;
    // 最初两位为生成物编号
    e.prod = stoi(s.substr(n - 2));
    // 合成字符串获取反应物
    string temp;
    for (int i = 0; i < n; ++i) {if (s[i] >= '0' && s[i] <= '9') {temp.push_back(s[i]);
        } else if (s[i] == ' ' && !temp.empty()) {int v = stoi(temp);
            e.reacts.push_back(v);
            temp.clear();} else if (s[i] == '-') {break;}
    }
    e.equation = s;
    products[e.prod].insert(e);
}

// 判断以后的生成物 pro[proCur]是否能够被生成，如果不能够就得回溯
bool DFS(int proCur, int proEnd) {if (proCur == proEnd) {
        // 此时曾经将所有的生成物生成结束
        return true;
    }
    // 生成物编号
    int proNo = pro[proCur];
    // 遍历以后生成物 proNo 的所有化学方程式
    for (const auto &allEquations:products[proNo]) {
        // 判断以后的方程是是否能够应用（所有的反应物是否都没有被应用过）bool isvalid = true;
        for (int react:allEquations.reacts) {if (!reactants[react]) {
                // 以后反应物被应用过
                isvalid = false;
                break;
            }
        }
        if (!isvalid) {continue;}
        // 存在一种解
        ans.push_back(allEquations.equation);
        // 而后将所有的反应物都进行标记应用过
        for (int react:allEquations.reacts) {reactants[react] = false;
        }
        // 递归查问后续的生成物是否能够生成
        if (DFS(proCur + 1, proEnd)) {
            // 能够生成阐明找到了一组解，间接返回即可
            return true;
        }
        // 以后抉择的化学方程式使得后续的生成物无奈生成，须要回溯
        for (int react:allEquations.reacts) {reactants[react] = true;
        }
        ans.pop_back();}
    // 遍历了所有的化学生成式都没有方法取得以后生成物
    return false;
}

int main() {
    // n 为反应物数量，m 为生成物数量
    int n, m;
    scanf("%d", &n);
    int index;
    for (int i = 0; i < n; ++i) {scanf("%d", &index);
        // 标记所有给出的反应式
        reactants[index] = true;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        pro.push_back(stoi(s));
        // 每一个反应物都存在一个 pro->pro 的化学方程式
        Equation e;
        e.equation.append(s);
        e.equation.append("->");
        e.equation.append(s);
        e.prod = pro[i];
        e.reacts.push_back(pro[i]);
        // 标记以后的生成物同时为反应物
        reactants[pro[i]] = true;
        // 将以后的 pro->pro 的化学方程式增加到 products 汇合中
        products[pro[i]].insert(e);
    }
    int k;
    scanf("%d", &k);
    // 排汇回车
    getchar();
    string s;
    for (int i = 0; i < k; ++i) {getline(cin, s);
        // 解决每一个化学方程式，封装为 Equation
        process(s);
    }
    // 深度搜寻，保障取得所有的生成物
    DFS(0, m);
    // 输入后果汇合
    for (const auto &v:ans) {cout << v << endl;}
    return 0;
}