SinzoL

用户名：SinzoL

访问量：2328

签　名：

编程菜鸟，感谢指导

等　　级
排　　名	570
经　　验	4311
参赛次数	12
文章发表	17
年　　龄	19
在职情况	学生
学　　校	哈尔滨工业大学（深圳）
专　　业	cs

　　自我简介：

很懒，很烂，很难

TA的其他文章

SinzoL--题解 1678: 数据结构-双向循环链表
浏览：115

你可能喜欢

SinzoL--题解 1193: 半数集问题

　　作者: SinzoL　　　　发表时间：2022-07-06 15:00:27 浏览：171　|　评论：0　

原题链接：半数集问题

###两种方法哦，第一种是大家常见的记忆搜索，我稍微优化了一下,第二种是递推的方法，不过是真正的递推哦（小伙伴们好像都没写出来）
###第一种方法：
```cpp
#include<bits/stdc++.h>
using namespace std;
int m;
long long num[100004];
long long bsj(int a)
{
    if(num[a])
        return num[a];//记忆化搜索的常规操作，但如果只写这一次，则仍有时间被浪费
    num[a]=1;
    for(int i=a/2;i>=1;i--)
    {
        if(num[i])num[a]+=num[i];//
        else num[a]+=bsj(i);//优化在这两行，对a提前进行判断，避免多调用函数，这里主要减少的是第二次及以后的调用，大约可以优化10~20%的时间
    }
    return num[a];
}
int main()
{
    num[1]=1;
    while(cin>>m)
    {
        cout<<bsj(m)<<endl;
    }
    return 0;
}
```
###第二种方法：
####在看代码之前我们先来思考一下：对于2n+1与2n，它们对应的结果有什么关系
####对于2n+2与2n，它们对应的结果又有什么关系
####首先我们来看2n+1与2n，由于题目要求“在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半”，故2n+1与2n对应的结果应该相同，于是有了第10行代码
####我们再来看2n+2与2n，根据题目要求我们可以知道，2n+2相比2n来说多了（2n+2）/2=n+1这一项产生的结果，于是有了第12行代码
-
-
-
-
-
-
-
-

```cpp
#include<bits/stdc++.h>
using namespace std;
long long num[100004]={0,1};
int main()
{
    int m;
    for(int i=2;i<=100000;i++)
    {
        if(i%2){
            num[i]=num[i-1];
        }else {
            num[i]=num[i-1]+num[i/2];
        }
    }
    while(cin>>m)
    {
        cout<<num[m]<<endl;
    }
    return 0;
}
```
第二种方法的时间复杂度为O(n)，输入值为90000时耗时1ms，很快了，应该是正解
新手写题解，欢迎吐槽

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

SinzoL

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

剔除相关数（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

SinzoL--题解 1193: 半数集问题

评论区

精彩推荐

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

母牛的故事（C语言代码）

采药（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）简单版

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

SinzoL

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

剔除相关数 （C语言代码）

【偶数求和】 （C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

SinzoL--题解 1193: 半数集问题

评论区

精彩推荐

小明A+B （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

母牛的故事 （C语言代码）

采药 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）简单版

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

剔除相关数（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

　　评论区

母牛的故事（C语言代码）

采药（C语言代码）