当前位置 博文首页 > 文章内容

    【Codeforces 1369D】TediousLee

    作者: 栏目:未分类 时间:2020-07-14 9:00:29

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    题目链接

    点我呀

    翻译

    高度为 \(i+1\) 的一棵 \(RDC\) 树可以由高度为 \(i\) 的一棵 \(RDC\) 树通过这样的规则构造出来:

    在高度为 \(i\)\(RDC\) 中,对于只有一个孩子的节点,加上两个孩子节点,没有孩子的节点加上一个节点。

    问你高度为 \(h\)\(RDC\) 树有多少个互不重叠的爪型的节点。

    题解

    递推题。

    动手画一下的话,会发现高度为 \(h\)\(RDC\) 树,总是由两个高度为 \(h-2\)\(RDC\) 树和一个高度为 \(h-1\)\(RDC\) 以及一个根节点

    构成的。

    选取爪型的时候,应该尽量让选择的爪的根节点在子树下方,这样整个树的根节点就能跟三个子树的根节点再形成一个爪了。

    所以思路就是,设置一个 \(ans[N]\) 表示高度为 \(h\)\(RDC\) 树能有多少个爪,以及选出的爪中有没有选树的根节点。

    然后,\(ans[i] = ans[i-2]*2+ans[i-1]+can\), 其中如果高度为 \(i-2\)\(i-1\)\(RDC\) 树都没有选根节点作为爪的根的话,

    \(can=1\),否则 \(can = 0\)

    最后输入 \(n\), 直接输出 \(ans[n]*4\) 即可。

    代码

    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    const int N = 2e6;
    const LL MOD = 1e9+7;
    
    LL ans[N+10];
    bool used[N+10];
    
    int main()
    {
        ans[1] = 0;ans[2] = 0;
        for (int i = 3;i <= N; i++){
            if (!used[i-1] && !used[i-2]){
                ans[i] = ans[i-2]*2%MOD + ans[i-1] + 1;
                ans[i] %= MOD;
                used[i] = true;
            }else{
                ans[i] = ans[i-2]*2%MOD + ans[i-1];
                ans[i] %= MOD;
            }
        }
        int T;
        scanf("%d",&T);
        while (T--){
            int n;
            scanf("%d",&n);
            printf("%lld\n",ans[n]*4%MOD);
        }
        return 0;
    }