核心: dfs

普通人想法, 直接将每个product中方程式中最小的化学方程组输出即可(其实就是我开始的想法)

大佬总能在考场时候,想到这题需要用dfs来验证每一种可能输出方案

核心: 想到方案组合的可能性,一定要用dfs

需要用到substr() ,灵活的截取方程组中的数字

经典操作: substr(len - 2)

满分代码

/**
题意: 输出化学方程式

难点: 输入数据, 标记哪些化学物使用过了
截取最后一个数字,用len - 2
*/
#include <cstring>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 120;
unordered_map<int, vector<vector<int>>> need;
bool st[N], ori[N]; // st是否使用过, ori是否原材料,
int p[N];
int m, n, q;


bool dfs(int s, vector<vector<int>> &res)
{
    if (s == n)
    {
        int j = 0;
        for(auto &r : res)
        {
            for(int i = 0; i < r.size(); i++)
            {
                if (i) printf(" + ");
                printf("%02d", r[i]);
            }
            printf(" -> %02d\n", p[j++]);
        }
        return true;
    }
    int product = p[s];
    vector<vector<int>> react = need[product];

    for(auto &t: react)
    {
        bool success = true;
        for(auto u: t)
        {
            if (!ori[u] || st[u]) // 这一步逻辑开始很复杂, 借鉴了大佬的思路(节约了不少代码)
            {
                success = false;
                break;
            }
        }
        if (!success) continue;
        for(auto u: t) st[u] = true;
        res.push_back(t);
        if (dfs(s + 1, res)) return true;
        for(auto u: t) st[u] = false;
        res.pop_back();
    }

    return false;
}
int main()
{
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        ori[x] = true;
    }
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        vector<int> temp;
        if (ori[p[i]])
        {
            temp.push_back(p[i]);
            need[p[i]].push_back(temp);
        }
    }
    cin >> q;
    getchar();
    while (q --)
    {
        string str;
        getline(cin, str);
        int len = str.length();
        int product = stoi(str.substr(len - 2));
        vector<int> temp;
        // 经典操作, 借鉴大佬的代码
        for (int k = 0; k < str.size() - 6; k += 5) {
            int b = stoi(str.substr(k, 2));//取出公式原料
            temp.push_back(b);
        }
        need[product].push_back(temp);
    }
    // 排序方程式
    for(auto &t: need)
    {
        sort(t.second.begin(), t.second.end());
    }
    vector<vector<int>> result;
    dfs(0, result);
}

21 分代码 3个测试点错误

/**
题意: 输出化学方程式

难点: 输入数据, 标记哪些化学物使用过了
截取最后一个数字,用len - 2
*/
#include <cstring>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 120;
unordered_map<int, vector<vector<int>>> need;
bool st[N], ext[N], is_p[N]; // st是否使用过, ext是否存在, ep是否是反应物
int p[N];
int m, n, q;


bool dfs(int s, vector<vector<int>> &res)
{
    if (s == n)
    {
        int j = 0;
        for(auto &r : res)
        {
            for(int i = 0; i < r.size(); i++)
            {
                if (i) printf(" + ");
                printf("%02d", r[i]);
            }
            printf(" -> %02d\n", p[j++]);
        }
        return true;
    }
    int product = p[s];
    vector<vector<int>> react = need[product];

    for(auto &t: react)
    {
        bool success = true;

        for(auto u: t)
        {
            if (!ext[u] || st[u])
            {
                success = false;
                break;
            }
        }
        if (!success) continue;
        for(auto u: t) st[u] = true;
        res.push_back(t);
        if (dfs(s + 1, res)) return true;
        for(auto u: t) st[u] = false;
        res.pop_back();

    }

    return false;
}
int main()
{
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        ext[x] = true;
    }
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        is_p[p[i]] = true;
    }
    cin >> q;
    getchar();
    while (q --)
    {
        string str;
        getline(cin, str);
        int len = str.length();
        int product = stoi(str.substr(len - 2));
        vector<int> temp;
        if (is_p[product])
        {
            temp.push_back(product);
            need[product].push_back(temp);
            temp.clear();
        }

       for(int i = 0; i < len - 2; i++)
       {
           int sum = 0;
           bool flag = false;

           while (str[i] >= '0' && str[i] <= '9')
           {
               int x = str[i] - '0';
               sum = sum * 10 + x;
               i++;
               flag = true;
           }
           if (flag) temp.push_back(sum); // 方程式元素可能是0
       }
        need[product].push_back(temp);
    }
    // 排序方程式
    for(auto &t: need)
    {
        sort(t.second.begin(), t.second.end());
    }
    vector<vector<int>> result;
    dfs(0, result);
}