深圳营2期 X03-1班 day下午笔记
2024-07-24 15:24:29
发布于：广东
59阅读
0回复
0点赞
ST创建模版
ST=k=floor(log2(n))
void ST_create(){
for(int i=1;i<=n;i++){F[i][0]=a[i];}
int k=log2(n);
for(int j=1;j<=k;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);
}
}
}
双指针1
#include <bits/stdc++.h>
using namespace std;
int a[100005];
signed main(){
int n;
long long m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
long long mx=0,sum=0,st=1;
for(int i=1;i<=n;i++){
sum+=a[i];
while(sum>m){
sum-=a[st++];
}
mx=max(mx,sum);
}
cout<<mx;
return 0;
}
区间修改模板题
运用差分
#include<iostream>
using namespace std;
const int maxn = 1e5+10;
int a[maxn],b[maxn];
void chafeng(int b[],int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
int maxn,m;
cin>>maxn>>m;
for(int i=1;i<=maxn;i++)
{
cin>>a[i];
chafeng(b,i,i,a[i]);
}
int l,r,c;
while(m--)
{
cin>>l>>r>>c;
chafeng(b,l,r,c);
}
for(int i=1;i<=maxn;i++)
{
a[i]=a[i-1]+b[i];
cout<<a[i]<<" ";
}
return 0;
}
ST查询，复杂度O(1)
int ST_query(int L,int R){
int k=log2(R-L+1);
return max(F[L][k]),F[R-(1<<k)+1][k]);
}
ST表
ST代码
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class SparseTable {
using VT = vector<T>;
using VVT = vector<VT>;
using func_type = function<T(const T &, const T &)>;
VVT ST;
static T default_func(const T &t1, const T &t2) { return max(t1, t2); }
func_type op;
public:
SparseTable(const vector<T> &v, func_type _func = default_func) {
op = _func;
int len = v.size(), l1 = ceil(log2(len)) + 1;
ST.assign(len, VT(l1, 0));
for (int i = 0; i < len; ++i) {
ST[i][0] = v[i];
}
for (int j = 1; j < l1; ++j) {
int pj = (1 << (j - 1));
for (int i = 0; i + pj < len; ++i) {
ST[i][j] = op(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
}
}
}
T query(int l, int r) {
int lt = r - l + 1;
int q = floor(log2(lt));
return op(ST[l][q], ST[r - (1 << q) + 1][q]);
}
};
很好的题目1:「SCOI2007」降雨量
很好的题目2:「[USACO07JAN] 平衡的阵容 Balanced Lineup
我推荐做一做
ST算法的代码实现
代码中以求最大值为例，改为最小值只需要把max改成min即可
数据储存方式
const int MAXN=100050,MAXF=18;
int ar[MAXN];//原数组
int dp[MAXN][MAXF];//dp[i][j]表示从i开始往右2^j长度的区间内的最值
int LOG[MAXN];//LOG[i]=log2(i)向下取整
点击此图
完整模版
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100050,MAXF=18;
int ar[MAXN];
int dp[MAXN][MAXF];
int LOG[MAXN];
int main()
{
int n,q,L,R,d;
scanf("%d%d",&n,&q);
LOG[1]=0;
for(int i=2;i<=n;i++)
LOG[i]=LOG[i/2]+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&ar[i]);
dp[i][0]=ar[i];
}
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]);
while(q--)
{
scanf("%d%d",&L,&R);
d=LOG[R-L+1];
printf("%d\n",max(dp[L][d],dp[R-(1<<d)+1][d]));
}
return 0;
}
有帮助，赞一个