比赛 EYOI暨SBOI暑假快乐赛4th 评测结果 ATAA
题目名称 锑分解炉 最终得分 75
用户昵称 lihaoze 运行时间 1.197 s
代码语言 C++ 内存使用 2.87 MiB
提交时间 2022-06-28 09:45:29
显示代码纯文本
#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<int, int>;
using PSI = std::pair<std::string, int>;

struct Node {
    std::map<std::string, int> a;
    Node () {}
    Node (std::string s) {
        s += 'Q';
        std::string t; int n = 0;
        for (auto i : s) {
            if ('0' <= i && i <= '9') n = n * 10 + i - '0'; 
            else if ('A' <= i && i <= 'Z' && t.size()) {
                a[t] += std::max(n, 1);
                t.clear(), n = 0, t += i;
            }
            else t += i;
        }
    }
    Node operator + (Node x) {
        Node t = *this;
        for (auto [x, y] : x.a) t.a[x] += y;
        return t;
    }
    Node operator * (int x) {
        Node t = *this;
        for (int i = 1; i < x; ++ i)
            t = *this + t;
        return t;
    }
    bool operator == (Node x) {
        return a == x.a;
    }
};

struct NodeSet {
    Node a;
    NodeSet () {}
    NodeSet (std::vector<Node>& x) { 
        for (auto i : x) a = a + i;
    }
    bool operator == (NodeSet x) {
        return a == x.a;
    }
    bool operator != (NodeSet x) {
        return !(a == x.a);
    }
};

int n, m, mx;
std::string t;
std::vector<std::string> sa, sb;
std::vector<Node> a, b;
std::vector<int> na, nb;

bool dfs(int ia, int ib) {
    if (ia > n || ib > m) return false;
    if (ia == n && ib == m) {
        std::vector<Node> ta, tb;
        for (int i = 0; i < n; ++ i) ta.emplace_back(a[i] * na[i]);
        for (int i = 0; i < m; ++ i) tb.emplace_back(b[i] * nb[i]);
        return NodeSet(ta) == NodeSet(tb);
    }
    for (int i = 1; i <= mx; ++ i) {
        na.emplace_back(i);
        if (dfs(ia + 1, ib)) return true;
        na.pop_back();
    }
    for (int i = 1; i <= mx; ++ i) {
        nb.emplace_back(i);
        if (dfs(ia, ib + 1)) return true;
        nb.pop_back();
    }
    return false;
}

int main() {
    freopen("Sbfenjielu.in", "r", stdin); 
    freopen("Sbfenjielu.out", "w", stdout);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> t;
        sa.emplace_back(t);
        a.emplace_back(t);
    }
    for (int i = 1; i <= m; ++ i) {
        std::cin >> t;
        sb.emplace_back(t);
        b.emplace_back(t);
    }
    while (++ mx, !dfs(0, 0));
    for (int i = 0; i < n; ++ i) {
        if (na[i] != 1) std::cout << na[i];
        std::cout << sa[i];
        if (i != n - 1) std::cout << '+';
    }
    std::cout << '=';
    for (int i = 0; i < m; ++ i) {
        if (nb[i] != 1) std::cout << nb[i];
        std::cout << sb[i];
        if (i != m - 1) std::cout << '+';
    }
    return 0;
}