洛谷1092 虫食算

开始爆肝题解

题意

给出一个 $N$ 进制加法的竖式，一个大写字母代表一个数字。求每个大写字母代表的数字。

$N\le 26$ 。

题解

直接爆搜。从右往左一次搜各个竖排，如果搜到就退出。

要开 O2 并且优化搜索顺序（就是把每个竖排的第一个数倒叙搜索，可以通过分析数据点得出）才能过，而且 #9 刚好 $1000ms$ ，真是刺激。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

char ch[27];
bool vis[27];
int n,mp[27],s[5][27];

void dfs(int x,int add)
{
    if (!x)
    {
        for (int i=0;i<n;i++) printf("%d ",mp[i]);
        exit(0);
    }
    for (int i=n-1;~i;i--)
    {
        if (mp[s[1][x]]==-1 && vis[i]) continue;
        if (mp[s[1][x]]!=-1 && mp[s[1][x]]!=i) continue;
        int last=mp[s[1][x]]; mp[s[1][x]]=i;
        int lastvis=vis[i]; vis[i]=1;
        int last3,lastvis3;
        for (int j=0;j<n;j++)
        {
            if (mp[s[2][x]]==-1 && vis[j]) continue;
            if (mp[s[2][x]]!=-1 && mp[s[2][x]]!=j) continue;
            int last2=mp[s[2][x]]; mp[s[2][x]]=j;
            int lastvis2=vis[j]; vis[j]=1;
            int sum=i+j+add,cur=sum%n,nxt=sum/n;
            if (mp[s[3][x]]==-1 && vis[cur]) goto back;
            if (mp[s[3][x]]!=-1 && mp[s[3][x]]!=cur) goto back;
            last3=mp[s[3][x]]; mp[s[3][x]]=cur;
            lastvis3=vis[cur]; vis[cur]=1;
            dfs(x-1,nxt);
            mp[s[3][x]]=last3; vis[cur]=lastvis3;
            back:mp[s[2][x]]=last2; vis[j]=lastvis2;
        }
        mp[s[1][x]]=last; vis[i]=lastvis;
    }
}

signed main()
{
    n=read();
    memset(mp,-1,sizeof(mp));
    for (int i=1;i<=3;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<=n;j++) s[i][j]=ch[j]-'A';
    }
    dfs(n,0);
    return 0;
}