题目链接:Codeforces 466D Increase Sequence
题目大意:给定一个序列,现在可以选中一段区间,使得整段区间上每个位置数加1,要求最后每个位置都为h,并且选中的区间不能有相同l或则r。
解题思路:因为每个位置最多有一个起始和一个终止(区间)。
- ai和ai+1差的绝对值超过1,则肯定是不行的,
- ai+1−ai=1,那么一定要从i+1的位置新起一段区间
- ai+1−ai=−1,那么一定要在i+1的位置上终止一段区间,C(1ai)
- ai+1−ai=0,可以不变,也可以终止并新起一段。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2005;
const ll mod = 1e9+7;
int N, H, arr[maxn];
int solve () {
N++;
ll ret = 1;
for (int i = 1; i <= N; i++) {
int t = arr[i] - arr[i-1];
if (t > 1 || t < -1)
return 0;
else if (t == 0)
ret = ret * (arr[i] + 1) % mod;
else if (t == -1)
ret = ret * arr[i-1] % mod;
}
return ret;
}
int main() {
scanf("%d%d", &N, &H);
for (int i = 1; i <= N; i++) {
scanf("%d", &arr[i]);
arr[i] = H - arr[i];
}
printf("%d\n", solve());
return 0;
}
分享到:
相关推荐
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
题目大意:给出一个数列 a ,求出 题目分析:如果暴力的话显然时间复杂度是 n * n 的,我们应该想办法去优化,比赛的时候想用线段树,但是不会在维护异或的前提下区间加法,也想过用矩阵维护,但丝毫没什么用呀,...
Codeforces 1925D Good Trip 题解
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
268C Beautiful Sets of Points 传送门 题意:在n*m的格点图里尽量多的选点,使点之间两两距离不为整数,同时不能选(0,0). 构造水题了,很明显每行/列最多放一个,那么最多应该放min(n,m)+1个,由于0,0不能选,直接...
题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp,因为题目已经明确了需要求什么,所以我们不妨设 dp[ i ][ j ] 为区间 [ i , j ] 合并后的最短数列的长度,因为...
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Educational Codeforces Round 157D. XOR Construction
codeForces C ++中的Code Force解决方案
波兰球和游戏: ://codeforces.com/problemset/problem/755/B 问题779 B.怪异的舍入: : 问题845 A.国际象棋锦标赛: : 问题884 B.日语填字游戏反击: : 问题985 A.国际象棋的放置: : 问题1042 A.长凳: : 问题1105...
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces Round #620 (Div. 2) [codeforces 1304A] Two Rabbits 整除+模 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.ml/contest/1304/problem/A ...
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
Codeforces 185A - Plant 全测试点49个
Codeforces 149 D-Coloring Brackets,动态规划求解
Codeforces扩展包 是否曾经想让Codeforce拥有方便的快捷键,自动更新排行榜,可以按需隐藏/显示的问题标签,更好的站点导航,深色主题或以上所有功能? 这些和更多功能可以在Codeforces ++中获得! 该扩展是开源的,...