2019HDU多校第七场 HDU6646 A + B = C 【模拟】

一、题目

　　A + B = C

二、分析

　　比较考验码力的题。

　　对于$c$，因为首位肯定不为0，那么$a$或者$b$至少有一个最高位是和$c$平齐的，或者少一位（相当于$a$+$b$进位得到）。

　　那么这里，我们可以分四种情况

　　1　让$a$与$c$变为等长$A$和$C$

　　　　等长后判断$R = C - A$是否等于$b$，这里的等实际上是${R}\times{10^{d1}}$与${b}\times{10^{d2}}$比较，$d1$和$d2$都可能为结果做出贡献。

　　2　让$a$与$c$变为等长$A$和$C$，但$C$继续增长一位变为$C = {C}\times{10}$

　　　　判断$R = C - A$是否等于$b$，后面同上。

　　3　让$b$与$c$变为等长$B$和$C$

　　　　同情况1

　　4　让$b$与$c$变为等长$B$和$C$，但$C$继续增长一位变为$C = {C}\times{10}$

　　　　同情况2

　　然后就是紧张刺激的码代码了，细节很多，因为变量太多，该初始化的要初始化，特别是X，Y，Z的变化一定要即时增长。

三、AC代码

  1 #include <bits/stdc++.h>

  2

  3 using namespace std;

  4 #define ll long long

  5 #define Min(a,b) ((a)>(b)?(b):(a))

  6 #define Max(a,b) ((a)>(b)?(a):(b))

  7 const int maxn = 1e5+13;

  8 char aa[maxn], bb[maxn], cc[maxn];

  9 int a[maxn], b[maxn], c[maxn];

 10 int lena, lenb, lenc;

 11 int la, lb, lc;

 12 int tx, ty, tz, deta1, deta2, deta3;

 13

 14 void debug()

 15 {

 16     cout << " a ";

 17     for(int i = 0; i < la; i++)

 18         cout << a[i];

 19     cout << endl << " c ";

 20     for(int i = 0; i < lc; i++)

 21         cout << c[i];

 22     cout << endl;

 23 }

 24

 25 // A - B == C

 26 bool check(int A[], int B[], int C[], int LA, int LB, int LC)

 27 {

 28     deta1 = deta2 = deta3 = 0;   //变化量

 29     if(A[0] < B[0])

 30         return false;

 31     int Res[maxn], L = LA;

 32     int pos = L - 1, tmp = 0;

 33     int i, j;

 34     for(i = LA - 1, j = LB - 1; i >= 0 && j >= 0; i--, j--, pos--)

 35     {

 36         A[i] -= tmp;

 37         tmp = 0;

 38         Res[pos] = A[i] - B[j];

 39         if(Res[pos] < 0)

 40         {

 41             tmp = 1;

 42             Res[pos] += 10;

 43         }

 44     }

 45     for(i; i >= 0; i--, pos--)

 46     {

 47         A[i] -= tmp;

 48         tmp = 0;

 49         Res[pos] = A[i];

 50         if(Res[pos] < 0)

 51         {

 52             tmp = 1;

 53             Res[pos] += 10;

 54         }

 55     }

 56     if(tmp > 0)

 57         return false;

 58     // 判断 Res  == C * 10^deta

 59     //  或者 Res * 10 ^ deta = C

 60     for(i = 0; i < L; i++)

 61     {

 62         if(Res[i] != 0)

 63             break;

 64     }

 65     for(j = 0; j < LC && i < L; j++, i++)

 66     {

 67         if(Res[i] != C[j])

 68             return false;

 69     }

 70     while(i < L)

 71     {

 72         if(Res[i] != 0)

 73             return false;

 74         deta3++;

 75         i++;

 76     }

 77     while(j < LC)

 78     {

 79         if(C[j] != 0)

 80             return false;

 81         deta1++;

 82         j++;

 83     }

 84     deta2 = deta1;

 85     // cout << "Res : ";

 86     // for(i = 0; i < L; i++)

 87     //     cout << Res[i];

 88     // cout << endl << "C : ";

 89     // for(i = 0; i < LC; i++)

 90     //     cout << C[i];

 91     // cout << endl;

 92     return true;

 93 }

 94

 95 void init1()

 96 {

 97     tx = 0, ty = 0, tz = 0;

 98     for(int i = 0; i < lena; i++)

 99         a[i] = aa[i] - '0';

100     for(int i = 0; i < lenb; i++)

101         b[i] = bb[i] - '0';

102     for(int i = 0; i < lenc; i++)

103         c[i] = cc[i] - '0';

104     la = lena, lb = lenb, lc = lenc;

105     if(la > lc)

106     {

107         lc = la;

108         tz += (lc - lenc);

109         for(int i = lenc; i < lc; i++)

110         {

111             c[i] = 0;

112         }

113     }

114     else if(la < lc)

115     {

116         la = lc;

117         tx += (la - lena);

118         for(int i = lena; i < la; i++)

119         {

120             a[i] = 0;

121         }

122     }

123     //cout << "tx : " << tx << " ty : " << ty << " tz : " << tz << endl;

124 }

125 void init2()

126 {

127     tx = 0, ty = 0, tz = 0;

128     for(int i = 0; i < lena; i++)

129         a[i] = aa[i] - '0';

130     for(int i = 0; i < lenb; i++)

131         b[i] = bb[i] - '0';

132     for(int i = 0; i < lenc; i++)

133         c[i] = cc[i] - '0';

134     la = lena, lb = lenb, lc = lenc;

135     if(lb > lc)

136     {

137         lc = lb;

138         tz += lc - lenc;

139         for(int i = lenc; i < lc; i++)

140         {

141             c[i] = 0;

142         }

143     }

144     else if(lb < lc)

145     {

146         lb = lc;

147         ty += lb - lenb;

148         for(int i = lenb; i < lb; i++)

149         {

150             b[i] = 0;

151         }

152     }

153 }

154

155 int main()

156 {

157     //freopen("input.txt", "r", stdin);

158     //freopen("out.txt", "w", stdout);

159     int T;

160     scanf("%d", &T);

161     while(T--)

162     {

163         scanf("%s%s%s", aa, bb, cc);

164         lena = strlen(aa);

165         lenb = strlen(bb);

166         lenc = strlen(cc);

167         init1();

168         //c - a == b

169         if(check(c, a, b, lc, la, lb))

170         {

171             // cout << " c - a ?= b " << deta << endl;

172             tx += deta2, ty += deta3, tz += deta1;

173             printf("%d %d %d\n", tx, ty, tz);

174             continue;

175         }

176         init1();

177         //c*10 - a == b

178         c[lc++] = 0;

179         tz++;

180         if(check(c, a, b, lc, la, lb))

181         {

182             // cout << " c*10 - a ?= b" << endl;

183             tx += deta2, ty += deta3, tz += deta1;

184             printf("%d %d %d\n", tx, ty, tz);

185             continue;

186         }

187         init2();

188         //c - b == a

189         if(check(c, b, a, lc, lb, la))

190         {

191             // cout << " c - b ?= a" << endl;

192             tx += deta3, ty += deta2, tz += deta1;

193             printf("%d %d %d\n", tx, ty, tz);

194             continue;

195         }

196         init2();

197         //c*10 - b == a

198         c[lc++] = 0;

199         tz++;

200         if(check(c, b, a, lc, lb, la))

201         {

202             // cout << " c*10 - b ?= a" << endl;

203             tx += deta3, ty += deta2, tz += deta1;

204             printf("%d %d %d\n", tx, ty, tz);

205             continue;

206         }

207         puts("-1");

208     }

209     return 0;

210 }

巴特西

2019HDU多校第七场 HDU6646 A + B = C 【模拟】

一、题目

二、分析

三、AC代码

最新文章

热门文章