题意大概是:
一个数比如242,把所有数字分成两组,而且两组的和相等,那么这个数就是神奇数,此时242,能够分成{2,2}和{4},所以242是神奇数。
题目要求输入n和m求[n,m]区间内神奇数的个数。
思路:
对于任意一个数字,将每一位上的数字保存到数组里,并求所有位上的数字的和sum。然后使用回溯法遍历数组,
查看数组内是否存在和为sum/2的情况,如果存在则为神奇数。
bool isfind(vector<int>& nums, int sum, int cur, int begin)
{
if( begin == nums.size() ) return false;
if( cur == sum / ) return true;
bool res1 = isfind( nums, sum, cur+nums[begin], begin+ );
if( res1 ) return true;
bool res2 = isfind( nums, sum, cur, begin+ );
if( res2 ) return true;
return res1 || res2;
} bool fenjie(long long n)
{
vector<int> dig;
int sum = ;
if(n==)
{
dig.push_back();
return false;
}
int t =;
while(n>)
{
t = n%;
n/=;
dig.push_back(t);
sum+=t;
}
sort(dig.begin(),dig.end());
if(sum&)return false;
return isfind(dig,sum,,);
}
void core()
{
int n,m,ret =;
cin>>n>>m;
for( int i = n; i <= m; i++ )
{
if (fenjie(i))ret++;
}
cout<<ret<<endl;
}
int main()
{
core();
}