求助卡常
查看原帖
求助卡常
204109
Daniel1234楼主2023/11/29 19:50

RTRT

#include<bits/stdc++.h>
using namespace std;
int n;
string s[1005];
int ord[15];
int ap[15];
int ans_ap[15];
int ans_ord[15];
bitset<15>op;
int b[40005];
unordered_map<int, int>mp[1<<13];
int dp[1<<13][13];
int lowbit(int x){
    return x & (-x);
}
void dfs(int now){
    if(1000 * clock() > 230 * CLOCKS_PER_SEC)return;
    int he = 0;
    for(int i = 0; i < now; ++i){
        if(ap[i] < ans_ap[i])return;
        if(ap[i] > ans_ap[i])break;
        he += (1 << ord[i]);
    }
    if(now == 13){
        for(int j = 0; j < 13; ++j){
            ans_ap[j] = ap[j];
            ans_ord[j] = ord[j];
        }
        return;
    }
    for(int i = op._Find_first(); i != op.size(); i = op._Find_next(i)){
        ord[now] = i;
        op[i] = 0;
        ap[now] += dp[he][i];
        dfs(now + 1);
        ap[now] -= dp[he][i];
        op[i] = 1;
    }
}
bool check(int i, int deng, int cheng, int jia, int ling){
    if(s[i][0] - 'a' == deng || s[i][s[i].size() - 1] - 'a' == deng)return 0;
    if(s[i][0] - 'a' == cheng || s[i][s[i].size() - 1] - 'a' == cheng)return 0;
    if(s[i][0] - 'a' == jia || s[i][s[i].size() - 1] - 'a' == jia)return 0;
    int num = 0;
    for(int p = 1; p < s[i].size(); p++){
        if(s[i][p] - 'a' == deng)num++;
        if(s[i][p] - 'a'  == deng || s[i][p] - 'a' == cheng || s[i][p] - 'a' == jia){
            if(s[i][p - 1] - 'a' == deng || s[i][p - 1] - 'a' == cheng || s[i][p - 1] - 'a' == jia){
                return 0;
            }
        }
    }
    if(num != 1)return 0;
    for(int p = 0; p < s[i].size() - 1; ++p){
        if(p == 0 || (p > 0 && (s[i][p-1] - 'a' == deng || s[i][p-1] - 'a' == jia || s[i][p-1] - 'a' == cheng))){
            if(s[i][p] - 'a' == ling && s[i][p + 1] - 'a' != deng && s[i][p + 1] - 'a' != jia && s[i][p + 1] - 'a' != cheng){
                return 0;
            }
        }
    }
    if(s[i].size() == 11){
        if(s[i][1] - 'a' == deng){
            int ok = 0;
            for(int j = 2; j < 11; ++j){
                if(s[i][j] - 'a' == cheng || s[i][j] - 'a' == jia){
                    ok = 1;
                    break;
                }
            }
            if(!ok)return 0;
        }
        if(s[i][9] - 'a' == deng){
            int ok = 0;
            for(int j = 0; j < 9; ++j){
                if(s[i][j] - 'a' == cheng || s[i][j] - 'a' == jia){
                    ok = 1;
                    break;
                }
            }
            if(!ok)return 0;
        }
    }
    return 1;
}
int dui[13];
bitset<15>may[13];
char ch[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '*', '='};
vector<int>can[13];
int js(string x){
    int ans = 0;
    int now = 1;
    int change = 0;
    for(int i = 0; i < x.size(); i++){
        if('0' <= x[i] && x[i] <= '9'){
            int s = 0;
            while(i < x.size() - 1 && '0' <= x[i + 1] && x[i + 1] <= '9'){
                s = s * 10 + x[i] - '0';
                i++;
            }
            s = s * 10 + x[i] - '0';
            now *= s;
            change = 1;
        }else if(x[i] == '+'){
            ans += now;
            now = 1;
            change = 0;
        }
    }
    if(change)ans += now;
    return ans;
}
bool pan(string x){
    int p = 0;
    for(int i = 0; i < x.size(); i++){
        if(x[i] == '=')p = i;
    }
    return js(x.substr(0, p)) == js(x.substr(p+1));
}
bool solve(int i){
    string x = "";
    for(auto j : s[i]){
        x += ch[dui[j - 'a']];
    }
    if(!pan(x))return 0;
    return 1;
}
int vis[13];
int now_is_ok[13];
void dfss(int now){
    if(now == 13){
        for(auto i : can[12]){
            if(!solve(i))return;
        }
        for(int i = 0; i < 13; i++){
            may[i][dui[i]] = 1;
            if(may[i].count() > 1)now_is_ok[i] = 1;
        }
        return;
    }
    if(now > 0){
        for(auto i : can[now - 1]){
            if(!solve(i))return;
        }
    }
    if(vis[ans_ord[now]]){
        dfss(now + 1);
    }else{
        for(int i = op._Find_first(); i != op.size(); i = op._Find_next(i)){
            dui[ans_ord[now]] = i;
            op[i] = 0;                                                                                  
            dfss(now + 1);
            op[i] = 1;
        }
    }
}
signed main(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
        int sum = 0;
        for(int j = 0; j < s[i].size(); ++j){
            if(s[i][j] < 'a' || s[i][j] > 'm'){
                cout << "noway" << endl;
                return 0;
            }
            sum |= 1<<(s[i][j] - 'a');
        }
        b[sum]++;
    }
    for(int i = 0; i < 13; i++)op[i] = 1;
    for(int i = 0; i < (1 << 13); i++){
        for(int j = (1 << 13) - 1; j >= 0; j--){
            if(i&j)continue;
            if(!i)mp[i][j] = b[j];
            else mp[i][j] = mp[i^lowbit(i)][j] + mp[i^lowbit(i)][j^lowbit(i)];
        }
    }
    for(int i = 0; i < (1 << 13); i++){
        for(int j = 0; j < 13; j++){
            dp[i][j] = mp[i][1<<j];
        }
    }
    dfs(0);
    for(int i = 1; i <= n; i++){
        int mx = 0;
        for(int j = 0; j < s[i].size(); j++){
            for(int k = 0; k < 13; k++){
                if(ans_ord[k] == s[i][j] - 'a'){
                    mx = max(mx, k);
                    break;
                }
            }
        }
        can[mx].emplace_back(i);
    }
    for(int i = 0; i < 13; ++i){
        for(int j = 0; j < 13; ++j){
            for(int k = 0; k < 13; ++k){
                for(int w = 0; w < 13; ++w){
                    if(i == j || i == k || i == w || j == k || j == w || k == w)continue;
                    int ok = 1;
                    for(int p = 1; p <= n; p++){
                        if(!check(p, i, j, k, w))ok = 0;
                    }
                    if(!ok)continue;
                    dui[i] = 12;
                    dui[j] = 11;
                    dui[k] = 10;
                    dui[w] = 0;
                    op.reset();
                    for(int ii = 1; ii <= 9; ii++)op[ii] = 1;
                    memset(vis, 0, sizeof(vis));
                    vis[i] = vis[j] = vis[k] = vis[w] = 1;
                    dfss(0);
                }
            }
        }
    }
    for(int i = 0; i < 13; i++){
        if(may[i].count() == 0){
            cout << "noway" << endl;
            return 0;
        }
    }
    for(int i = 0; i < 13; i++){
        if(may[i].count() == 1){
            cout << char(i+'a') << ch[may[i]._Find_first()] << endl;
        }
    }
    return 0;
}
2023/11/29 19:50
加载中...