题解：CF625D Finals in arithmetic

不知道为啥其他题解的代码如此长。

下设

s

为数，

n=len(s)

。

有两种情况：

$len(a)=n$ 。那么 $a_1+a_n$ 没有进位。因此通过 $s_n$ 得出了他们的和。如果现在 $s_1=s_n$ ，说明 $a_2+a_{n-1}$ 没有进位，否则进了，……，以此类推。
$len(a)=n-1$ 。类似的， $a_1+a_n$ 进位了。也可以依次递推。

CPP

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5+5;

int n,a[N],b[N],c[N];
string s;

bool chk(int len){
    if (b[1]==0) return 0;
    for (int i=1; i<=len; i++){
        if (!(0<=b[i] && b[i]<=9)) return 0;
    }
    for (int i=1; i<=len; i++){
        c[i]=b[i]+b[len-i+1];
    }
    for (int i=len; i; i--){
        if (c[i]>=10){
            c[i-1]+=c[i]/10;
            c[i]%=10;
        }
    }
    for (int i=1; i<=n; i++){
        if (c[i-(n-len)]!=s[i]-'0') return 0;
    }
    return 1;
}

void sol(int len){
    int l=1,r=len;
    while (l<=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]){
            return;
        }
        if (l==r && a[l]%2){
            return;
        }
        int x=(a[l]+1)/2;
        b[l]=x;
        b[r]=a[l]-x;
        l++,r--;
    }
    if (chk(len)){
        for (int i=1; i<=len; i++){
            cout<<b[i];
        }
        cout<<"\n";
        exit(0);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>s;
    n=s.size();
    s=" "+s;
    for (int i=1; i<=n; i++){
        a[i]=s[i]-'0';
    }
    sol(n);
    if (s[1]=='1' && n!=1){
        for (int i=1; i<n; i++){
            a[i]=s[i+1]-'0';
        }
        a[1]+=10;
        sol(n-1);
    }
    cout<<"0\n";
    return 0;
}

题解：CF625D Finals in arithmetic

文章操作

相关推荐

评论

题解：CF625D Finals in arithmetic