HDU6646 A + B = C

题意

给三个数a，b，c，问是否存在(a*10^n+b*10^m=c*10^k)。
题目链接

思路

将a，b，c末尾的零去掉得到A，B，C，考虑几种情况，其中(n,m,k>0)。

1. (A*10^n+B=C*10^k)不合法
2. (A+B*10^m=C*10^k)不合法
3. (A*10^n+B*10^m=C)不合法
4. (A+B=C*10^k)
5. (A*10^n+B=C)
6. (A+B*10^m=C)
7. (A+B=C)

对于5，6，7三种情况，尝试用C-A，C-B，看是否能与另一个匹配。对于4，用A+B看是否于C匹配。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000+10;

int na,nb,nc,nd;
char s[maxn];
int a[maxn],b[maxn],c[maxn],d[maxn];
int numa,numb,numc;

bool xiao(int a[],int na,int b[],int nb)
{
    if (na<nb) return 1;
    if (na>nb) return 0;
    for (int i=na-1;i>=0;i--)
    {
        if (a[i]<b[i]) return 1;
        if (a[i]>b[i]) return 0;
    }
    return 0;
}

void jian(int a[],int na,int b[],int nb)
{
    nd=na;
    memset(d,0,sizeof(d));
    int o=0;
    for (int i=0;i<na;i++)
    {
        d[i]=(a[i]+o-b[i]+10)%10;
        if (a[i]+o-b[i]<0) o=-1; else o=0;
    }
    while (nd>1&&d[nd-1]==0) nd--;
}

void add(int a[],int na,int b[],int nb)
{
    nd=max(na,nb);
    memset(d,0,sizeof(d));
    int o=0;
    for (int i=0;i<nd;i++)
    {
        d[i]=(a[i]+b[i]+o)%10;
        o=(a[i]+b[i]+o)/10;
    }
    if (o) d[nd++]=1;
}

bool cmp(int a[],int la,int ra,int b[],int lb,int rb)
{
    if (ra-la!=rb-lb) return 0;
    for (int i=0;i<ra-la;i++)
    {
        if (a[la+i]!=b[lb+i]) return 0;
    }
    return 1;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        memset(a,0,sizeof(a)); numa=0;
        memset(b,0,sizeof(b)); numb=0;
        memset(c,0,sizeof(c)); numc=0;
        scanf("%s",s);
        na=strlen(s);
        while (na>1&&s[na-1]=='0') na--,numa--;
        for (int i=0;i<na;i++) a[i]=s[na-i-1]-'0';

        scanf("%s",s);
        nb=strlen(s);
        while (nb>1&&s[nb-1]=='0') nb--,numb--;
        for (int i=0;i<nb;i++) b[i]=s[nb-i-1]-'0';

        scanf("%s",s);
        nc=strlen(s);
        while (nc>1&&s[nc-1]=='0') nc--,numc--;
        for (int i=0;i<nc;i++) c[i]=s[nc-i-1]-'0';

        int tmp,p;
        if (xiao(b,nb,c,nc))
        {
            jian(c,nc,b,nb);
            p=0;
            while (d[p]==0) p++;
            if (cmp(a,0,na,d,p,nd))
            {
                numa+=p;
                tmp=min(min(numa,numb),numc);
                if (tmp<0) numa-=tmp,numb-=tmp,numc-=tmp;
                printf("%d %d %d
",numa,numb,numc);
                continue;
            }
        }

        if (xiao(a,na,c,nc))
        {
            jian(c,nc,a,na);
            p=0;
            while (d[p]==0) p++;
            if (cmp(b,0,nb,d,p,nd))
            {
                numb+=p;
                tmp=min(min(numa,numb),numc);
                if (tmp<0) numa-=tmp,numb-=tmp,numc-=tmp;
                printf("%d %d %d
",numa,numb,numc);
                continue;
            }
        }

        add(a,na,b,nb);
        p=0;
        while (d[p]==0) p++;
        if (cmp(c,0,nc,d,p,nd))
        {
            numc+=p;
            tmp=min(min(numa,numb),numc);
            if (tmp<0) numa-=tmp,numb-=tmp,numc-=tmp;
            printf("%d %d %d
",numa,numb,numc);
            continue;
        }

        printf("-1
");
    }
    return 0;
}