欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

GREAT + SWERC = PORTO UVALive - 6884 Regionals 2014 >> Europe - Southwestern

程序员文章站 2022-06-02 17:46:53
...

vj题目链接

原题题目链接

GREAT + SWERC = PORTO UVALive - 6884 Regionals 2014 >> Europe - SouthwesternGREAT + SWERC = PORTO UVALive - 6884 Regionals 2014 >> Europe - Southwestern


blablabla: 十分扎心的一道dfs。。。。       扎心的就是因为当时没debug 。。。没发现数组开小了

要是能及时A掉就不是倒一了啊=  =

扎铁了老心

tho: 先dfs给已出现的字母分配数字,然后判断一下前n个字符串变成的数的和是否等于最后一个变成的数的和。注意要判断前导0;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(x) memset(x,0,sizeof(x))
using namespace std;
int n,o,ans;
char s[15][15];
int book[15] ,f[35],p[35], a[35];
int change(char te[]) //将一个字符串转换成数字;
{
    int len = strlen(te),sum=0;
    if(a[te[0]-'A']==0)  return -1;
    int mu=1;
    for(int i=len-1;i>=0;i--)
    {
        sum+=mu*a[te[i]-'A'];
        mu*=10;
    }
    return sum;
}
bool whe()  //判断前n-1个数的和是否等于最后一个数
{
    int pre=0,sum=0;
    for(int i=0;i<n-1;i++)
    {
        if(change(s[i])!=-1)//判断前导0
            pre+=change(s[i]);
        else
            return false;
    }
    if(change(s[n-1])!=-1)//判断前导0
        sum+=change(s[n-1]);
    else
        return false;
    if(sum == pre) return true;
    else return false;
}
void dfs(int step)//赋值
{
    if(step >= o)
    {
        if(whe()) ans++;
        return ;
    }
    for(int i=0;i<10;i++)
    {
        if(book[i]==0)
        {
            a[p[step]] = i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
    return ;
}
int main()
{
    while(cin>>n)
    {
        ms(f);
        ms(book);
        ms(a);
        ms(p);
        o=0, ans=0;
        for(int i=0;i<n;i++)
        {
            scanf("%s",s[i]);
            int len = strlen(s[i]);
            for(int j=0;j<len;j++)
            {
                f[s[i][j]-'A']=1;
            }
        }
        for(int i=0;i<=25;i++)
        {
            if(f[i]) p[o++]=i;
        }
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}