2020牛客寒假算法基础集训营5

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2020牛客寒假算法基础集训营5，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含933字，纯文字阅读大概需要2分钟。

内容图文

E碎碎念

 

 

思路：

题目中有一句话很重要：

 

所以一旦这一发是错的，那么下一发一定是对的。即上一发错，这一发对。

dp[i][0]的含义是：对于第i这一句是不行的

dp[i][1]的含义是：对于第i这一句是行的

两个转移方程： dp[i][0] = dp[i-x][1],由于你能不能行呀这句话是连着说x句的,所以这一句是不行的话，那么i-x+1~i都是不行的，所以转移到的是i-x这一句是行的

　　　　　　　dp[i][1] = dp[i-1][0]+dp[i-1][1]，对于这一句是行的，那么就没什么要求，上一句无论是什么都行

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int maxn= 1e5+10;
const int mod = 1e9+7;
ll dp[maxn][2],sum[maxn];
int main(){
    int x;
    cin>>x;
    int q;
    cin>>q;
    dp[0][1] =1;//初始化
    for(int i=1;i<=maxn;i++){
        if(i>=x) dp[i][0] = dp[i-x][1];
        dp[i][1] = (dp[i-1][0]+dp[i-1][1])%mod;
    }
    for(int i=1;i<=maxn;i++){
        sum[i]=(sum[i-1]+dp[i][0]+dp[i][1])%mod;
    }
    
    while(q--){
        int l,r;
        scanf("%d%d",&l,&r);
        cout<<(sum[r]-sum[l-1]+mod)%mod<<endl;//这个一定不能少，少了就只有33%的通过率
    }
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的2020牛客寒假算法基础集训营5全部内容，希望文章能够帮你解决2020牛客寒假算法基础集训营5所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---