Codeforces 898F

传送门：Codeforces 898F

题意

给一个只有数字的字符串，让你在其中插入“+”和“=”，将其分成三部分a，b，c（不含前导零），使得a+b=c。输出这个等式。

题解

设a，b，c的长度分别为lena，lenb，lenc。因为a+b=c，所以lena和lenb中至少有一个为lenc或者lenc-1，并且lena<=lenc，lenb<=lenc。我们可以枚举lenc，对每个lenc而言，lena，lenb可能有四种取值，如果直接判断a+b=c的话会TLE，所以想到hash，如果hash(a)+hash(b)=hash(c)，那么再去判断a+b是否等于c，或者可以直接认为a+b=c（这道题没有产生冲突）。

注

1、判断是否有前导零
2、一开始根据蓝书上将base设置成了131，然后一直wa，因为a+b=c这个等式中是十进制的，那么如果将base设置成131，当加法中产生了进位，就会出错。所以base只能设置成10，并且需要取mod=1e9+7，如果用unsigned long long的自然溢出会TLE。

代码1

直接判断hash(a)+hash(b)=hash(c)

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N=1e6+10;
const ull base=10;
const ull mod=1e9+7;
ull f[N],p[N];

char s[N];
int len,idx0,idx1;
char s1[N],s2[N],s3[N];

void Hash(char *s){
    p[0]=1;
    for(int i=1;i<=len;i++){
        f[i]=(f[i-1]*base+s[i]-'0')%mod;
        p[i]=p[i-1]*base%mod;
    }
}

bool solve(int la,int lb,int lc){
    if(la<1||lb<1||lc<1) return 0;
    if(la>lc||lb>lc) return 0;
    if(s[la+1]=='0'&&lb!=1) return 0;
    ull ha,hb,hc;
    ha=f[la]%mod;
    hb=(f[la+lb]-f[la]*p[lb]%mod+mod)%mod;
    hc=(f[len]-f[la+lb]*p[lc]%mod+mod)%mod;
    if((ha+hb)%mod==hc){
        idx0=la;
        idx1=la+lb;
        return 1;
    }
    return 0; 
}

int main(){
    scanf("%s",s+1);
    len=strlen(s+1);
    Hash(s);
    //枚举c的长度 
    for(int i=1;2*i<=len;i++){
        if(s[len-i+1]=='0'&&i!=1) continue;
        
        if(solve(i,len-2*i,i)) break;
        if(solve(i-1,len-2*i+1,i)) break;
        if(solve(len-2*i,i,i)) break;
        if(solve(len-2*i+1,i-1,i)) break;
    }
    for(int i=1;i<=idx0;i++) printf("%c",s[i]);
    printf("+");
    for(int i=idx0+1;i<=idx1;i++) printf("%c",s[i]);
    printf("=");
    for(int i=idx1+1;i<=len;i++) printf("%c",s[i]);
    printf("\n");
    return 0;
}

代码2

hash完之后再判断a+b=c

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N=1e6+10;
const ull base=10;
const ull mod=1e9+7;
ull f[N],p[N];

char s[N];
int len,idx0,idx1;
char s1[N],s2[N],s3[N];

void Hash(char *s){
    p[0]=1;
    for(int i=1;i<=len;i++){
        f[i]=(f[i-1]*base+s[i]-'0')%mod;
        p[i]=p[i-1]*base%mod;
    }
}

bool check(int la,int lb,int lc){
    int d=0;
    int pos0=la,pos1=la+lb;
    while(la>=1&&lb>=1){
        int x=s1[la]-'0',y=s2[lb]-'0';
        int s=s3[lc]-'0';
        int sum=x+y+d;
        if(sum>=10) d=1,sum-=10;
        else d=0;
        if(sum!=s) return 0;
        la--;lb--;lc--;
    }
    while(la>=1){
        int x=s1[la]-'0';
        int s=s3[lc]-'0';
        x+=d;
        if(x>=10) d=1,x-=10;
        else d=0;
        if(x!=s) return 0;
        la--;lc--;
    }
    while(lb>=1){
        int x=s2[lb]-'0';
        int s=s3[lc]-'0';
        x+=d;
        if(x>=10) d=1,x-=10;
        else d=0;
        if(x!=s) return 0;
        lb--;lc--;
    }
    idx0=pos0;idx1=pos1;
    return 1;
}


bool solve(int la,int lb,int lc){
    if(la<1||lb<1||lc<1) return 0;
    if(la>lc||lb>lc) return 0;
    if(s[la+1]=='0'&&lb!=1) return 0;
    ull ha,hb,hc;
    ha=f[la]%mod;
    hb=(f[la+lb]-f[la]*p[lb]%mod+mod)%mod;
    hc=(f[len]-f[la+lb]*p[lc]%mod+mod)%mod;
    if((ha+hb)%mod==hc){
        for(int i=1;i<=la;i++) s1[i]=s[i]; s1[la+1]='\0';
        for(int i=1;i<=lb;i++) s2[i]=s[i+la]; s2[lb+1]='\0';
        for(int i=1;i<=lc;i++) s3[i]=s[i+la+lb]; s3[lc+1]='\0'; 
        if(check(la,lb,lc)) return 1;
    }
    return 0; 
}

int main(){
    scanf("%s",s+1);
    len=strlen(s+1);
    Hash(s);
    for(int i=1;2*i<=len;i++){
        if(s[len-i+1]=='0'&&i!=1) continue;
        
        if(solve(i,len-2*i,i)) break;
        if(solve(i-1,len-2*i+1,i)) break;
        if(solve(len-2*i,i,i)) break;
        if(solve(len-2*i+1,i-1,i)) break;
    }
    for(int i=1;i<=idx0;i++) printf("%c",s[i]);
    printf("+");
    for(int i=idx0+1;i<=idx1;i++) printf("%c",s[i]);
    printf("=");
    for(int i=idx1+1;i<=len;i++) printf("%c",s[i]);
    printf("\n");
    return 0;
}

Codeforces 898F

原文：https://www.cnblogs.com/qjy73/p/12465496.html