比赛 |
EYOI暨SBOI暑假快乐赛4th |
评测结果 |
AWAW |
题目名称 |
锑分解炉 |
最终得分 |
50 |
用户昵称 |
Restly |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-06-28 10:09:53 |
显示代码纯文本
#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
#define pb emplace_back
using namespace std;
const int maxn = 15;
string s[maxn],t[maxn];
vector<pair<int,int> > g[maxn];
vector<pair<int,int> > p[maxn];
int n,m,w1[maxn],w2[maxn];
int cnt[200],tot[200];
int gcd(int x,int y) {
return y ? gcd(y , x % y) : x;
}
bool flag = false;
void dfs(int x,int T) {
if(flag)return ;
if(x > T) {
memset(cnt , 0 , sizeof(cnt));
memset(tot , 0 , sizeof(tot));
for(int i = 1;i <= n;++ i) {
for(auto k : g[i])cnt[k.fir] += w1[i] * k.sec;
}
for(int i = 1;i <= m;++ i) {
for(auto k : p[i])tot[k.fir] += w2[i] * k.sec;
}
for(int i = 0;i < 200;++ i) {
if(cnt[i] != tot[i]) {
flag = false;
return ;
}
}
flag = true;
int g = 0;
for(int i = 1;i <= n;++ i)g = gcd(g , w1[i]);
for(int i = 1;i <= m;++ i)g = gcd(g , w2[i]);
for(int i = 1;i <= n;++ i) {
if(i != 1)cout << "+";
if(w1[i] / g > 1)cout << w1[i] / g;
cout << s[i];
}
cout << "=";
for(int i = 1;i <= m;++ i) {
if(i != 1)cout << "+";
if(w2[i] / g > 1)cout << w2[i] / g;
cout << t[i];
}
return ;
}
if(x <= n) {
for(int i = 1;i <= 6;++ i) {
if(flag)return ;
w1[x] = i;
dfs(x + 1 , T);
w1[x] = 0;
}
return ;
}
else {
for(int i = 1;i <= 6;++ i) {
if(flag)return ;
w2[x - n] = i;
dfs(x + 1 , T);
w2[x - n] = 0;
}
}
return ;
}
int main() {
freopen("Sbfenjielu.in","r",stdin);
freopen("Sbfenjielu.out","w",stdout);
cin >> n >> m;
for(int i = 1;i <= n;++ i)cin >> s[i];
for(int i = 1;i <= m;++ i)cin >> t[i];
for(int i = 1;i <= n;++ i) {
memset(cnt , 0 , sizeof(cnt));
for(int k = 0;k < s[i].length();++ k) {
if(s[i][k] >= '0'&&s[i][k] <= '9') {
-- cnt[s[i][k - 1]];
cnt[s[i][k - 1]] += s[i][k] ^ '0';
if(s[i][k - 1] >= 'a'&&s[i][k - 1] <= 'z')-- cnt[s[i][k - 2]],cnt[s[i][k - 2]] += s[i][k] ^ '0';
}
else {
++ cnt[s[i][k]];
}
}
for(int k = 0;k < 200;++ k) {
if(cnt[k])g[i].pb(mp(k , cnt[k]));
}
}
for(int i = 1;i <= m;++ i) {
memset(cnt , 0 , sizeof(cnt));
for(int k = 0;k < t[i].length();++ k) {
if(t[i][k] >= '0'&&t[i][k] <= '9') {
-- cnt[t[i][k - 1]];
cnt[t[i][k - 1]] += t[i][k] ^ '0';
if(t[i][k - 1] >= 'a'&&t[i][k - 1] <= 'z')-- cnt[t[i][k - 2]],cnt[t[i][k - 2]] += t[i][k] ^ '0';
}
else ++ cnt[t[i][k]];
}
for(int k = 0;k < 200;++ k) {
if(cnt[k])p[i].pb(mp(k , cnt[k]));
}
}
dfs(1 , n + m);
return 0;
}