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

    第九届蓝桥杯国赛c++B组第二题

    作者: 栏目:未分类 时间:2020-11-14 9:00:16

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

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

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

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

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



    今天早起没事干,因为自己省赛的时候的垃圾状态没能打入决赛很不甘心,就随便点开了一道国赛真题看了看,发现确实不难。

    2.激光样式
    问题描述
    x星球的盛大节日为增加气氛,用30台机光器一字排开,向太空中打出光柱。
    安装调试的时候才发现,不知什么原因,相邻的两台激光器不能同时打开!
    国王很想知道,在目前这种bug存在的情况下,一共能打出多少种激光效果?
    显然,如果只有3台机器,一共可以成5种样式,即:
    全都关上(sorry, 此时无声胜有声,这也算一种)
    开一台,共3种
    开两台,只1种
    30台就不好算了,国王只好请你帮忙了。
    要求提交一个整数,表示30台激光器能形成的样式种数。
    注意,只提交一个整数,不要填写任何多余的内容。
    答案:2178309

    思路:用dfs来做。
    1.每一个灯都有两条路可走,打开或者不打开。
    2.当一个灯不打开的时候直接往下走就可以了。
    3.当一个灯打开的时候,前提是:它前面的灯不打开。(因为我们每次计算都是看的前面的灯,所以就保证了所有相邻的灯不同时打开,每个灯都会和它前面的灯比较。)

    弄好思路之后就可以写代码啦~
    一道dfs模板题~

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 40;
    int st[N];
    
    long long ans;
    
    void dfs(int x){
        if(x > 30){
            ans ++;
            return ;
        }
        dfs(x + 1);  //x不打开
        if(!st[x - 1]){
            st[x] = 1; //x打开
            dfs(x + 1);
            st[x] = 0;
        }
    }
    
    int main(){
        dfs(1);
        
        printf("%d",ans);
        
        return 0;
    }