题解：BISHI37 数位差与数值和的构造

题目链接

数位差与数值和的构造

题目描述

给定整数 ，请构造非负整数 ，满足 ，且 ，其中 表示 的十进制各位数字之和。保证解一定存在。

解题思路

目标是让 与 的数位和尽量均衡，同时保证逐位相加无进位，从而自然满足 。设 的十进制从高到低的每一位为 ：

  • 若 为偶数，则把该位平均分给 ，即本位 取 ， 取 ；
  • 若 为奇数，则在本位让 与 在 之间交替分配（用一个开关在遇到奇数位时翻转）。

由于对每一位都保证两数本位之和等于 ，故整个加法无进位，天然满足 ；而所有奇数位多出来的那个 会在 之间交替分担，因而两者的数位和之差至多为 。

实现细节：将 作为字符串读取，按高位到低位处理，分别构造 与 的对应位（字符串）。最后去掉前导零并输出（若全为零，则输出 0）。

代码

#include <bits/stdc++.h>
using namespace std;

string strip_leading_zeros(const string &s) {
    size_t i = 0; while (i < s.size() && s[i] == '0') ++i;
    return (i == s.size()) ? string("0") : s.substr(i);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        string n; 
        cin >> n;
        string a, b; a.reserve(n.size()); b.reserve(n.size());
        bool give_to_a = true;
        for (char c : n) {
            int d = c - '0';
            if (d % 2 == 0) {
                int x = d / 2;
                a.push_back(char('0' + x));
                b.push_back(char('0' + x));
            } else {
                int lo = d / 2, hi = lo + 1;
                if (give_to_a) {
                    a.push_back(char('0' + hi));
                    b.push_back(char('0' + lo));
                } else {
                    a.push_back(char('0' + lo));
                    b.push_back(char('0' + hi));
                }
                give_to_a = !give_to_a;
            }
        }
        cout << strip_leading_zeros(a) << ' ' << strip_leading_zeros(b) << '\n';
    }
    return 0;
}

import java.util.*;

public class Main {
    private static String stripLeadingZeros(String s) {
        int i = 0, n = s.length();
        while (i < n && s.charAt(i) == '0') i++;
        return (i == n) ? "0" : s.substring(i);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            String n = sc.next();
            StringBuilder a = new StringBuilder(n.length());
            StringBuilder b = new StringBuilder(n.length());
            boolean giveToA = true;
            for (int i = 0; i < n.length(); i++) {
                int d = n.charAt(i) - '0';
                if ((d & 1) == 0) {
                    int x = d / 2;
                    a.append((char) ('0' + x));
                    b.append((char) ('0' + x));
                } else {
                    int lo = d / 2, hi = lo + 1;
                    if (giveToA) {
                        a.append((char) ('0' + hi));
                        b.append((char) ('0' + lo));
                    } else {
                        a.append((char) ('0' + lo));
                        b.append((char) ('0' + hi));
                    }
                    giveToA = !giveToA;
                }
            }
            System.out.println(stripLeadingZeros(a.toString()) + " " + stripLeadingZeros(b.toString()));
        }
    }
}

import sys

def strip_leading_zeros(s: str) -> str:
    i = 0
    while i < len(s) and s[i] == '0':
        i += 1
    return "0" if i == len(s) else s[i:]

T = int(input())
for _ in range(T):
    n = input().strip()
    a = []
    b = []
    give_to_a = True
    for ch in n:
        d = ord(ch) - ord('0')
        if d % 2 == 0:
            x = d // 2
            a.append(chr(ord('0') + x))
            b.append(chr(ord('0') + x))
        else:
            lo, hi = d // 2, d // 2 + 1
            if give_to_a:
                a.append(chr(ord('0') + hi))
                b.append(chr(ord('0') + lo))
            else:
                a.append(chr(ord('0') + lo))
                b.append(chr(ord('0') + hi))
            give_to_a = not give_to_a
    print(strip_leading_zeros(''.join(a)), strip_leading_zeros(''.join(b)))

算法及复杂度

  • 算法：逐位构造，奇数位交替分配 与
  • 时间复杂度： 每组
  • 空间复杂度：