题解 | 数位染色

1. 核心思想：将数字转为字符串，计算所有数位之和 如果能找到一些数位，使其和为 ，则可以实现要求本质是一个子集和问题
2. 解决方案：先判断总和是否为偶数（如果为奇数则无解）使用状态压缩DP或DFS判断是否存在子集和为 由于数据范围较小（最多18位数字），可以直接DFS

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

bool can_split(string& num, int target) {
    int n = num.length();
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    
    // 初始化：空集的和为0
    for(int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
    
    // 动态规划
    for(int i = 1; i <= n; i++) {
        int digit = num[i-1] - '0';
        for(int j = 0; j <= target; j++) {
            dp[i][j] = dp[i-1][j];  // 不选当前数位
            if(j >= digit) {
                dp[i][j] = dp[i][j] || dp[i-1][j-digit];  // 选当前数位
            }
        }
    }
    
    return dp[n][target];
}

int main() {
    string x;
    cin >> x;
    
    // 计算所有数位之和
    int total = 0;
    for(char c : x) {
        total += c - '0';
    }
    
    // 如果总和为奇数，无解
    if(total % 2 != 0) {
        cout << "No" << endl;
        return 0;
    }
    
    // 判断是否能找到和为total/2的子集
    if(can_split(x, total/2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}