题解 CF625D 【Finals in arithmetic】

开始新的记忆 · 2019-08-04 13:19:47 · 题解

此题看起来比较烦，其实只要把进位的关系和方法搞清楚就行

具体看代码：

#include<bits/stdc++.h>
using namespace std;
char s[100010];
int a[100010],ans[100010];

int main()
{   memset(a,0,sizeof(a));
    memset(ans,0,sizeof(ans));
    scanf("%s",&s);
    int n=strlen(s);
    for(int i=1;i<=n;i++)//转成数字 
        a[i]=s[i-1]-'0';
    int l=1,r=n,flag=1;
    if(a[l]!=a[r])//判断第一位是否为1，可能是进位产生 
    {
        a[l]--;
        a[l+1]+=10;
        if(a[l]==0) 
            l++;
    }
    while(l<=r)//判断是否回文并处理进位 
    {
        if(a[l]!=a[r]) //有进位 
        {
            if(a[l]-a[r]>=10)//后一位进位了 
            {
                a[r]+=10;
                a[r-1]--;
            }
            if(a[l]-a[r]==1)//从前一位进位 
            {
                a[l]--;
                a[l+1]+=10;
            }
        }
        if(a[l]!=a[r])//没有相等，没法回文，得不到答案 
        {
            flag=0;
            break;
        }
        if(l!=r)//算答案，因为a[r]/2是向下取整，所以ans[l]>=ans[r]，不会出现前置0的情况 
        {
            ans[l]=a[l]-a[r]/2;
            ans[r]=a[r]/2;
        }
        else//判断中间位 
        {
            if(a[l]&1)//中间不可能为奇数 
            {
                flag=0;
                break;
            }
            ans[l]=a[r]/2;
        }
        if(ans[l]<0 || ans[l]>9 || ans[r]<0 || ans[l]>9)//判断ans有没有超过边界 
        {
            flag=0;
            break;
        }
        l++;r--;//向中间靠拢 
    }
    if(flag==0 || l<=r)//没有答案 
    {
        printf("0\n");
        return 0;
    }
    int cnt=1;
    while(ans[cnt]==0)//开头因为可能因为进位造成1，所以可能第一位没有数字 
        cnt++;
    for(int i=cnt;i<=n;i++)//输出 
        printf("%d",ans[i]);
    printf("\n");
    return 0;
}