神奇数

import java.util.Arrays;
import java.util.Scanner;

/**
 * 京东2018秋招Android
 * 神奇数
 * 东东在一本古籍上看到有一种神奇数,如果能够将一个数的数字分成两组,其中一组数字的和等于另一组数字的和,
 * 我们就将这个数称为神奇数。例如242就是一个神奇数,我们能够将这个数的数字分成两组,分别是{2,2}以及{4},
 * 而且这两组数的和都是4.东东现在需要统计给定区间中有多少个神奇数,即给定区间[l, r],统计这个区间中有多
 * 少个神奇数,请你来帮助他。
 * 输入描述:
 * 输入包括一行,一行中两个整数l和r(1 ≤ l, r ≤ 10^9, 0 ≤ r - l ≤ 10^6),以空格分割
 * <p>
 * <p>
 * 输出描述:
 * 输出一个整数,即区间内的神奇数个数
 * <p>
 * 输入例子1:
 * 1 50
 * <p>
 * 输出例子1:
 * 4
 */
public class MagicNumber {
    /**
     * 首先判断数组能否被平分，即数组分割问题，
     * dp[i][j]
     * 表示数组前 i
     * 个数字能否求和得到 j
     * 则
     * dp[i][j]=dp[i−1][j]||dp[i−1][j−array[i]]
     * 其中||是逻辑或运算。
     * 优化：
     * 1、若sum（array）为奇数，直接返回false
     * 2、使用逆序循环将dp数组简化为一维数组
     */

    public static boolean isMagic(int[] nums, int sum) {
        int len = nums.length;

        if (sum % 2 != 0)
            return false;

        int mid = sum / 2;

        int[] dp = new int[mid + 1];
        dp[0] = 1;
        for (int i = 0; i < len; i++) {
            for (int j = mid; j > 0; j--) {
                if (j >= nums[i] && nums[i] != -1)
                    dp[j] = Math.max(dp[j], dp[j - nums[i]]);
            }
        }
        if (dp[mid] > 0)
            return true;
        else
            return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int r = sc.nextInt();

        int result = 0;

        for (int i = l; i <= r; i++) {

            int num = i;
            int[] nums = new int[10];
            int sum = 0;
            Arrays.fill(nums, -1);
            int index = 0;
            while (num > 0) {
                int temp = num % 10;
                nums[index++] = temp;
                sum += temp;
                num = num / 10;
            }

            if (isMagic(nums, sum)) {
                result++;
            }
        }

        System.out.println(result);
    }

}

	#include <iostream>



	#include <vector>
#include <algorithm>
using namespace std;
bool judge(vector<int>& nums,int sum){
    if(sum%2!=0) //如果累加和为奇数，直接false
        return false;
    int n=nums.size();
    int target=sum/2; //目标累加和
    vector<bool> dp(target+1,false); //dp[i][j]为前i个数的累加和能否为j，简化为一维数组
    dp[0]=true;
    for(int i=1;i<=n;++i)
        for(int j=target;j>=nums[i];--j) //0-1背包问题，逆序循环
            dp[j]=dp[j-nums[i]] || dp[j];
    return dp[target];
}

vector<int> get_num(int i){ //取出每一位数字
    vector<int> res;
    while(i){
        res.push_back(i%10);
        i/=10;
    }
    return res;
}
int main(){
    int l,r;
    cin>>l>>r;
    int cnt=0;
    for(int i=l;i<=r;++i){
        vector<int> nums=get_num(i);
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(judge(nums,sum))
            cnt++;
    }
    cout<<cnt;
    return 0;
}  



	

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
bool IsNum(int &in){
       vector<int> arry;
       int num=in;
       int half=0;
       while(num){//将数字打散存入arry数组
              arry.push_back(num%10);
              half+=num%10;
              num/=10;
       }
       if (half%2!=0) return false;
       half/=2;
       vector<int> dp(half+1); //之后这一小段用的是01背包，判断能装下最大的数和一半是否相等。
       for (int i=0;i<arry.size();i++){
              for(int j=half;j>=arry[i];j--){
                     dp[j]=max(dp[j],dp[j-arry[i]]+arry[i]);
              }
       }
       return dp[half]==half;
}
 
 
 
int main()
{
       int l,r;
       cin>>l>>r;
       int count=0;
       for(int i=l;i<=r;i++){
              if(IsNum(i))
                     count++;//如果是神奇数，计数+1
       }
       cout<<count<<endl;
       return 0;
}

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

bool F(int x){
    int k=0, s=0, t, a[11];
    while(x){
        t = x%10;
        if(t){
            a[k++] = t;
            s += t;
        }
        x /= 10;
    }
    if(s&1)
        return 0;
    s >>= 1;
    int dp[s+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i=0;i<k;i++)
        for(int j=s;j>=a[i];j--)
            dp[j] = dp[j] || dp[j-a[i]];
    return dp[s];
}

int main(){
    int l, r, cnt=0;
    scanf("%d%d", &l, &r);
    for(int i=l;i<=r;i++)
        if(F(i))
            cnt++;
    printf("%d\n", cnt);
    return 0;
}

思路：设数X，先求出X的每位数存到vector中，再求出X每位数之和sum，
若为奇数则舍弃，
若为偶数则判断是否是神奇数，若是神奇数，则vector中必存在若干个数的和为sum/2,
所以只需判断sum/2 减去vector中的数是否为0即可
ps：感觉思路没啥问题，但只通过40%，很悲伤
      
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
    int l,r;
    cin>>l>>r;
    int total = 0;
    for(int i = l; i <= r; i++)
    {
        int n=i;
        int sum = 0;
        int half = 0;
        vector<int> vec;
        while(n > 0)
        {
            vec.push_back(n % 10);
            sum += n % 10;
            n = n / 10;
        }
        if(sum % 2 == 0)
        {
            half = sum / 2;
            sort(vec.begin(),vec.end());
            for(int j=vec.size()-1;j>=0;j--)
            {
                if(half>=vec[j])
                {
                    half=half-vec[j];
                    if(half==0)
                    {
                        total++;
                        break;
                    }
                }
            }
        }
    }
    cout << total;
    return 0;
}

//经好心人指出，已改正
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int l,r;
    cin>>l>>r;
    int total = 0;
    for(int i = l; i <= r; i++)
    {
        int n=i;
        int sum = 0;
        int half = 0;
        vector<int> vec;
        while(n > 0)
        {
            vec.push_back(n % 10);
            sum += n % 10;
            n = n / 10;
        }
        if(sum % 2 == 0)
        {
            half = sum / 2;
            vector<int> re(half+1); 
            for(int i=0;i<vec.size();i++)
            {
                for(int j=half;j>=vec[i];j--)
                {
                    re[j]=max(re[j],re[j-vec[i]]+vec[i]);
                }
            }
            if(half==re[half])
            {
              total++; 
            }
         }
    }
    cout << total;
    return 0;
}

import java.util.*;

public class Main {
    private static Map<Integer, Boolean> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt(), r = sc.nextInt();
        int ans = 0;
        for (int i=l; i<=r; i++) {
            if (isMiraculous(i)) { ans++; }
        }
        System.out.println(ans);
    }
    private static boolean isMiraculous(int p) {
        String sp = String.valueOf(p);
        int n = sp.length();
        char[] sa = sp.toCharArray();
        Arrays.sort(sa);
        Integer sorted = Integer.valueOf(new String(sa));
        if (map.containsKey(sorted)) {
            return map.get(sorted);
        }
        int in = sp.chars().map(c -> c -'0').sum();
        if (in % 2 != 0) {
            map.put(sorted, false);
            return false;
        }
        int[] ia = sp.chars().map(c -> c -'0').toArray();
        for (int i=1; i<=(1<<n); i++) {
            int tmp = i; int left = 0 ,right = 0;
            for (int j=0; j<n; j++) {
                if (((tmp >> j) & 1)== 0) {
                    left+=ia[j];
                }
                else {
                    right+=ia[j];
                }
            }
            if (left == right) {
                map.put(sorted, true);
                return true;
            }
        }
        map.put(sorted, false);
        return false;
    }
}

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Main test = new Main();
    Scanner in = new Scanner(System.in);
    int l, n;
    l = in.nextInt();
    n = in.nextInt();
    in.close();

    int sum = 0;

    for(int i = l; i <= n; i++){
        if(test.checkNumber(i))
            sum++;
    }

    System.out.println(sum);

}

private boolean checkNumber(int N){
    int B_sum = 0,n = N,cur = 0;
    int[] str = new int[10];
    while(n > 0){
        str[cur] = n % 10;
        B_sum += str[cur];
        cur++;
        n /= 10;
    }

    if((B_sum % 2) != 0) return false;

    B_sum /= 2;

    boolean[] f = new boolean[41];

    f[str[0]] = true;

    for(int i = 1; i < cur; i++){
        int value = str[i];
        for(int j = 40; j >= 0; --j){         //只能逆序循环，因为下一行会把f[j+value]改为true
            if(f[j] && j + value <= 40)       //顺序循环的话，j=k时，将k+value设为true，当j读到k+value时就出问题了
                f[j + value] = true;
        }

        if(f[B_sum]) {
            return true;
        }
    }

    return false;

}

}

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader df=new BufferedReader(new InputStreamReader(System.in));
        String sd;
        while((sd=df.readLine())!=null){
            String[] ds=sd.split(" ");
            int end=Integer.valueOf(ds[1]);
            if(end<=10){
                System.out.println(0);
                return;
            }
            int num=0;
            int start1=Integer.valueOf(ds[0]);
            int start =start1<=10?10:start1;
            for(int i=start;i<=end;i++){
               if(gg(i)) {
                   num++;
               }
            }
            System.out.println(num);
        }
    }
    public static boolean gg(int h){
        List<Integer> res=new ArrayList<Integer>();
        int  sum=0;
        while(h!=0){
            int h1=h%10;
            sum+=h1;
            res.add(h1);
            h=h/10;
        }
        if(sum%2==1){
            return false;
        }
        sum=sum/2;
        boolean[] res1=new boolean[sum+1];
        res1[0]=true;
        for(Integer d:res){
            for(int i=sum;i>=0;i--){
                if(i>=d){
                    res1[i]=res1[i-d]|res1[i];
                    
                }
            }
        }
        return res1[sum];
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        // 01背包
        Scanner scan = new Scanner(System.in);
        int l = scan.nextInt();
        int r = scan.nextInt();
        int ans = 0;
        for(int i=l;i<=r;++i){
            if(check(i))
            {
                ++ans;
                //System.out.println(i);
            }
                
        }
        System.out.println(ans);
    }
    private static boolean check(int x){
        ArrayList<Integer>list = new ArrayList<>();
        int v = 0;
        while(x!=0){
            list.add(x%10);
            v+=x%10;
            x/=10;
        }
        if((v&1)==1) return false;
        v/=2;
        int[] dp = new int[v+1];
        dp[0] = 1;
        for(int i=0;i<list.size();++i){
            int t = list.get(i);
            for(int j=v;j>=t;j--){
                if(dp[j-t]!=0) dp[j]=1;
            }
        }
        return dp[v]==1;
    }
}

//方法1每个数暴力搜索
//方法2记忆化搜索
//方法3动态规划
//可能是状态不多或是每个数初始化dp数组费时，测下来发现暴力搜索是最快的

#include <bits/stdc++.h>
using namespace std;
#define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int a[15];
//dp用
int dp[50];

//记忆化搜索用
bool DP[15][50];
bool vis[15][50];

//暴力搜索
bool dfs(int i,int n,int w){
    if(i==n) return w==0;
    if(w<a[i]) return dfs(i+1,n,w);
    return dfs(i+1,n,w-a[i])||dfs(i+1,n,w);
}

//方法1，暴力搜索
bool dynamicP1(int n, int w){
    return dfs(0,n,w);
}

//记忆化搜索
bool ms(int i,int n,int w){
    if(vis[i][w]) return DP[i][w];
    vis[i][w] = 1;
    if(i==n) return DP[i][w] = (w==0);
    if(w<a[i]) return DP[i][w] = dfs(i+1,n,w);
    return DP[i][w] = (dfs(i+1,n,w-a[i])||dfs(i+1,n,w));
}

//方法2：记忆化
bool dynamicP2(int n, int w){
    memset(DP,0,sizeof(DP));
    memset(vis,0,sizeof(vis));
    return ms(0,n,w);
}

//方法3，直接dp
bool dynamicP3(int n, int w){
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for(int i=0;i<n;i++){
        for(int j=w;j>=a[i];j--) dp[j] = dp[j]||dp[j-a[i]];
    }
    return dp[w];
}

bool judge(int number){
    int cnt = 0, sum = 0;
    while(number){
        int tmp = number%10;
        if(tmp) {
            a[cnt++] = tmp;
            sum+=tmp;
        }
        number/=10;
    }
    if(sum&1) return 0;
    return dynamicP3(cnt,sum>>1);
}

void solve(int l,int r){
    int ans = 0;
    for(int i=l;i<=r;i++){
        if(judge(i)) ans++;
    }
    cout<<ans<<endl;
}

int main() {
    INIT()
    int l,r;
    while(cin>>l>>r){
        solve(l,r);
    }
    return 0;
}

import java.util.Scanner;

public class Main{    public static boolean isJJ(int num) {    int[] arr = new int[11];    int index = 0;    int sum = 0;    for( ; num > 0; index++) {    arr[index] = num % 10;    sum += arr[index];    num /= 10;    }    if(sum % 2 != 0) return false;    return isKK(arr, sum / 2, index);    }    public static boolean isKK(int[] arr, int sum, int index) {  if(sum == 0) return true;    if(index < 0 || sum < 0) return false;    return isKK(arr, sum - arr[index], index - 1) || 
                    isKK(arr, sum, index - 1);    }    public static void main(String[] args) {    Scanner in = new Scanner(System.in);    int l = in.nextInt();    int r = in.nextInt();    int count = 0;    for(int i = l; i <= r; i++) {    if(isJJ(i))  count++;    }    System.out.println(count);    }
}