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

思路

先考虑每一位要满足什么情况才可能出现在竖式里。

假设当前位的三个数分别为 $a,b,c$，首先 $a+b=c$ 肯定满足，然后假如进了一位，就要满足 $a+b-10=c$。

因为是加法，所以进位最多为 1，那么需要进位才能满足的有 $a+b+1=c,a+b-9=c$。

然后设 $p_i$ 表示当前位是否进位，$q_i$ 表示当前位是否需要进位。

从前往后遍历每一位，维护 $cnt$ 表示当前有多少个可以作为开头的位，$now$ 表示前一个位需要进位。

具体实现过程看代码，细节比较多。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string a,b,c; 
int vis[1000010],p[1000010],q[1000010];//vis[i]:该位是否合法;p[i]:是否向高位进位;q[i]:是否需要低位进位
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>a>>b>>c;
	int n=a.size();
	a=" "+a;b=" "+b;c=" "+c;//下标从1开始
	for(int i=1;i<=n;i++){//预处理每一位的进位状态
		if(a[i]-'0'+b[i]-'0'==c[i]-'0'){//无进位输入,无进位输出
			vis[i]=1;
			p[i]=0;
			q[i]=0;
		} 
		else if(a[i]-'0'+b[i]-'0'+1==c[i]-'0'){//有进位输入,无进位输出
			vis[i]=1;
			p[i]=0;
			q[i]=1;
		}
		else if(a[i]-'0'+b[i]-'0'-10==c[i]-'0'){//无进位输入,有进位输出
			vis[i]=1;
			p[i]=1;
			q[i]=0;
		}
		else if(a[i]-'0'+b[i]-'0'+1-10==c[i]-'0'){//有进位输入,有进位输出
			vis[i]=1;p[i]=1;q[i]=1;
		}
	}
	ll ans=0,cnt=0,now=0;//ans:总答案;cnt:以i为右端点的合法左端点数;now:候选左端点集合是否需要i产生进位
	for(int i=1;i<=n;i++){//i作为右端点,从左到右枚举
		if(!vis[i]){//当前位不合法,状态清零
			cnt=now=0;
		}
		else{
			if(p[i]==0&&q[i]==0){//i不产进位也不需进位
				if(!now){//候选集合不需要进位,进位链连贯
					cnt++;//i可作为新左端点
				}
				else{//候选集合需要进位,但i不产进位,链断开
					cnt=1;//之前的左端点失效,i作为新左端点
					now=0;//更新状态
				}
				ans+=cnt;//q[i]=0,i可作为右端点,累加答案
			}
			else if(p[i]==0&&q[i]==1){//i需进位但不产进位
				if(!now){//候选集合不需要进位
					cnt++;//i可作为新左端点
					now=1;//标记候选集合需要i+1产生进位
				}
				else{//候选集合需要进位,但i不产进位,链断开
					cnt=1;//之前的左端点失效,i作为新左端点(now保持为1)
				}
				
			}
			else if(p[i]==1&&q[i]==0){//i产进位但不需进位
				if(now){//候选集合需要进位,i正好产生进位,链连贯
					ans+=cnt;//q[i]=0,i可作为右端点,累加答案
					now=0;//候选集合不再需要进位
				}
				else{//候选集合不需要进位,但i产进位,链断开(最高位不能产进位)
					cnt=0;//候选左端点全部失效
				}
			}
			else if(p[i]==1&&q[i]==1){//i需进位且产进位
				if(!now){//候选集合不需要进位,但i需要进位,链断开
					cnt=now=0;//候选左端点失效
				}
				//若now=1,候选集合需要进位,i产进位满足需求,且i还需进位,now保持1,cnt不变
			}
		}
	}
	cout<<ans;
	return 0;
}

思路

设三串数字为 $a、b、c$，那么 $now_i$ 就 $a_i+b_i$。

对于 $a_i+b_i$ 有两种情况，要么是不进位要么是进位。

此时我们发现：对于每个合法区间 $(l,r)$，$l,r$ 之间的每一位都是情况 1 或情况 2，且第 $l$ 位一定不会进位，第 $r$ 位一定是情况 2。

最后要注意处理前一位没有进位时如果 $now_i$ 是 $9$ 要做进位处理。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
string a,b,c;
int ans,w,s;
signed main(){
    cin>>a>>b>>c;
    for(int i=a.size()-1;i>=0;--i){
        int now=a[i]-'0'+b[i]-'0',h=c[i]-'0';
        if(now>=10||(now==9&&w==1&&h==0)){
            if(now%10==h){
                if(w==1){
                    s=1;
                }
                else{
                    ++s;
                }
                w=1;
            }
            else if((now+1)%10==h&&w==1){
                w=1;
            }
            else{
                s=0;
                w=0;
            }
        }
        else{
            if(now%10==h){
                if(w==1){
                    s=1;
                    ans+=s;
                }
                else{
                    ++s;
                    ans+=s;
                }
                w=0;
            }
            else if((now+1)%10==h&&w==1)
            {
                ans+=s;
                w=0;
            }
            else
            {
                s=0;
                w=0;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

结语

感谢大家的观看和管理员的审核，祝大家在算法竞赛的道路上越走越远！