1. 首页
2. 大数模拟
3. 本页

HDU 5920 Ugly Problem (模拟)

题目链接：点我~~

题意：给定一个不大于 10^1000 的正整数$s$，构造不超过$50$个回文数，使得这些数之和恰好是$s$。

思路：每次用不超过$s$的最大回文数去减$s$，这样$s$的位数会减半，需要实现一个高精度减法。

import java.util.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(System.in);
		int t, cas = 1;
		t = cin.nextInt();
		BigInteger s, tmp, tmp2, tmp3, tmp4, tmp5, hh;
		BigInteger[] ans = new BigInteger[5005];
		BigInteger[] pw = new BigInteger[1001];
		pw[1] = BigInteger.valueOf(10);
		for (int i = 2; i <= 1000; ++i) {
			pw[i] = pw[i - 1].multiply(BigInteger.valueOf(10));
		}
		while (t > 0) {
			t--;
			s = cin.nextBigInteger();
			tmp = s;
			int tol = 0, ll;
			while (true) {
				if (s.compareTo(BigInteger.ZERO) == 0)
					break;
				ll = String.valueOf(s).length();
				if (ll == 1) {
					ans[tol++] = s;
					break;
				} else if (ll == 2) {
					while (s.compareTo(BigInteger.valueOf(9)) > 0) {
						ans[tol++] = BigInteger.valueOf(9);
						s = s.subtract(BigInteger.valueOf(9));
					}
					if (s.compareTo(BigInteger.ZERO) != 0)
						ans[tol++] = s;
					break;
				}
				tmp = tmp2 = s;
				int len = ll;
				boolean flag;
				if (len % 2 == 1) {
					tmp = tmp.mod(pw[len / 2]);
					tmp2 = tmp2.divide(pw[len / 2 + 1]);
					flag = true;
				} else {
					tmp = tmp.mod(pw[len / 2]);
					tmp2 = tmp2.divide(pw[len / 2]);
					flag = false;
				}
				// tmp2 前 tmp后 tmp4翻转后 tmp5翻转前
				ll = String.valueOf(tmp2).length();
				tmp3 = BigInteger.ZERO;
				tmp4 = tmp;
				for (int i = 0; i < ll; ++i) {
					tmp3 = tmp3.multiply(BigInteger.valueOf(10));
					tmp3 = tmp3.add(tmp4.mod(BigInteger.valueOf(10)));
					tmp4 = tmp4.divide(BigInteger.valueOf(10));
				}
				tmp4 = tmp3;
				tmp3 = BigInteger.ZERO;
				tmp5 = tmp2;
				for (int i = 0; i < ll; ++i) {
					tmp3 = tmp3.multiply(BigInteger.valueOf(10));
					tmp3 = tmp3.add(tmp5.mod(BigInteger.valueOf(10)));
					tmp5 = tmp5.divide(BigInteger.valueOf(10));
				}
				tmp5 = tmp3;
				if (tmp5.compareTo(tmp) < 0) {
					tmp3 = s.divide(pw[len / 2]).multiply(pw[len / 2]);
					tmp3 = tmp3.add(tmp5);
					ans[tol++] = tmp3;
					s = s.subtract(tmp3);
				} else if (tmp5.compareTo(tmp) == 0) {
					ans[tol++] = s;
					break;
				}
				else {
					tmp = tmp.add(BigInteger.ONE);
					tmp3 = s.subtract(tmp);
					int jj = String.valueOf(tmp3).length();
					boolean fff = jj % 2 == 1 ? true : false;
					if (fff) {
						tmp2 = tmp3.divide(pw[jj / 2 + 1]);
						tmp5 = tmp2;
						hh = BigInteger.ZERO;
						for (int i = 0; i < jj / 2; ++i) {
							hh = hh.multiply(BigInteger.valueOf(10));
							hh = hh.add(tmp5.mod(BigInteger.valueOf(10)));
							tmp5 = tmp5.divide(BigInteger.valueOf(10));
						}
						tmp5 = hh;
						hh = tmp3.divide(pw[jj / 2]).multiply(pw[jj / 2]).add(tmp5);
						ans[tol++] = hh;
						hh = tmp3.subtract(hh);
						s = tmp.add(hh);
					} else {
						tmp2 = tmp3.divide(pw[jj / 2]);
						tmp5 = tmp2;
						hh = BigInteger.ZERO;
						for (int i = 0; i < jj / 2; ++i) {
							hh = hh.multiply(BigInteger.valueOf(10));
							hh = hh.add(tmp5.mod(BigInteger.valueOf(10)));
							tmp5 = tmp5.divide(BigInteger.valueOf(10));
						}
						tmp5 = hh;
						hh = tmp3.divide(pw[jj / 2]).multiply(pw[jj / 2]).add(tmp5);
						ans[tol++] = hh;
						hh = tmp3.subtract(hh);
						s = tmp.add(hh);
					}
				}
			}
			System.out.println("Case #" + cas + ":");
			cas++;
			System.out.println(tol);
			for (int i = 0; i < tol; ++i) {
				System.out.println(ans[i]);
			}
		}
		cin.close();
	}
}