比赛 20120919dfs 评测结果 AAAAAATAAA
题目名称 虫食算 最终得分 90
用户昵称 王者自由 运行时间 2.583 s
代码语言 C++ 内存使用 1.94 MiB
提交时间 2012-09-19 20:32:59
显示代码纯文本
#include <cstdio>
#include <cstdlib>
const int N = 'Z';
int n, a[N], b[N], c[N], t[N], o[N], k;
char s[4][N];
bool u[N], h[N];
bool ok() {
    for(int i=n; i>0; i--)
        if(t[a[i]] >= 0 && t[b[i]] >= 0 && t[c[i]] >= 0
                && t[c[i]] != (t[a[i]] + t[b[i]]) % n
                && t[c[i]] != (t[a[i]] + t[b[i]] + 1) % n)
            return 0;
    return 1;
}
void pailie(int x) {
    if(x > n) {
        int r = 0;
        for(int i=n; i>0; i--) {
            if((t[a[i]] + t[b[i]] + r) % n != t[c[i]])
                return;
            r = (t[a[i]] + t[b[i]] + r) / n;
        }
        for(int i=1; i<=n; i++)
            printf("%d ", t[i]);
        printf("\n");
        exit(0);
    }
    for(int i=n-1; i>=0; i--)
        if(!h[i]) {
            t[o[x]] = i;
            h[i] = 1;
            if(ok()) pailie(x + 1);
            h[i] = 0;
            t[o[x]] = -1;
        }
}
int main() {
    freopen("alpha.in", "r", stdin);
    freopen("alpha.out", "w", stdout);
    scanf("%d\n", &n);
    for(int i=1; i<=3; i++)
        scanf("%s\n", s[i]);
    for(int i=1; i<=n; i++) {
        a[i] = s[1][i-1] - 'A' + 1;
        b[i] = s[2][i-1] - 'A' + 1;
        c[i] = s[3][i-1] - 'A' + 1;
    }
    for(int i=n; i>0; i--) {
        if(!u[a[i]]) u[o[++k] = a[i]] = 1;
        if(!u[b[i]]) u[o[++k] = b[i]] = 1;
        if(!u[c[i]]) u[o[++k] = c[i]] = 1;
    }
    for(int i=0; i<n; i++) {
        t[i] = -1;
        pailie(1);
    }
    return 0;
}