半数单集问题
【问题描述】
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。n∈set(n)；在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。
注意半数集不是多重集. 集合中已经有的元素不再添加到集合中。
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
【输入】
输入文件只有1行，给出整数n。
【输出】
输出文件只有1行，给出半数集set(n)中的元素个数。
【样例】
sample.in
6
sample.out
6
【数据范围】
30%数据:1<=n<=20
100%数据:1<=n<=200
Solution
30分:按照题意枚举数的左边可以加上的数,拿个map标记一下,或者直接丢进set里面,最后输出size即可
100分:
半数集:多重集
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下：
-
(1) n ∈set(n)；
-
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
-
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如：set(8)={8，18，28，38，48，128，138，148，248，1248}，则半数集set(8)中共有10个元素
void dfs(int x,int ans=1) {
if(n>1) for(int i=1;i<=x/2;i++) ans+=dfs(i);
return ans;
}
改进一下,加个记忆化
void dfs(int x) {
if(f[x]>0) return f[x];
f[x]=1;
for(int i=1;i<=x/2;i++) f[x]+=dfs(i);
return f[x];
}
半数单集:非多重集
类似半数集，区别在于：半数集是多重集，而半数单集不是多重集，即集合中已有的元素不再添加到集合中。
例如：n=24，那么半数集set(24)中的元素1224就有如下两种方式可以生成：
24 → 1224
24 →224 → 1224
所以，1224就是一个被重复计算的元素
那么我们怎么剔除这种重复元素呢?我们发现题目给的n<=200,所以n/2<=100,那么重复元素一定是一个两位数,且十位上的数字<=个位上的数字的一半,我们剔除组成十位上的数字的方案数即可
#include<bits/stdc++.h>
using namespace std;
int f[210];
int dfs(int n) {
if(f[n]>0) return f[n];
f[n]=1;
for(int i=1;i<=n/2;i++) {
f[n]+=dfs(i);
if(i>10 && (2*(i/10))<=i%10)
f[n]-=f[i/10];
}return f[n];
}
int main()
{
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
ios::sync_with_stdio(0);
int n;cin>>n;
cout<<dfs(n)<<endl;
return 0;
}