苦难之路01

苦难之路01 | SOX

---

题目：

思路：

1.起初是想暴力解决，但是发现10^9的数据大小后认为一定会超时，再由于肉眼可见的大量重复计算导致向着递归与位运算方向思考，最后实在不会了

Leetcode题解：

可以将所有小于等于n的数字建立字典数存储起来，然后找到从跟节点到叶结点且满足不出现连续1的路径的数目

由图我们可以找到如下关系

1. 若a、b两个树中的节点中，a是b的子结点，并且他们的值都是1，那么所有经过a和b的从根节点到叶节点的路径一定包含连续的1。
2. 对于树中节点a、b，若其高度相同，节点值相同，且子树都为满二叉树，则包含无连续1的从根节点到叶节点的路径个数是相同的。

因为根节点为1的节点的子树可能只存在一个左子结点为0的完全二叉树，所以题目再次改变：

1. 如何计算根结点为 0 的满二叉树中，不包含连续 1 的从根结点到叶结点的路径数量
2. 如何将将字典树拆分为根结点为 0 的满二叉树和根结点不定的完全二叉树

算法：

对于问题1（动态规划dp–数位dp）：找到节点间与路径的关系：dp[t]表示高度为 t、根结点为 0 的满二叉树中，不包含连续 1 的从根结点到叶结点的路径数量。

可得到状态转移方程：

对于问题2：考虑到 01 字典树作为完全二叉树所具有的性质，我们可以从根结点开始处理。如果当前结点包含两个子结点，则用问题 1 的解决方法计算其左子结点中不包含连续 11 的从根结点到叶结点的路径数量，并继续处理其右子结点；如果当前结点只包含一个左子结点，那么继续处理其左子结点。

-—————————————————————————————————————

在实现中，需要注意如果已经出现连续 11 则不用继续处理；另外，叶结点没有子结点，需要作为特殊情况单独处理。

代码：

#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int dp[31];
    dp[0]=dp[1]=1;
    //预处理第i层满二叉树的路径数量
    for(int i=2;i<31;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    int pre=0,res=0;//pre记录上一层的根节点的值,res记录最终的路径数
    for(int i=29;i>=0;i--)//由于之前已经递归过了，所以直接从上到下加即可
    {
        int val=1<<i;
        if((n&val)!=0)
        {
            res+=dp[i+1];//先将左子树（满二叉树）的路径加到结果中
            if(pre==1)break;//上一层为1，这一层的右子树节点也为1，不合题意，舍去
            pre=1;//标记当前根节点为1
        }
        else pre=0;//无右子树，此时不能保证左子树是否为满二叉树，所以要在下一层继续再判断
        if(i==0)res++;//对于单个子叶节点1，予以加上
    }
    cout<<res<<endl;
    return 0;
}