1179 Chemical Equation – PAT甲级真题

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, CH4+2O2=CO2+2H2O means that the reactants in this chemical reaction are methane and oxygen: CH4 and O2, 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 { a1,⋯,am } is said to be smaller than another sequence { b1,⋯,bn } if there exists 1≤i≤min(m,n) so that aj=bj 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

题目大意：给定一组反应物和产物，你需要告诉我们如何获得这些产物，假设每种反应物只能使用一次。为了简单起见，我们将方程式右侧的所有实体视为一个单一的产物。打印使用给定的反应物来获得所有给定的产物的方程式。注意，每个反应物只能使用一次。

分析：used用来标记每个反应物是否可用，ans[i]表示第i个产物需要用到它的第i条合成公式（排序后），pro中存储产物的编号，equa中存储每个产物的所有合成公式。
如果某个产物自己本身就是反应物，这一条合成公式需要加到配方里。在匹配方案之前，先把每个配方按照题目要求从小到大排序。
本文搜索采用的序列是按照产物编号进行顺序搜索，确保每一个产物都在满足要求的情况下才继续下一次的搜索。
搜索过程中，尝试某产物的所有合成公式，如果当前公式中所有反应物都还可用，则进入下一层搜索（注意回来时要把这些反应物还给我们）。当达到M层时，表示已经完全匹配，并且是按照题目要求的最优序，输出每一条合成配方即可。

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
int N, M, K, num, used[101], ans[101];
vector<int> pro, temp;
vector<vector<int>> equa[101];
string s;
bool cmp(const vector<int> &a, const vector<int> &b) {
    for (int i = 0; ; i++) 
        if (a[i] != b[i]) return a[i] < b[i];
}
void dfs(int x) {
    if (x == M) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < equa[pro[i]][ans[i]].size(); j++) {
                if (j != 0) cout << " + ";
                cout << setw(2) << setfill('0') << equa[pro[i]][ans[i]][j];
            }
            cout << " -> " << setw(2) << setfill('0') << pro[i] << "\n";
        }
        exit(0);
    }
    for (int i = 0; i < equa[pro[x]].size(); i++) {
        int flag = 1;
        vector<int> A = equa[pro[x]][i];
        for (auto it : A) 
            if (used[it] != 1) {
                flag = 0;
                break;
            }
        if (flag == 0) continue;
        for (auto it : A) used[it] = 2;
        ans[x] = i;
        dfs(x + 1);
        for (auto it : A) used[it] = 1;
    }
}
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num;
        used[num] = 1;
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> num;
        if(used[num] == 1) equa[num].push_back({num});
        pro.push_back(num);
    }
    cin >> K;
    for (int i = 0; i < K; i++) {
        temp.clear();
        while (cin >> num >> s) {
            temp.push_back(num);
            if (s == "->") {
                cin >> num;
                equa[num].push_back(temp);
                break;
            }
        }
    }
    for (int i = 0; i < M; i++) sort(equa[pro[i]].begin(), equa[pro[i]].end(), cmp);
    dfs(0);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <iomanip>

#include <vector>

using namespace std;

int N, M, K, num, used[101], ans[101];

vector<int> pro, temp;

vector<vector<int>> equa[101];

string s;

bool cmp(const vector<int> &a, const vector<int> &b) {

for (int i = 0; ; i++)

if (a[i] != b[i]) return a[i] < b[i];

}

void dfs(int x) {

if (x == M) {

for (int i = 0; i < M; i++) {

for (int j = 0; j < equa[pro[i]][ans[i]].size(); j++) {

if (j != 0) cout << " + ";

cout << setw(2) << setfill('0') << equa[pro[i]][ans[i]][j];

}

cout << " -> " << setw(2) << setfill('0') << pro[i] << "\n";

}

exit(0);

}

for (int i = 0; i < equa[pro[x]].size(); i++) {

int flag = 1;

vector<int> A = equa[pro[x]][i];

for (auto it : A)

if (used[it] != 1) {

flag = 0;

break;

}

if (flag == 0) continue;

for (auto it : A) used[it] = 2;

ans[x] = i;

dfs(x + 1);

for (auto it : A) used[it] = 1;

}

int main() {

cin >> N;

for (int i = 0; i < N; i++) {

cin >> num;

used[num] = 1;

}

cin >> M;

for (int i = 0; i < M; i++) {

cin >> num;

if(used[num] == 1) equa[num].push_back({num});

pro.push_back(num);

}

cin >> K;

for (int i = 0; i < K; i++) {

temp.clear();

while (cin >> num >> s) {

temp.push_back(num);

if (s == "->") {

cin >> num;

equa[num].push_back(temp);

break;

}

for (int i = 0; i < M; i++) sort(equa[pro[i]].begin(), equa[pro[i]].end(), cmp);

dfs(0);

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版