题解 | 神奇数

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

class Solution {
public:
    bool isMagicNumber(int x) {
        // 提取非零位数字并计算总和
        vector<int> digits;
        int sum = 0;
        
        while (x) {
            int digit = x % 10;
            if (digit) {
                digits.push_back(digit);
                sum += digit;
            }
            x /= 10;
        }
        
        // 总和为奇数时不可能分成相等的两组
        if (sum & 1) {
            return false;
        }
        
        // 目标和为总和的一半
        sum >>= 1;
        
        // 动态规划数组
        vector<bool> dp(sum + 1, false);
        dp[0] = true;
        
        // 01背包
        for (int digit : digits) {
            for (int j = sum; j >= digit; j--) {
                dp[j] = dp[j] || dp[j - digit];
            }
        }
        
        return dp[sum];
    }
};

int main() {
    int l, r;
    cin >> l >> r;
    
    Solution solution;
    int count = 0;
    
    for (int i = l; i <= r; i++) {
        if (solution.isMagicNumber(i)) {
            count++;
        }
    }
    
    cout << count << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public boolean isMagicNumber(int x) {
            // 提取非零位数字并计算总和
            List<Integer> digits = new ArrayList<>();
            int sum = 0;
            
            while (x > 0) {
                int digit = x % 10;
                if (digit != 0) {
                    digits.add(digit);
                    sum += digit;
                }
                x /= 10;
            }
            
            // 总和为奇数时不可能分成相等的两组
            if ((sum & 1) == 1) {
                return false;
            }
            
            // 目标和为总和的一半
            sum >>= 1;
            
            // 动态规划数组
            boolean[] dp = new boolean[sum + 1];
            dp[0] = true;
            
            // 01背包
            for (int digit : digits) {
                for (int j = sum; j >= digit; j--) {
                    dp[j] |= dp[j - digit];
                }
            }
            
            return dp[sum];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int r = sc.nextInt();
        
        Solution solution = new Solution();
        int count = 0;
        
        for (int i = l; i <= r; i++) {
            if (solution.isMagicNumber(i)) {
                count++;
            }
        }
        
        System.out.println(count);
        sc.close();
    }
}

class Solution:
    def isMagicNumber(self, x):
        # 提取非零位数字并计算总和
        digits = []
        sum_val = 0
        
        while x:
            digit = x % 10
            if digit:
                digits.append(digit)
                sum_val += digit
            x //= 10
        
        # 总和为奇数时不可能分成相等的两组
        if sum_val & 1:
            return False
        
        # 目标和为总和的一半
        sum_val >>= 1
        
        # 动态规划数组
        dp = [False] * (sum_val + 1)
        dp[0] = True
        
        # 01背包
        for digit in digits:
            for j in range(sum_val, digit - 1, -1):
                dp[j] = dp[j] or dp[j - digit]
        
        return dp[sum_val]

# 主函数
while True:
    try:
        l, r = map(int, input().split())
        solution = Solution()
        count = sum(1 for i in range(l, r + 1) if solution.isMagicNumber(i))
        print(count)
    except:
        break