书海扬帆的博客

谁说暴力铁定拿低分!!!

本题数据非常弱,大模拟90分,除了最后一个点TLE了,其他都能很快AC,如果真是到了赛场上,没时间做这个题或者觉得代码难度较高的话,暴力的解法不妨一试!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,a[200100];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
int ans=a[x];
for(int j=x;j<=y;j++) ans=min(a[j],ans);
printf("%d ",ans);
}
return 0;
}

下面放一下ST表实现的正解,这是很标准的RMQ问题~

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m;
int st[100010][22];
int st_init(){
for(int j=1;1<<j<=m;j++)
for(int i=1;i+(1<<j)-1<=m;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int st_ask(int l,int r){
int k=log2(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) scanf("%d",&st[i][0]);
st_init();
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d ",st_ask(x,y));
}
return 0;
}

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int a[100100],logn[100100],st[100100][35],doing[36],n,m;
void init_st(){
logn[1]=0;
logn[2]=1;
for(int i=3;i<=n;i++) logn[i]=logn[i>>1]+1;
int j=0,cnt=1;
doing[0]=1;
while(cnt<=n){
cnt<<=1;
j++;
doing[j]=cnt;
}
for(int i=1;i<=n;i++){
int j=0,k=i-1;
st[i][0]=a[i];
while(k>0){
j++;
st[i][j]=max(st[i][j-1],st[i-doing[j-1]][j-1]);
k-=doing[j];
}
}
}
void ask(int l,int r){
int len=logn[r-l+1];
int ret=max(st[l+doing[len]-1][len],st[r][len]);
printf("%d\n",ret);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
init_st();
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
ask(l,r);
}
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:725.9k