[AtCoder ABC-198D] Send More Money（map用法）题解

D – Send More Money

Time Limit: 5 sec / Memory Limit: 1024 MB

Problem Statement

Given strings S1,S2,S3,S1,S2,S3 consisting of lowercase English letters, solve the alphametic S1+S2=S3

Formally, determine whether there is a triple of positive integers N1,N2,N3 satisfying all of the three conditions below, and find one such triple if it exists.
Here, N′1,N′2,N′3 are strings representing N1,N2,N3(without leading zeros) in base ten, respectively.

• N′i and Si have the same number of characters.
• N1+N2=N3.
• The x-th character of Si and the y-th character of Sj is the same if and only if the x-th character of N′i and the y-th character of N′j are the same.

Constraints

• Each of S1, S2, S3 is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S1
S2
S3

Output

If there is a triple of positive integers N1,N2,N3 satisfying the conditions, print one such triple, using newline as a separator. Otherwise, print UNSOLVABLE instead.

Sample Input 1

a
b
c

Sample Output 1

1
2
3

Outputs such as (N1,N2,N3)=(4,5,9) will also be accepted, but (1,1,2)will not since it violates the third condition (both a and b correspond to 1).

Sample Input 2

x
x
y

Sample Output 2

1
1
2

Outputs such as (N1,N2,N3)=(3,3,6)will also be accepted, but (1,2,3)will not since it violates the third condition (both 1 and 2 correspond to x).

Sample Input 3

p
q
p

Sample Output 3

UNSOLVABLE

Sample Input 4

abcd
efgh
ijkl

Sample Output 4

UNSOLVABLE

Sample Input 5

send
more
money

Sample Output 5

9567
1085
10652

题目大意

输入三个字符串s1、s2、s3，字符串中的每个不同的字符代表一种数字。例如（aab可代表110（一百一十）或221、223等）。

要求：替换后的数值num1+num2  = num3。

问：能不能找到这么一种字符-数字的替换方式，使得要求被满足？能的话，输出num1、num2、num3。不能的话输出UNSOLVABLE。

思路

利用map容器存储字符-数字的对应关系，用回溯法遍历所有的对应关系。判断找出满足条件且合法的对应关系。最后对应输出。

重点

使用set 容器用来确保每个不同种类的字母能有不同的对应数字。

判断数值是否合法。

数值高位换低位。

AC代码

#include<set>
#include<map>
#include<string>
#include<iostream>
using namespace std;
int s;
map<char,int> a,ans;
map<char,int>::iterator it;
set<int> b;
string s1,s2,s3;
//判断s3字符串最后得到的数合不合法？
int check()
{
    int t=0;
    //判断三个最后输出数首位是否为0？
    if(a[s1[s1.length()-1]]==0||a[s2[s2.length()-1]]==0||a[s3[s3.length()-1]]==0){
        return 0;
    }
    //判断s3的每一位是否等于相应位的s1,s2之和。
    for(int i=0;i<s3.length();i++)
    {
        int g=a[s1[i]]+a[s2[i]]+t;
        if(g%10!=a[s3[i]]) return 0;
        t=g/10;
    }
    //判断最后的进位是否为0，也就是判断s3的长度够不够？
    if(t) return 0;
    return 1;
}
//回溯法遍历所有字母替换数字的可能。但是时间最坏不是10^10吗？超限？
void fun(int i)
{
    if(i>=s)
    {
        if(check())
        {
            ans=a;
        }
        return;
    }
    if(!ans.empty()) return;
    for(int j=0;j<=9;j++)
    {
        if(b.find(j)==b.end())
        {
            it->second=j;it++;
            b.insert(j);
            fun(i+1);
            b.erase(j);it--;
        }
    }
}
int main()
{
    
    cin>>s1>>s2>>s3;
    
    for(int i=0;i<s1.length()/2;i++) swap(s1[i],s1[s1.length()-1-i]);
    for(int i=0;i<s2.length()/2;i++) swap(s2[i],s2[s2.length()-1-i]);
    for(int i=0;i<s3.length()/2;i++) swap(s3[i],s3[s3.length()-1-i]);
    
    //数值高位换低位，便于后续操作
    for(int i=0;i<s1.length();i++) a[s1[i]]=-1;
    for(int i=0;i<s2.length();i++) a[s2[i]]=-1;
    for(int i=0;i<s3.length();i++) a[s3[i]]=-1;
    it=a.begin();

    s=a.size();
    a['\0']=0;
    //超过10个字母总数，则可直接输出不能解决
    if(s<=10)
    fun(0);
    if(!ans.empty())
    {
        for(int i=s1.length()-1;i>=0;i--)
        {cout<<ans[s1[i]];}cout<<endl;
        for(int i=s2.length()-1;i>=0;i--)
        {cout<<ans[s2[i]];}cout<<endl;
        for(int i=s3.length()-1;i>=0;i--)
        {cout<<ans[s3[i]];}cout<<endl;
    }
    else
    {
        cout<<"UNSOLVABLE"<<endl;
    }
    return 0;
}