看了两个小时RMQ并位运算,对二进制勉勉强强有了个初步了解,不能说精通(可能今年CSP前都做不到精通),但是记熟板子做做题还是没有问题的

以下是正式题解,相信你看过了题目,我介绍的是ST表的做法(很简单)


—题目网址点这里—

如果你不想切出去也可以直接往下看(想看题解或代码往下翻翻)


分析

这题是真的完全没有掩饰的区间最值问题(RMQ),刚学的话拿来练板子还行(?),就是个模板题啦

这题就是板子改个大于小于的程度也搞不清为什么它是个绿题(模板题是黄题)

如果你学过ST表这题会又简单又好打,如果没有学过(就去学啊很重要的)

不会ST表打线段树当然也可以,但是线段树很长啊(发出蒟蒻的声音)

RMQ的模板在这,没学过可以去题解试试学一学,这里就不过多赘述

以及宣传姐妹博客她写的模板也可以去康康

或者往下看我的代码注释(就当练习代码阅读能力)

代码

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int n,m,a[],f[][];
inline int read()
{
int x=;
char c=getchar();
while (c>''||c<'') c=getchar();
do
{
x=x*+c-;
c=getchar();
}while(c<=''&&c>='');
return x;
} //快读,优化常数从我做起
inline void rmq()
{
for (int j=; (<<j)<=m; j++)
for (int i=; i+(<<j)-<=m; i++)
f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);
}//核心预处理,运用DP和二进制
int main()
{
m=read(); n=read();
for (int i=; i<=m; i++)
{
a[i]=read();
f[i][]=a[i];
//初始化
}
rmq();
int l,r;
for (int i=; i<=n; i++)
{
l=read(); r=read();
int k=floor(log(r-l+)/log());
//2^k=r-l+1
printf("%d ",min(f[l][k],f[r-(<<k)+][k]));
//这个地方用COUT会TLE!!凉凉 !!!
}
return ;//本命生日防我自己偷窥
}

好的就是这些

惯例

ありがとうございます

05-11 21:53