1.题目描述
东东在一本古籍上看到有一种神奇数,如果能够将一个数的数字分成两组,其中一组数字的和 等于另一组数字的和,我们就将这个数称为神奇数。例如242就是一个神奇数,我们能够将这个数的数字分 成两组,分别是{2,2}以及{4},而且这两组数的和都是4.东东现在需要统计给定区间中有多少个神奇数,即 给定区间[l,r],统计这个区间中有多少个神奇数,请你来帮助他。
- 输入描述:
输入包括一行,一行中两个整数l 和 r(1 ≤ l, r ≤ 10^9, 0 ≤ r - l ≤ 10^6),以空格分割 输出描述:
输出一个整数,即区间内的神奇数个数 - 输入示例:
1 50 - 输出示例:
4
2.题目解析
- 要把数字按位转化成数组。
- 每位数字累计求和
- 数组中元素和是否能累加成半和。(01背包问题)
3.参考答案
自顶而下递归
#include <bits/stdc++.h>
using namespace std;
bool IsMagic(int i,int sum,int* nums){
if(0 == sum) return true;
if(0 > sum) return false;
if(i < 0) return false;
return IsMagic(i-1,sum-nums[i],nums)
||IsMagic(i-1,sum,nums);
}
bool check(int num) {
int nums[11]; // 把数字n按位存到s中
int i = 0; // 下标
int sum = 0; // 每位数字求和
while(num > 0) {
nums[i] = num % 10; // 获取并保存每位数字
sum += nums[i++]; // 每位数字累计求和
num /= 10; // 除去个位数字
}
// 每位数和是奇数，则肯定不是神奇数
if(sum%2) return false;
// 从每位数字中取出数字和是否为和的一半
return IsMagic(i-1,sum/2,nums);
}
int main() {
int l = 0;
int r = 0;
scanf("%d%d",&l,&r);
int res = 0;
for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
if(check(i)) ++res;
}
printf("%d\n",res);
return 0;
}
自顶而下递归(备忘录法/记忆化搜索)
#include <bits/stdc++.h>
using namespace std;
bool IsMagic(int i,int sum,int* nums,vector<bool>* dp){
if(0 == sum) return true;
if(0 > sum) return false;
if(i < 0) return false;
if(false != dp[i][sum]) return dp[i][sum];
return dp[i][sum] = IsMagic(i-1,sum-nums[i],nums,dp)
||IsMagic(i-1,sum,nums,dp);
}
bool check(int num) {
int nums[11]; // 把数字n按位存到s中
int i = 0; // 下标
int sum = 0; // 每位数字求和
while(num > 0) {
nums[i] = num % 10; // 获取并保存每位数字
sum += nums[i++]; // 每位数字累计求和
num /= 10; // 除去个位数字
}
// 每位数和是奇数，则肯定不是神奇数
if(sum%2) return false;
// 从每位数字中取出数字和是否为和的一半
vector<bool> dp[i];
fill_n(dp,i,vector<bool>(sum/2+1,false));
return IsMagic(i-1,sum/2,nums,dp);
}
int main() {
int l = 0;
int r = 0;
scanf("%d%d",&l,&r);
int res = 0;
for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
if(check(i)) ++res;
}
printf("%d\n",res);
return 0;
}
自底而上递推
#include <bits/stdc++.h>
using namespace std;
bool IsMagic(int i,int sum,int* nums,vector<bool>* dp){
for(int idx=1;idx<=i;++idx){
for(int s=0;s<=sum;++s){
if(s-nums[idx] == 0){
dp[idx][s] = true;
}else if(s-nums[idx]>0){
dp[idx][s] = dp[idx-1][s-nums[idx]]||dp[idx-1][s];
}else{
dp[idx][s] = dp[idx-1][s];
}
}
}
return dp[i][sum];
}
bool check(int num) {
int nums[11]; // 把数字n按位存到s中
int i = 0; // 下标
int sum = 0; // 每位数字求和
while(num > 0) {
nums[i] = num % 10; // 获取并保存每位数字
sum += nums[i++]; // 每位数字累计求和
num /= 10; // 除去个位数字
}
// 每位数和是奇数，则肯定不是神奇数
if(sum%2) return false;
// 从每位数字中取出数字和是否为和的一半
vector<bool> dp[i];
fill_n(dp,i,vector<bool>(sum/2+1,false));
return IsMagic(i-1,sum/2,nums,dp);
}
int main() {
int l = 0;
int r = 0;
scanf("%d%d",&l,&r);
int res = 0;
for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
if(check(i)) ++res;
}
printf("%d\n",res);
return 0;
}
滚动数组优化
#include <bits/stdc++.h>
using namespace std;
bool IsMagic(int i,int sum,int* nums,bool* dp){
for(int idx=1;idx<=i;++idx){
for(int s=sum;s>=nums[idx];--s){
if(s-nums[idx] == 0){
dp[nums[idx]] = true;
}else{
dp[s] = dp[s-nums[idx]]||dp[s];
}
}
}
return dp[sum];
}
bool check(int num) {
int nums[11]; // 把数字n按位存到s中
int i = 0; // 下标
int sum = 0; // 每位数字求和
while(num > 0) {
nums[i] = num % 10; // 获取并保存每位数字
sum += nums[i++]; // 每位数字累计求和
num /= 10; // 除去个位数字
}
// 每位数和是奇数，则肯定不是神奇数
if(sum%2) return false;
// 从每位数字中取出数字和是否为和的一半
bool dp[sum/2+1];
fill_n(dp,sum/2+1,false);
return IsMagic(i-1,sum/2,nums,dp);
}
int main() {
int l = 0;
int r = 0;
scanf("%d%d",&l,&r);
int res = 0;
for(int i = l; i <= r; ++i) { // 遍历[l,r]中所有数字
if(check(i)) ++res;
}
printf("%d\n",res);
return 0;
}
