【HDOJ6646】A + B = C（模拟）

题意

 1<=a,b,c<=1e100000

思路：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 #define N  1100000
 11 #define M  4100000
 12 #define fi first
 13 #define se second
 14 #define MP make_pair
 15 #define pi acos(-1)
 16 #define mem(a,b) memset(a,b,sizeof(a))
 17 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 18 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 19 #define lowbit(x) x&(-x)
 20 #define Rand (rand()*(1<<16)+rand())
 21 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 22 #define ls p<<1
 23 #define rs p<<1|1
 24 
 25 const ll MOD=1e9+7,inv2=(MOD+1)/2;
 26       double eps=1e-6;
 27       int INF=1e9;
 28 
 29 char a[N],b[N],c[N];
 30 int A[N],B[N],C[N],t[N],flag,la,lb,lc;
 31 
 32 int read()
 33 {
 34    int v=0,f=1;
 35    char c=getchar();
 36    while(c<48||57<c) {if(c==‘-‘) f=-1; c=getchar();}
 37    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 38    return v*f;
 39 }
 40 
 41 void solve1()
 42 {
 43     int na=0,nc=0;
 44     rep(i,1,1e6+1) A[i]=B[i]=C[i]=t[i]=0;
 45     rep(i,1,1e6-la) A[++na]=0;
 46     per(i,la,1) A[++na]=a[i]-‘0‘;
 47     rep(i,1,1e6-lc) C[++nc]=0;
 48     per(i,lc,1) C[++nc]=c[i]-‘0‘;
 49     int p=1;
 50     per(i,1e6,1)
 51     {
 52         if(C[i]>A[i]) break;
 53         if(C[i]<A[i]){p=0; break;}
 54     }
 55     if(!p) return;
 56     rep(i,1,1e6)
 57     {
 58         t[i]=t[i]+C[i]-A[i];
 59         if(t[i]<0)
 60         {
 61             t[i+1]--;
 62             t[i]+=10;
 63         }
 64     }
 65     p=1;
 66     int k=1e6;
 67     while(k>1&&t[k]==0) k--;
 68     per(i,k/2,1) swap(t[i],t[k-i+1]);
 69     rep(i,1,lb)
 70      if((b[i]-‘0‘)!=t[i]){p=0; break;}
 71     if(p)
 72     {
 73         flag=1;
 74         printf("%d %d %d\n",1000000-la,k-lb,1000000-lc);
 75     }
 76 }
 77 
 78 void solve2()
 79 {
 80     if(flag) return;
 81     rep(i,1,1e6+1) A[i]=B[i]=C[i]=t[i]=0;
 82     int nb=0,nc=0;
 83     rep(i,1,1e6-lb) B[++nb]=0;
 84     per(i,lb,1) B[++nb]=b[i]-‘0‘;
 85     rep(i,1,1e6-lc) C[++nc]=0;
 86     per(i,lc,1) C[++nc]=c[i]-‘0‘;
 87     int p=1;
 88     per(i,1e6,1)
 89     {
 90         if(C[i]>B[i]) break;
 91         if(C[i]<B[i]){p=0; break;}
 92     }
 93     if(!p) return;
 94     rep(i,1,1e6)
 95     {
 96         t[i]=t[i]+C[i]-B[i];
 97         if(t[i]<0)
 98         {
 99             t[i+1]--;
100             t[i]+=10;
101         }
102     }
103     p=1;
104     int k=1e6;
105     while(k>1&&t[k]==0) k--;
106     per(i,k/2,1) swap(t[i],t[k-i+1]);
107     rep(i,1,la)
108      if((a[i]-‘0‘)!=t[i]){p=0; break;}
109     if(p)
110     {
111         flag=1;
112         printf("%d %d %d\n",k-la,1000000-lb,1000000-lc);
113     }
114 }
115 
116 void solve3()
117 {
118     if(flag) return;
119     rep(i,1,1e6+1) A[i]=B[i]=C[i]=t[i]=0;
120     int na=0,nb=0,nc=0;
121     rep(i,1,1e6-1-la) A[++na]=0;
122     per(i,la,1) A[++na]=a[i]-‘0‘;
123     rep(i,1,1e6-1-lb) B[++nb]=0;
124     per(i,lb,1) B[++nb]=b[i]-‘0‘;
125     rep(i,1,1e6-lc) C[++nc]=0;
126     per(i,lc,1) C[++nc]=c[i]-‘0‘;
127     rep(i,1,1e6)
128     {
129         t[i]=t[i]+A[i]+B[i];
130         if(t[i]>9)
131         {
132             t[i]-=10;
133             t[i+1]++;
134         }
135     }
136     int p=1;
137     rep(i,1,1e6+1)
138      if(t[i]!=c[i]){p=0; break;}
139     if(p)
140     {
141         flag=1;
142         printf("%d %d %d\n",1000000-1-la,1000000-1-lb,1000000-lc);
143     }
144 }
145 
146 int main()
147 {
148     //freopen("1.in","r",stdin);
149     int cas;
150     scanf("%d",&cas);
151     while(cas--)
152     {
153         scanf("%s",a+1);
154         scanf("%s",b+1);
155         scanf("%s",c+1);
156         la=strlen(a+1),lb=strlen(b+1),lc=strlen(c+1);
157         //printf("la=%d lb=%d lc=%d\n",la,lb,lc);
158         flag=0;
159         solve1();
160         solve2();
161         solve3();
162         if(!flag) printf("-1\n");
163     }
164 
165     return 0;
166 }