【杭电多校第七场】A + B = C

原题：

Given a,b,c, find an arbitrary set of x,y,z such that a*10^x+b*10^y=c*10^z and 0≤x,y,z≤10^6.

给你三个高精度数a、b、c，要求找出任意一组x、y、z满足a*10^x+b*10^y=c*10^z

首先需要发现一个性质

乘上10的幂会往数的最后面填上0，而不会对最前面的位造成影响

一开始我的思路是考虑三个数的个位，这种就很麻烦了

（听说能忽略前导零然后讨论，但我总觉得是假做法）

考虑前面位的话，就只有几种情况：

①a、b、c对齐

②a和b对齐，然后相加进一位，然后和c对齐

③a和c对齐，b在中间

④a加上b进一位和c对齐

⑤⑥同③④

（注意重要性质：加法最多只会进1，最多增加1位）

前两个可以a+b然后判断

后两个可以c-a然后判断

（这里的a、b、c都是指对齐过的）

所有情况都判断一下找到一组解就vans了

接下来就是喜闻乐见的码农时间

因为情况比较多，所以用工具函数，数组作为参数，以a[0]作为a的长度，这样是非常舒服的

一开始写的是二分，即a和c对齐后二分b左移的位数

但是又100组数据，1e6*log1e6*100肯定T了

实际上不用二分，直接减然后判断是比较简单的

另外，第一次写的时候左移是用函数里的参数控制的，这样写前两个还好，后四个情况再带上减法会及其麻烦

写到后期把减法加进去后代码直接崩溃了，前言不搭后语

最后额外开三个高精度数，写一个左移函数，用函数额外的一个参数表示高精度运算过后的结果放到哪里

这样写下来一气呵成，很顺利

所以说代码自动化和通用工具函数还是很有用的

（一开始写屎的锅就是因为中午没睡一脸蒙蔽=。=）

总结经验：
1.有时候不要贪图局部的代码方便

尤其是不要偷懒，为了想起来简单而放弃写通用函数

2.结构化程序设计（或者工具函数、代码自动化）带来的加成是惊人的

甚至可以为了这些放弃别的东西，比如代码复杂度，比如常数

3.敢于重构代码

又一个实例证明重构利大于弊

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int a[],b[],c[],d[];

 int e[],f[],g[];

 void clr(int x[]){

     for(int i=;i<=x[];++i)  x[i]=;

     x[]=;

 }

 void rvs(int x[]){

     clr(d);

     d[]=x[];

     for(int i=;i<=d[];++i)  d[i]=x[i];

     for(int i=;i<=d[];++i)  x[i]=d[d[]-i+];

 }

 void rd(int x[]){

     clr(x);

     char ch=getchar();

     while(ch<''||ch>'')  ch=getchar();

     while(ch>=''&&ch<=''){

         x[++x[]]=ch-'';

         ch=getchar();

     }

     rvs(x);

 }

 void cpy(int x[],int y[]){

     clr(y);

     y[]=x[];

     for(int i=;i<=x[];++i)  y[i]=x[i];

 }

 void lm(int x[],int y,int z[]){

     cpy(x,z);

     for(int i=z[];i>=;--i)  z[i+y]=z[i];

     for(int i=;i<=y;++i)  z[i]=;

     z[]+=y;

 }

 void pls(int x[],int y[],int z[]){

     clr(z);

     z[]=max(x[],y[]);

     for(int i=;i<=x[];++i)  z[i]+=x[i];

     for(int i=;i<=y[];++i)  z[i]+=y[i];

     for(int i=;i<=z[];++i)if(z[i]>=){

         z[i+]+=z[i]/;

         z[i]%=;

     }

     if(z[z[]+])  ++z[];

 }

 void mns(int x[],int y[],int z[]){

     cpy(x,z);

     for(int i=;i<=z[];++i){

         z[i]-=y[i];

         if(z[i]<){

             z[i]+=;

             --z[i+];

         }

     }

     while(!z[z[]])  --z[];

 }

 int cmp(int x[],int y[]){

     if(x[]<y[])  return -;

     if(x[]>y[])  return ;

     for(int i=x[];i>=;--i){

         if(x[i]<y[i])  return -;

         if(x[i]>y[i])  return ;

     }

     return ;

 }

 void ot(int x,int y,int z){

     int mn=min(x,min(y,z));

     printf("%d %d %d\n",x-mn,y-mn,z-mn);

 }

 int chck(int x[],int y[]){

     if(x[]<y[])  return -;

     for(int i=y[],j=x[];i>=;--i,--j)

         if(y[i]!=x[j])  return -;

     for(int i=;i<=y[]-x[];++i)

         if(x[i])  return -;

     return x[]-y[];

 }

 void gogogo(){

     int mxl=max(a[],max(b[],c[]));

     lm(a,mxl-a[],e),lm(b,mxl-b[],f),lm(c,mxl-c[],g);

     pls(e,f,d);

     if(!cmp(d,g)){

         ot(mxl-a[],mxl-b[],mxl-c[]);

         return ;

     }

     lm(c,mxl-c[]+,g);

     if(!cmp(d,g)){

         ot(mxl-a[],mxl-b[],mxl-c[]+);

         return ;

     }

     int tmx=max(a[]+b[],c[])+b[]-;

     lm(a,tmx-a[],e),lm(b,tmx-b[],f),lm(c,tmx-c[],g);

     if(cmp(g,e)==){

         mns(g,e,d);

         int tmp=chck(d,b);

         if(tmp!=-){

             ot(tmx-a[],tmp,tmx-c[]);

             return ;

         }

     }

     if(cmp(g,f)==){

         mns(g,f,d);

         int tmp=chck(d,a);

         if(tmp!=-){

             ot(tmp,tmx-b[],tmx-c[]);

             return ;

         }

     }

     lm(c,tmx-c[]+,g);

     if(cmp(g,e)==){

         mns(g,e,d);

         int tmp=chck(d,b);

         if(tmp!=-){

             ot(tmx-a[],tmp,tmx-c[]+);

             return ;

         }

     }

     if(cmp(g,f)==){

         mns(g,f,d);

         int tmp=chck(d,a);

         if(tmp!=-){

             ot(tmp,tmx-b[],tmx-c[]+);

             return ;

         }

     }

     printf("-1\n");

 }

 void prvs(){

     clr(a),clr(b),clr(c),clr(d);

 }

 int main(){

     freopen("ddd.in","r",stdin);

     a[]=,b[]=,c[]=,d[]=;

     int T;  cin>>T;

     while(T --> ){

         prvs();

         rd(a),rd(b),rd(c);

         gogogo();

     }

     return ;

 }

巴特西

【杭电多校第七场】A + B = C

最新文章

热门文章