比赛的时候又被数学题坑到了……

最后一场个人赛,并不知道是好是坏,但该来的还是要来……

题意:
给你一个序列,q个询问,每个询问为一个区间,问你这个区间的序列是否是Ladder序列。

所谓Ladder序列,就是A星序列,也可以说是峰型序列,包括非减和非增的断崖型。
比如说 1 2 2 1 或是 1 2 或是 2 1

思路:
我还在想到底得用什么数据结构……
实际上只要记录一下每个端点向左向右各能递减到的最大范围,再把端点值相加,看是否等于区间长度即可。

另一种想法是记录向左向右的峰,查询是检查两边中间的峰是否是同一个也可。

感觉第二个好理解一些。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int ldes[maxn];
int rdes[maxn];
int ary[maxn];

int main()
{
    int n, q, l, r;
    scanf("%d %d", &n, &q);
    each(i, n) scanf("%d", ary + i);
    each(i, n) if (ary[i - 1] >= ary[i]) ldes[i] = ldes[i - 1] + 1;
    else ldes[i] = 1;
    reach(i, n) if (ary[i] <= ary[i + 1]) rdes[i] = rdes[i + 1] + 1;
    else rdes[i] = 1;
    while (q--) {
        scanf("%d %d", &l, &r);
        if (ldes[r - 1] + rdes[l - 1] < r - l + 1)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}
Categories: 思维

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

思维

HDU 5486 Difference of Clustering

这种题目就是专门针对我的…… 思路简单,所需注意细节多。 题意: 给你 Read more…

思维

CodeForces 853 B Jury Meeting

思维题,老实说我并没有想出来,应该说是我想歪了…… 看了一个大佬的代码 Read more…

思维

HDU 6038 Function

多校第一场没有怎么想的题,然而实际上是很简单的……就是题意在理解上有点 Read more…