0%

2020工大杯题解-G

个人题解,和比赛官方无关,仅供参考

2020工大杯题解-G - L 同学的睡眠

题目描述

L同学日理万机,睡眠非常不规律,最早下午7点就会睡觉,最晚早上7点才去睡觉。但规律的睡眠才会使L同学精力充沛,善良的你快关心一下L同学吧!

输入

第一行为空格分隔的3个整数。在接下来的天里,细心的你将记录L同学每天的睡眠时间,从第2天开始,如果在你所记录的过去天内(包括当天)L同学最早和最晚睡眠时间差超过了分钟,那么善良的你需要对L同学说句“辛苦了!”。

第二行为空格分隔的个时间,依次表示天你所记录L同学的睡眠时间,采用HH:MM格式的24小时制表示。

输出

输出一个整数表示你一共需要对L同学说多少次“辛苦了!”

样例输入

5 3 30
23:30 1:20 1:07 0:50 19:00

样例输出

3

题解

题目重述

暴力查询的时间复杂度为 ,肯定是不行的。因此,需要一种区间最值查询的数据结构。因此,这是一个 RMQ 问题。

RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。

可以使用线段树、ST 表、单调栈解决问题。由于线段树和单调栈太简单了,没意思,这里介绍 ST 表。

ST 表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题 是指对于运算 ,满足 ,则对应的区间询问就是一个可重复贡献问题。例如,最大值有 ,gcd 有 ,所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外, 还必须满足结合律才能使用 ST 表求解。

ST 表基于 倍增 思想,可以做到 预处理, 回答每个询问。但是不支持修改操作。

基于倍增思想,我们考虑如何求出区间最大值。可以发现,如果按照一般的倍增流程,每次跳 步的话,询问时的复杂度仍旧是 ,并没有比线段树更优,反而预处理一步还比线段树慢。

我们发现 ,也就是说,区间最大值是一个具有“可重复贡献”性质的问题。即使用来求解的预处理区间有重叠部分,只要这些区间的并是所求的区间,最终计算出的答案就是正确的。

如果手动模拟一下,可以发现我们能使用至多两个预处理过的区间来覆盖询问区间,也就是说询问时的时间复杂度可以被降至 ,在处理有大量询问的题目时十分有效。

具体实现如下:

表示区间 的最大值。

显然

根据定义式,第二维就相当于倍增的时候“跳了 步”,依据倍增的思路,写出状态转移方程:

img

以上就是预处理部分。而对于查询,可以简单实现如下:

对于每个询问 ,我们把它分成两部分:

其中

根据上面对于“可重复贡献问题”的论证,由于最大值是“可重复贡献问题”,重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 ,可以保证答案的正确性。

以上内容以 CC BY-SA 4.0 协议和 SATA 协议提供在 OI-WIKI

贡献者:orzAtalod, Henry-ZHR, leoleoasd, Chrogeek, H-J-Granger, ouuan

题目解法

#include <iostream>
using namespace std;
const int logn = 17;
const int maxn = 100050;
int fmax[maxn][logn+1], fmin[maxn][logn+1], Logn[maxn];
void pre() {
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < maxn; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }
}
int querymax(int x,int y){
    return max(fmax[x][Logn[y - x + 1]], fmax[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int querymin(int x,int y){
    return min(fmin[x][Logn[y - x + 1]], fmin[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,d,t;
    int a,b;
    int output = 0;
    char _;
    cin>>n>>d>>t;
    for (int i = 1; i <= n; i++){
        cin>>a>>_>>b;
        fmax[i][0] = (a + 5) % 24 * 60 + b;
        fmin[i][0] = (a + 5) % 24 * 60 + b;
    }
    pre();
    for (int j = 1; j <= logn; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            fmax[i][j] = max(fmax[i][j - 1], fmax[i + (1 << (j - 1))][j - 1]);
            fmin[i][j] = min(fmin[i][j - 1], fmin[i + (1 << (j - 1))][j - 1]);
        }

    for (int i = 1; i <= n; ++ i){
        int mm = querymax( max(i - d + 1, 1), i);
        int mi = querymin( max(i - d + 1, 1), i);
        if (mm - mi  > t){
            output++;
        }
    }
    cout<<output<<endl;
    return 0;
}

欢迎关注我的其它发布渠道