题目链接(CF洛谷) | 强烈推荐博客中观看。

打的第一场 CF div.4

这个题就是那种想到点了就很很简单,没想到的话就……寄了的题(我就属于是寄了)。

1. 题意:

给你一个长度为 n (n<2105)n \ (\sum n < 2\cdot 10^5) 的数组 aa,问你在这个数组中,有多少个长度为 k+1 (1k<n)k + 1 \ (1\le k < n) 的区间,符合以下的条件:

20ai<21ai+1<22ai+2< ⁣<2kai+k注:i为这个区间开始的位置2^0 \cdot a_i < 2^1 \cdot a_{i + 1} < 2^2 \cdot a_{i + 2} < \dotsi < 2^k \cdot a_{i + k}\\ \footnotesize{注:i 为这个区间开始的位置}

2. 思路

暴力还是很好搞的,就把数组中每个可能的区间都算一遍就行了,但是看到 n<2105\sum n < 2\cdot 10^5 这个条件就知道要寄了。

所以我们需要一种能在 O(1)O(1) 的时间内判断区间是否符合条件的方法。(你要能搞出来 O(logn)O(\log n) 的也不是不可以)

可以发现,采用暴力的方法是因为每次这个区间的起始位都会变,所以数组的每一项前面要乘的数都不确定的。但如果我们能找到一种跟区间起始位置不相关的判断条件,这个问题就解决了。


接下来,重点来了

再仔细观察题目中给的条件,可以发现如果想要符合条件,数组中的前一项必须小于后一项的两倍,也就是:

ai<2ai+1 a_i < 2 \cdot a_{i + 1}

这个性质是和区间的位置,以及长度不相关的,只要两个相邻的数符合这个条件,那么它可以出现在任何长度,位置的区间中。

不过,这只是区间中的两个数,如果我们想要让一整个区间都合法,那么我们就需要让整个区间内,任意的 aia_i 都小于 2ai+12\cdot a_{i+ 1}

也就是说,只要长度为 kk 的区间内,有 k1k - 1 个符合 ai<2ai+1a_i < 2 \cdot a_{i + 1} 的数对,那这个区间就是符合条件的。

统计区间内的合法数量……并且需要在 O(1)O(1) 的时间内查询到结果,那这不就是前缀和吗?

于是我们很自然的就想到了判断完每个数对是否合法后,开一个前缀和数组 valid_sum[i] 来统计,到 ii 为止,有多少个符合条件的数对。

最后再搞个循环统计一下符合条件的区间就好了。

3. 代码:

代码还是比较简单的,这题的 ai<2ai+1a_i < 2 \cdot a_{i + 1} 这个点还是比较难想。

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
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d", &t);
while(t--){
int n, k;
scanf("%d%d", &n, &k);
//注意他给你的是 k,但是这个区间实际的长度是 k + 1
int a[n + 1];
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
bool valid[n + 1];
memset(valid, 0, sizeof(valid));
int valid_sum[n + 1];
memset(valid_sum, 0, sizeof(valid_sum));

for(int i = 1; i < n; i++){
if(a[i] < 2 * a[i + 1]){
valid[i] = true;
//判断和记录 a[i] 和 a[i + 1] 这个树对是否合法。
}
valid_sum[i] = valid_sum[i - 1] + valid[i];
//前缀和
}
int ans = 0;
for(int i = 1; i <= n - k; i++){
if(valid_sum[i + k - 1] - valid_sum[i - 1] == k){
//实际长度是 k + 1,所以 k + 1 再 - 1 = k
ans++;
}
}

printf("%d\n", ans);
}
}

最后,希望这篇题解对你有帮助,如果有问题可以通过评论区或者私信联系我。