GREAT + SWERC = PORTO(UVALive – 6884)

题目链接:https://cn.vjudge.net/problem/UVALive-6884
题目大意:给出n个由字母组成的数字,每个字母对应一个数字,不得有多个字母对应一个数字,要前n-1个数字的值相加等于第n个数的值,(每个数字都不得有前导零)求有多少种方案满足条件
解题思路:dfs暴力,比赛时以为是一道数论数学题,因为当时感觉暴力的话时间复杂度太高了,但后来一想,不同的字母最多可以同时存在10个 ,也不是很大
代码

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

char a[20][20];
int vis[30],p[30],book[30],num[30];
int cnt;
int ans;
int n,len;

int yes()
{
    int f=1;
    for(int i=0;i<n;i++)
    {
        if(num[a[i][0]-'A']==0)
        {
            f=0;
        }
    }
    if(f==0)return 0;
    long long sum=0,l=0;
    long long cheng=1;
    for(int i=0;i<n-1;i++)
    {
        len=strlen(a[i]);
        cheng=1;
        for(int j=len-1;j>=0;j--)
        {
            sum+=num[a[i][j]-'A']*cheng;
            cheng*=10;
        }
    }
    len=strlen(a[n-1]);
    cheng=1;
    for(int i=len-1;i>=0;i--)
    {
        l+=num[a[n-1][i]-'A']*cheng;
        cheng*=10;
    }
    if(l==sum)return 1;
    else return 0;
}

void dfs(int x)
{
    if(x==cnt)
    {
        if(yes())
            ans++;
        return;
    }
    else
    {
        for(int i=0;i<10;i++)
        {
            if(!book[i])
            {
                book[i]=1;
                num[p[x]]=i;
                dfs(x+1);
                book[i]=0;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        memset(vis,0,sizeof(vis));
        cnt=0;
        ans=0;
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
            len=strlen(a[i]);
            for(int j=0; j<len; j++)
            {
                if(!vis[a[i][j]-'A'])
                  {
                      vis[a[i][j]-'A']=1;
                      p[cnt++]=a[i][j]-'A';
                  }
            }
        }
        memset(book,0,sizeof(book));
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注