sac：考前佛系刷题，打打搜索和暴力...

Problem

https://www.luogu.org/problemnew/show/P1092

Solution

很明显可以看出：

• 从后面往前面搜，利用进位性质
• 数字从大到小枚举，使分支尽量少以尽快达到解
• 每次都进行目前竖式的正确性验证。若肯定无解，则退出

关于第三点有个 emm 的问题，就是如果中间的进位不能决定，后面都不能决定是否合法

然后我就找到不能决定的地方就退掉了？？往其它方向搜索去了改了一下午
事实上只有两种情况（进位 / 不进位），所以两种都判一下无解就行了

心路历程（TLE*1）:
10s -> 8s -> 5s -> 3s -> 1.xs

看了题解后就 emm

听说正解高斯消元但我不想写

话说 noip 要是考了这种题我岂不是药丸

$\sqrt{\sqrt{\text{me}}}$.jpg

Code

// Code by ajcxsu
// Problem: worm cac

#include<bits/stdc++.h>
using namespace std;

const int N=30;
int num[600];
char A[N];
char B[N];
char C[N], used[N];
int n;
bool check() {
    int t=0, j=n-1;
    for(int j=n-1;j>=0;j--)
        if(num[A[j]]!=-1 && num[B[j]]!=-1)
            if(num[C[j]]!=-1 && num[C[j]]!=(1+num[A[j]]+num[B[j]])%n && num[C[j]]!=(num[A[j]]+num[B[j]])%n)
                return false;
    for(int j=n-1;j>=0;j--) {
        if(num[A[j]]==-1 || num[B[j]]==-1)
            return true;
        if(num[C[j]]!=-1 && num[C[j]]!=(t+num[A[j]]+num[B[j]])%n) return false;
        t=(t+num[A[j]]+num[B[j]])/n;
    }
    if(t) return false;
    return true;
}
char arr[N];
int np=0;
void dfs(int x) {
    if(x>np) {
        for(int i='A';i<'A'+n;i++) cout<<num[i]<<" \n"[i=='A'+n-1];
        exit(0);
    }
    for(int i=n-1;i>=0;i--) if(!used[i]) {
        used[i]=1;
        num[arr[x]]=i;
        if(check()) dfs(x+1);
        num[arr[x]]=-1;
        used[i]=0;
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n;
    cin>>A>>B>>C;
    for(int i=n-1;i>=0;i--) {
        if(num[A[i]]!=-1) num[A[i]]=-1, arr[++np]=A[i];
        if(num[B[i]]!=-1) num[B[i]]=-1, arr[++np]=B[i];
        if(num[C[i]]!=-1) num[C[i]]=-1, arr[++np]=C[i];
    }
    dfs(1);
    return 0;
}

Code 1.xs

// Code by ajcxsu
// Problem: worm cac

#include<bits/stdc++.h>
using namespace std;

const int N=60;
int num[600];
char A[N];
char B[N];
char C[N], used[N];
int n;
char arr[N];
int np=0;
void dfs(int x, int p, int t) {
    while(p>=0 && num[A[p]]!=-1 && num[B[p]]!=-1 && num[C[p]]!=-1) {
        if((num[A[p]]+num[B[p]]+t)%n!=num[C[p]]) return;
        t=(num[A[p]]+num[B[p]]+t)/n, p--;
    }
    if(x>np) {
        if(t) return;
        for(int i='A';i<'A'+n;i++) cout<<num[i]<<" \n"[i=='A'+n-1];
        exit(0);
    }
    if(num[arr[x]]!=-1) { dfs(x+1, p, t); return; }
    if(num[A[p]]!=-1 && num[B[p]]!=-1 && num[C[p]]==-1) {
        if(used[(num[A[p]]+num[B[p]]+t)%n]) return;
        num[C[p]]=(num[A[p]]+num[B[p]]+t)%n, t=(num[A[p]]+num[B[p]]+t)/n;
        used[num[C[p]]]=1;
        dfs(x, p-1, t);
        used[num[C[p]]]=0, num[C[p]]=-1;
        return;
    }
    for(int i=n-1;i>=0;i--) if(!used[i]) {
        used[i]=1;
        num[arr[x]]=i;
        dfs(x+1, p, t);
        num[arr[x]]=-1;
        used[i]=0;
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n;
    cin>>A>>B>>C;
    for(int i=n-1;i>=0;i--) {
        if(num[A[i]]!=-1) num[A[i]]=-1, arr[++np]=A[i];
        if(num[B[i]]!=-1) num[B[i]]=-1, arr[++np]=B[i];
        if(num[C[i]]!=-1) num[C[i]]=-1, arr[++np]=C[i];
    }
    dfs(1, n-1, 0);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1092.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆