题解：P15983 [PA 2026] 列竖式 / Dodawanie

· · 题解

本文中规定，进位指向左进一位，而被进位指从右向被进了一位。如，13+17=30，我们就说第 1 位数被进了一位，第 2 位数进了一位。

对于每一位数，设两个加数对应位之和为 s，和的对应位为 c。若 c=s\bmod 10，则这一位数没有被进位，且向前进了一位。若 c=(s+1)\bmod 10，则这一位数被进了一位，这一位还要向左进 \lfloor(s+1)/10\rfloor 位。若两种情况都不满足，则这一位数显然无效，也就方案数为 0 了。

令 q_i=\lfloor(s_i+1)/10\rfloor，r_i 为第 i 位数从右边获得的进位数量。对于一个合法的区间 [i,j]，必须满足左端 q_i=0、右端 r_j=0，且区间内部相邻位数的进位匹配。

于是我们可以从左向右扫描，维护一个计数器 c 表示当前连续且进位匹配的区域内满足 q_i=0 的位置数量，即合法区间的左端点数。如果当前位无效或进位与前一位无法匹配，就清空 c；如果当前位 q=0，便将 c 加一；如果当前位 r=0，则将 c 累加到答案中。这样每个合法区间恰好在其右端点被统计一次，这道题也就做完了。

代码如下。

#include<bits/stdc++.h>
using namespace std;
string a,b,c;
int n,cnt,pre=-1;
long long ans=0;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>a>>b>>c;
    n=a.size();
    for(int i=0;i<n;i++){
        int s=a[i]-'0'+b[i]-'0',d=c[i]-'0';
        int r,q;
        if(d==s%10) r=0,q=s/10;
        else if(d==(s+1)%10) r=1,q=(s+1)/10;
        else{
            cnt=0;
            pre=-1;
            continue;
        }
        if(pre!=-1&&q!=pre) cnt=0;
        if(q==0) cnt++;
        if(r==0) ans+=cnt;
        pre=r;
    }
    cout<<ans;
    return 0;
}