半數單集問題

【問題描述】

給定一個自然數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;
}