• 欢迎光临~

CF1619C Wrong Addition 题解

开发技术 开发技术 2022-07-20 次浏览

似乎没人写记忆化搜索的,我就来一波(当然,写动态规划也是可以的,毕竟记忆化搜索只是动态规划的递归形式,不过蒟蒻太菜了,只想到搜索,而没有一开始就想到动规)。

我们把加法转化成减法,开始分割数字 (c),枚举情况。由于 (b) 是十进制的,所以 (c) 的每一段都由一个或两个数字组成(把这一段组成的数减去 (a) 对应的数字,就能算出 (b) 这一位是多少),至于判别条件很容易想到,详见代码。

为了保险起见,我还加了个记忆化,这样对于不行的情况,遇到可直接剪枝(其实这种橙题根本不需要记忆化,当然写都写了,我也不把它删除)。

Code:

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();return x*w;
}
inline void write(ll x){
	if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll T=read(),a,c,aa[25],cc[25],at,ct,ans[25],t;
bool dp[25][25];
bool dfs(int x,int y){//x:c,y:a
    if(x==ct)return y>=at?1:(dp[x][y]=0);
    if(dp[x][y]==0)return 0;
    if(cc[x+1]-aa[y+1]>=0&&cc[x+1]-aa[y+1]<10){
        ans[++t]=cc[x+1]-aa[y+1];
        if(dp[x+1][y+1]=dfs(x+1,y+1))return 1;
        t--;
    }
    if(x<=ct-2&&cc[x+2]!=0&&cc[x+2]*10+cc[x+1]-aa[y+1]>=0&&cc[x+2]*10+cc[x+1]-aa[y+1]<10){
        ans[++t]=cc[x+2]*10+cc[x+1]-aa[y+1];
        if(dp[x+2][y+1]=dfs(x+2,y+1))return 1;
        t--;
    }
    return dp[x][y]=0;
}
int main(){
    while(T--){
        memset(aa,0,sizeof(aa));
        memset(cc,0,sizeof(cc));
        for(int i=0;i<=23;i++)for(int j=0;j<=23;j++)dp[i][j]=1;
        a=read(),c=read(),at=ct=t=0;
        while(a)aa[++at]=(a+10)%10,a/=10;
        while(c)cc[++ct]=(c+10)%10,c/=10;
        if(dfs(0,0)){
            while(t&&ans[t]==0)t--;
            if(t==0)ans[++t]=0;
            for(int i=t;i>=1;i--)putchar(ans[i]+48);
        }
        else printf("-1");
        putchar('n');
    }
    return 0;
}
程序员灯塔
转载请注明原文链接:CF1619C Wrong Addition 题解
喜欢 (0)