小米oj 米兔的胡萝卜(ST表水题)

传送门

题意:

N 个米兔排成一排,每个米兔拥有的胡萝卜数可能为 0 ~ 9 中的任一整数,拥有胡萝卜最多的米兔可以获得由米司令奖励的品罗小怪兽料理机。M个询问,查询区间最大值

思路:

区间最大值也可以线段树的,但是这题数据量有点大,而且不带修改的,所以可以直接上ST表。

关于ST表

ST表就是一个来解决区间最值(Rmq)问题的算法,但是他不支持在线修改的.针对ST表,预处理是$O(nlogn)$但是查询$O(1)$的复杂度。这就是他的优良特性。

如何预处理ST表

ST表就是根据DP思想来求的,我们设$dp[i][j]$表示$[i,i+2^j-1]$的区间最大值.那么可知$ dp[i][0]=a[i]$.状态转移:将区间分为两段,一段为 $[i,i + 2^{j-1}-1]$,一段为

$[i + 2^{j-1},i + 2^{j-1} + 2^{j-1} - 1] $

即转移方程为 $dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1])$

如何查询

需要查询的区间为[i,j],则需要找到两个覆盖这个区间的最小幂区间。这两个区间可以重复,因为区间重复对最值是没有影响的

因为区间的长度为j-i+1,所以可以取k=log2(j-i+1)。

则$RMQ(A,i,j)=max(dp[i][k],dp[j-2^k+1][k])$。

本题代码

PS:这个垃圾oj的读入对C++很不友好,所以这里采用stringstream来进行转化。另外cin.geiline注意s的长度,wa了一晚上因为这个东西。。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

char s[10*maxn];

int dp[maxn][30];

int lg[maxn];

int N,M,R;

void Replace()

{

int len = strlen(s);

for(int i = 0;i < len;++i)

{

if(s[i] == ';') s[i] = ' ';

}

}

void ST()

{

for(int j = 1;(1 << j)<= N;++j)

for(int i = 1;i + (1 << j) - 1 <= N;++i)

dp[i][j] = max(dp[i][j - 1],dp[i + (1 << (j-1)) ][j - 1]);

return ;

}

int query(int l,int r)

{

l = max(1,l),r = min(r,N);

int k = lg[r-l+1];

return max(dp[l][k],dp[r-(1<<k) + 1][k]);

}

int main()

{

lg[1] = 0;

for(int i = 2;i < maxn;++i)

lg[i] = lg[i / 2] + 1;

while (cin.getline(s, 9*maxn)) {

Replace();

stringstream ss(s);

memset(dp,-1,sizeof dp);

ss >> N >> M >> R;

//cout << N << ' ' << M << ' ' << R << endl;

for(int i = 1;i <= N;++i)

ss >> dp[i][0];

ST();

for(int i = 0;i < M;++i)

{

int q;

ss >> q;

printf("%d%c",query(q-R,q+R),i == M - 1?'\n':' ');

}

}

return 0;

}

-------------本文结束感谢您的阅读-------------


本文标题:小米oj 米兔的胡萝卜(ST表水题)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2018年09月10日 - 20:09

最后更新:2018年12月20日 - 21:12

原始链接:https://statusrank.xyz/articles/b58b8411.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: