[NOI 2000]算符破译 - ppfish - 262369

记录编号	262369	评测结果	AAAAAAAAAA
题目名称	[NOI 2000]算符破译	最终得分	100
用户昵称	ppfish	是否通过	通过
代码语言	C++	运行时间	5.004 s
提交时间	2016-05-20 16:32:19	内存使用	0.34 MiB
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
 
template<typename T>inline void Read(T &x)
{
    int f = 1;
    char t = getchar();
    while (t < '0' || t > '9') {
        if (t == '-') f = -1;
        t = getchar();
    }
    x = 0;
    while (t >= '0' && t <= '9') {
        x = x * 10 + t - '0';
        t = getchar();
    }
    x *= f;
}
 
template<typename T>inline void Write(T x)
{
    static int output[20];
    int top = 0;
    if (x < 0) putchar('-'), x = -x;
    do {
        output[++top] = x % 10;
        x /= 10;
    } while (x > 0);
    while (top > 0) putchar('0' + output[top --]);
    putchar('\n');
}
 
template<typename T>inline void chkmin(T &x, T y) { if (x > y) x = y; }
template<typename T>inline void chkmax(T &x, T y) { if (x < y) x = y; }
 
const int maxn = 1005;
const int sigma = 13;
const int maxlen = 14;
const char uti[] = "=+*0123456789";
 
int n;
int len[maxn];
char str[maxn][maxlen];
 
bool ban[sigma];
bool fst[sigma];
bool end[sigma];
bool ineql[sigma];
bool okeql[sigma];
bool adj[sigma][sigma];
int st[maxn];
int ed[maxn];
vector<pair<int, int> > neighbor[sigma];
 
bool used[sigma];
int to[sigma];
 
bool nosol = true;
int res[sigma][sigma];
 
void input()
{
    Read(n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str[i] + 1);
        len[i] = strlen(str[i] + 1);
        for (int j = 1; j <= len[i]; j++) {
            if (str[i][j] - 'a' >= sigma) {
                puts("noway");
                exit(0);
            }
        }
    }
}
 
long long calc(char *re, int l, int r)
{
    static long long num[maxlen];
    static long long qn[maxlen];
    static char opr[maxlen];
    static char s[maxlen];
    int ol = 0;
    int nl = 0;
    int nt = 0;
    long long cnt;
    for (int i = l; i <= r; i++) {
        if (isalpha(re[i])) {
            s[i] = uti[to[re[i] - 'a']];
        } else {
            s[i] = re[i];
        }
    }
    if (!isdigit(s[l]) || !isdigit(s[r])) return -1;
    for (int i = l; i <= r; i++) {
        if (!isdigit(s[i])) opr[++ol] = s[i];
        else {
            cnt = s[i] - '0';
            while (i + 1 <= r && isdigit(s[i + 1])) {
                cnt = cnt * 10 + s[i + 1] - '0';
                i ++;
            }
            num[++nl] = cnt;
        }
    }
    qn[++nt] = num[1];
    for (int i = 1; i <= ol; i++) {
        if (opr[i] == '*') {
            qn[nt] = qn[nt] * num[i + 1];
        } else {
            qn[++nt] = num[i + 1];
        }
    }
    long long res = 0;
    while (nt > 0) res += qn[nt --];
    return res;
}
 
void prepare()
{
    static int appear[sigma];
    for (int i = 0; i < sigma; i++) okeql[i] = true;
    for (int i = 1; i <= n; i++) {
        memset(appear, 0, sizeof(appear));
        for (int j = 1; j <= len[i]; j++) {
            appear[str[i][j] - 'a'] ++;
            ineql[str[i][j] - 'a'] = true;
        }
        for (int j = 0; j < sigma; j++) {
            okeql[j] &= (appear[j] == 1);
            okeql[j] &= (str[i][1] - 'a' != j);
            okeql[j] &= (str[i][len[i]] - 'a' != j);
        }
        for (int j = 1; j < len[i]; j++) {
            adj[str[i][j] - 'a'][str[i][j + 1] - 'a'] = true;
            adj[str[i][j + 1] - 'a'][str[i][j] - 'a'] = true;
        }
        fst[str[i][1] - 'a'] = true;
        end[str[i][len[i]] - 'a'] = true;
    }
    static set<pair<int, int> > g[sigma];
    pair<int, int> foo;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < len[i]; j++) {
            g[str[i][j] - 'a'].insert(make_pair(j == 1 ? -1 : str[i][j - 1] - 'a', str[i][j + 1] - 'a'));
        }
    }
    for (int i = 0; i < sigma; i++) {
        for (set<pair<int, int> >::iterator it = g[i].begin(); it != g[i].end(); it++) {
            neighbor[i].push_back(*it);
        }
    }
}
 
vector<int> remain;
 
void fillmax(char s[maxlen], int l, int r)
{
    for (int i = l; i <= r; i++) {
        if (to[s[i] - 'a'] == -1) {
            s[i] = '9';
        }
    }
}
 
void fillmin(char s[maxlen], int l, int r)
{
    for (int i = l, last = -1; i <= r + 1; i++) {
        if (to[s[i] - 'a'] == -1 && last == -1) last = i;
        if ((to[s[i] - 'a'] != -1 || i == r + 1) && last != -1) {
            if (i - last == 1) {
                s[last] = '0';
            } else {
                s[last] = '1';
                for (int j = last + 1; j < i; j++) s[j] = '0';
            }
            last = -1;
        }
    }
}
 
void split()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= len[i]; j++) {
            if (to[str[i][j] - 'a'] == 0) {
                ed[i] = j - 1;
                st[i] = j + 1;
                break;
            }
        }
    }
}
 
bool checkrange()
{
    char tmp[maxlen];
    for (int i = 0; i < sigma; i++) {
        if (to[i] != -1) {
            for (int j = i; j < sigma; j++) {
                if (to[j] != -1) {
                    if (adj[i][j]) {
                        return false;
                    }
                }
            }
        }
    }
    long long lmax, rmax;
    long long lmin, rmin;
    for (int i = 1; i <= n; i++) {
        memcpy(tmp, str[i], sizeof(str[i]));
        fillmax(tmp, 1, len[i]);
        lmax = calc(tmp, 1, ed[i]);
        rmax = calc(tmp, st[i], len[i]);
        memcpy(tmp, str[i], sizeof(str[i]));
        fillmin(tmp, 1, len[i]);
        lmin = calc(tmp, 1, ed[i]);
        rmin = calc(tmp, st[i], len[i]);
        if (lmax < rmin || lmin > rmax) return false;
    }
    return true;
}
 
bool prezero()
{
    int pr, nx;
    for (int i = 0; i < sigma; i++) {
        if (to[i] == 3) {
            for (int j = 0; j < (int)neighbor[i].size(); j++) {
                pr = neighbor[i][j].first;
                nx = neighbor[i][j].second;
                if ((pr == -1 || (to[pr] < 3 && to[pr] != -1)) && (to[nx] == -1 || to[nx] >= 3)) {
                    return true;
                }
            }
        }
    }
    return false;
}
 
bool checkall()
{
    long long r1, r2;
    for (int i = 1; i <= n; i++) {
        r1 = calc(str[i], 1, ed[i]);
        r2 = calc(str[i], st[i], len[i]);
        if (r1 == -1 || r2 == -1 || r1 != r2) return false;
    }
    return true;
}
 
void dfs(int cur)
{
    if (cur == (int)remain.size()) {
        if (checkall()) {
            nosol = false;
            for (int i = 0; i < sigma; i++) {
                if (to[i] != -1) {
                    res[i][to[i]] ++;
                } else {
                    ban[i] = true;
                }
            }
        }
        return;
    }
    for (int i = 3; i < sigma; i++) {
        if (!used[i]) {
            used[i] = true;
            to[remain[cur]] = i;
            if (i != 3 || (i == 3 && !prezero())) dfs(cur + 1);
            used[i] = false;
            to[remain[cur]] = -1;
        }
    }
}
 
void enumopr(int cur)
{
    if (cur == 1) split();
    if (cur == 3) {
        if (checkrange()) {
            remain.clear();
            for (int i = 0; i < sigma; i++) {
                if (to[i] == -1 && ineql[i]) {
                    remain.push_back(i);
                }
            }
            dfs(0);
        }
        return;
    }
    for (int i = 0; i < sigma; i++) {
        if (cur == 0 && !okeql[i]) continue;
        if (to[i] == -1 && !fst[i] && !end[i]) {
            to[i] = cur;
            enumopr(cur + 1);
            to[i] = -1;
        }
    }
}
 
void solve()
{
    memset(to, -1, sizeof(to));
    enumopr(0);
    for (int i = 0; i < sigma; i++) {
        if (ban[i]) continue;
        int cert = -1;
        bool flag = true;
        for (int j = 0; j < sigma; j++) {
            if (res[i][j] > 0) {
                if (cert == -1) cert = j;
                else flag = false;
            }
        }
        if (cert != -1 && flag) {
            printf("%c%c\n", 'a' + i, uti[cert]);
        }
    }
    if (nosol) puts("noway");
}
 
int main()
{
    //#ifndef ONLINE_JUDGE
    freopen("equation.in", "r", stdin);
    freopen("equation.out", "w", stdout);
    //#endif
 
    input();
    prepare();
    solve();
 
    //#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    //#endif
    return 0;
}