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