HDU 4726 Kia's Calculation

Doctor Ghee is teaching Kia how to calculate the sum of two integers. But Kia is so careless and alway forget to carry a number when the sum of two digits exceeds 9. For example, when she calculates 4567+5789, she will get 9246, and for 1234+9876, she will get 0. Ghee is angry about this, and makes a hard problem for her to solve: Now Kia has two integers A and B, she can shuffle the digits in each number as she like, but leading zeros are not allowed. That is to say, for A = 11024, she can rearrange the number as 10124, or 41102, or many other, but 02411 is not allowed.  After she shuffles A and B, she will add them together, in her own way. And what will be the maximum possible sum of A "+" B ? Input The rst line has a number T (T <= 25) , indicating the number of test cases.  For each test case there are two lines. First line has the number A, and the second line has the number B.  Both A and B will have same number of digits, which is no larger than 10  ⁶, and without leading zeros. Output For test case X, output "Case #X: " first, then output the maximum possible sum without leading zeros. Sample Input 1 5958 3036 Sample Output

Case #1: 8984

对于第一位,进行特殊处理，遍历全部可能，然后之后贪心的构造最大的数。

#include<map> #include<set> #include<ctime> #include<cmath> #include<stack> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<functional> using namespace std; #define ms(x,y) memset(x,y,sizeof(x)) #define rep(i,j,k) for(int i=j;i<=k;i++) #define per(i,j,k) for(int i=j;i>=k;i--) #define loop(i,j,k) for (int i=j;i!=-1;i=k[i]) #define inone(x) scanf("%d",&x) #define intwo(x,y) scanf("%d%d",&x,&y) #define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z) #define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p) #define lson x<<1,l,mid #define rson x<<1|1,mid+1,r #define mp(i,j) make_pair(i,j) #define ff first #define ss second typedef long long LL; typedef pair<int, int> pii; const int low(int x) { return x&-x; } const int INF = 0x7FFFFFFF; const int mod = 1e9 + 7; const int N = 1e6 + 10; const double eps = 1e-8; int T, a[N], b[N], c[N], d[N], aa[N], bb[N], n, cas = 1; char A[N], B[N]; void calc() { rep(i, 0, 9) aa[i] = a[i], bb[i] = b[i], c[i] = 0; per(i, 9, 0) { rep(j, 0, 9) rep(k, 0, 9) { if ((j + k) % 10 != i) continue; int cost = min(aa[j], bb[k]); c[i] += cost; aa[j] -= cost; bb[k] -= cost; } } per(i, 9, 0) { if (c[i] > d[i]) { rep(j, 0, 9) d[j] = c[j]; break; } if (c[i] < d[i]) break; } } int main() { for (inone(T); T--; cas++) { rep(i, 0, 9) a[i] = b[i] = d[i] = 0; scanf("%s%s", A, B); n = strlen(A); rep(i, 0, n - 1) a[A[i] - '0']++; rep(i, 0, n - 1) b[B[i] - '0']++; if (n == 1) { printf("Case #%d: %d\n", cas, (A[0] + B[0] - '0' * 2) % 10); continue; } printf("Case #%d: ", cas); int res = 0, flag = 0; rep(i, 1, 9) rep(j, 1, 9) { if (!a[i] || !b[j]) continue; res = max(res, (i + j) % 10); } rep(i, 1, 9) rep(j, 1, 9) { if (!a[i] || !b[j]) continue; if (res != (i + j) % 10) continue; a[i]--; b[j]--; calc(); a[i]++; b[j]++; } per(i, 9, 1) if (i && d[i]) { flag = 1; break; } if (res || !res && !flag) printf("%d", res); if (res || !res && flag) per(i, 9, 0) rep(j, 1, d[i]) printf("%d", i); putchar(10); } return 0; }