京东2018校招C++工程师笔试题-编程题二

发表于 | 分类于 ，

题目

描述

一个十进制数字的各个位上的数若可以分成两部分 p1,p2,
且两分内的元素之和 sum(p1)=sum(p2),
则称这个数为神奇数 ,
例如 242,可以分为 {2,2} 与 {4},且两部分元素之和都为 4,
则 242 为神奇数.

输入

1 行,两个数 l,r

输出

输出 [l,r] 内神奇数的个数

Example

Input

1 55

Output

4

题解

穷举

  • 对于每个数,穷举每个组合,判断是否为神奇数
  • 判断是否是神奇数使用 dp
  • 时间复杂度 O((l-r)(log n)(log r)) (log r <= 9)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>

using namespace std;

bool check(int n)
{
    int pos[10],nz=0,sum=0;
    while(n)
    {
        int t=n%10;
        sum+=t;
        if(t)
            pos[++nz]=t;
        n/=10;
    }
    if(sum&1)return 0;
    sum>>=1;
    bool *dp=new bool[sum+1];
    dp[0]=1;
    sort(pos+1,pos+nz+1);
    if(pos[nz]>sum)return 0;
    for(int i=nz;i>0;--i)
    {
        for(int j=sum;j>=pos[i];--j)
        {
            dp[j]=dp[j]|dp[j-pos[i]];
        }
        if(dp[sum])
        {
            delete[]dp;
            return 1;
        }
    }
    delete[] dp;
    return 0;
}

int main(){
    int r,l,c=0;
    cin>>l>>r;
    while(l<=r)
    {
        c+=check(l++);
    }
    cout<<c;
}