2020工大杯题解-G

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

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

题目描述

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

输入

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

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

$2\le N \le 10^5, 2 \le D \le 10^5, 1 \le T \le 719$

输出

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

样例输入

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

样例输出

1
3

题解

题目重述

$2\le N \le 10^5, 2 \le D \le 10^5, 1 \le T \le 719$

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

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

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

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

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

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

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

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

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

具体实现如下:

令 $f(i,j)$ 表示区间 $[i,i+2^j-1]$ 的最大值。

显然 $f(i,0)=a_i$ 。

根据定义式,第二维就相当于倍增的时候“跳了 $2^j-1$ 步”,依据倍增的思路,写出状态转移方程: $f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))$ 。

img

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

对于每个询问 $[l,r]$ ,我们把它分成两部分: $f[l,l+2^s-1]$ 与 $f[r-2^s+1,r]$ 。

其中 $s=\left\lfloor\log_2(r-l+1)\right\rfloor$ 。

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

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

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

题目解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}