描述

给定一个不超过$1e181e18$的整数，选择$1010$进制下部分数位的数，使得选择数的和等于没选数的和

思路

• 反正只有$1818$位，直接枚举选择哪些数位暴力就好了，最坏复杂度$O(2^{18})O(2^\{18\})$貌似不用$DPDP$啊

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int nums[20];

int main()
{
    ll x;
    int len=0,sum=0;
    scanf("%lld",&x);
    for(int &i=len;x;x/=10,i++)
    {
        nums[i]=x%10;
        sum+=nums[i];
    }
    for(int i=0;i<(1<<len);i++)
    {
        int temp=0;
        for(int j=0;j<len;j++)
            if((i>>j)&1)
                temp+=nums[j];
        if(temp+temp==sum)
            return 0*puts("Yes");
    }
    puts("No");
    return 0;
}

空间复杂度$O(lo{g}_{10}n)O(log\_\{10\}n)$，时间复杂度$O(2^{lo{g}_{10}n})O(2^\{log\_\{10\}n\})$