虫食算

lqy1416 · 2019-03-15 23:45:00 · 题解

这道题令人一看就不想写啊QwQ 我们从最后一位开始枚举，进行搜索。 正解是高斯消元然而只会搜索的我不会呀呜呜呜 （码风奇丑无比不要喷我。。） 上代码

#include<cstdio>
#include<algorithm>
using namespace std;
char a[100],b[100],c[100];
int n;
bool usednum[100],usedchar[100];//这个数字，字符是否已用过
int jw[100],num[100];
bool pd(int pos) {
    while(pos--) {
        if(usedchar[a[pos]]&&usedchar[b[pos]]&&usedchar[c[pos]]) {
            int summ=num[a[pos]]+num[b[pos]];
            int x=num[c[pos]];
            if((summ+1)%n==x||summ==x||(summ-n)==x||(summ+1-n)==x) continue;
            else return true;
        }
    }
    return false;
}//这里的判断是判断逻辑是否出错，true代表出错，不要求完全剪没，只是粗略的剪枝
void dfs(int pos) {//从后往前按位枚举
    if(pos == -1) {
        for(int i=0; i<n; i++) printf("%d ",num[i]);
        exit(0);
    }//已经枚举完所有，并且成立
    if(pd(pos)) return ;//剪枝
    if(usedchar[a[pos]]&&usedchar[b[pos]]&&usedchar[c[pos]]) {
        if((num[a[pos]]+num[b[pos]]+jw[pos])%n==num[c[pos]]) {
            jw[pos-1]+=(num[a[pos]]+num[b[pos]]+jw[pos])/n;
            dfs(pos-1);
            jw[pos-1]-=(num[a[pos]]+num[b[pos]]+jw[pos])/n;
        } else return ;//这一位上的数都有赋过值
    } else if(usedchar[a[pos]]&&usedchar[b[pos]]) {
        if(usednum[(jw[pos]+num[a[pos]]+num[b[pos]])%n]) return;
        num[c[pos]]=(jw[pos]+num[a[pos]]+num[b[pos]])%n;
        usedchar[c[pos]]=true;
        usednum[num[c[pos]]]=true;
        jw[pos-1]+=(jw[pos]+num[a[pos]]+num[b[pos]])/n;
        dfs(pos-1);
        usednum[num[c[pos]]]=false;
        usedchar[c[pos]]=false;
        jw[pos-1]-=(jw[pos]+num[a[pos]]+num[b[pos]])/n;
    } else if(usedchar[a[pos]]&&usedchar[c[pos]]) {
        if(usednum[(num[c[pos]]+n-jw[pos]-num[a[pos]])%n]) return;
        num[b[pos]]=(num[c[pos]]+n-jw[pos]-num[a[pos]])%n;
        usedchar[b[pos]]=true;
        usednum[num[b[pos]]]=true;
        jw[pos-1]+=(jw[pos]+num[a[pos]]+num[b[pos]])/n;
        dfs(pos-1);
        usednum[num[b[pos]]]=false;
        usedchar[b[pos]]=false;
        jw[pos-1]-=(jw[pos]+num[a[pos]]+num[b[pos]])/n;//计算大法好啊
    } else if(usedchar[b[pos]]&&usedchar[c[pos]]) {
        if(usednum[(num[c[pos]]+n-jw[pos]-num[b[pos]])%n]) return;
        num[a[pos]]=((num[c[pos]]+n-jw[pos]-num[b[pos]]))%n;
        usedchar[a[pos]]=true;
        usednum[num[a[pos]]]=true;
        jw[pos-1]+=(jw[pos]+num[a[pos]]+num[b[pos]])/n;
        dfs(pos-1);
        usednum[num[a[pos]]]=false;
        usedchar[a[pos]]=false;
        jw[pos-1]-=(jw[pos]+num[a[pos]]+num[b[pos]])/n;//缺的话缺啥补啥
    } else if(usedchar[a[pos]]) {
        for(int i=n-1; i>=0; i--) {
            if(!usednum[i]) {
                num[b[pos]]=i;
                usednum[i]=true;
                usedchar[b[pos]]=true;
                dfs(pos);
                usednum[i]=false;
                usedchar[b[pos]]=false;
            }
        }//枚举a后枚举b，之后才会计算上面
    } else {
        for(int i=n-1; i>=0; i--) {
            if(!usednum[i]) {
                num[a[pos]]=i;
                usednum[i]=true;
                usedchar[a[pos]]=true;
                dfs(pos);
                usednum[i]=false;
                usedchar[a[pos]]=false;
            }//程序最开始运行的是这里，先枚举a
        }
    }
}
int main() {
    scanf("%d%s%s%s",&n,a,b,c);
    for(int i=0; i<n; i++) {
        a[i]-='A';
        b[i]-='A';
        c[i]-='A';/转成数字好操作
    }
    dfs(n-1);
    return 0;
}

代码奇乱不要喷我呜呜呜 嘤嘤嘤，蒟蒻爆哭