比赛 |
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;
}