专栏文章

8-6 ST表与树状数组测试总结

rren_gao_zu
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miohcm0e
此快照首次捕获于
2025/12/02 19:13
3 个月前
此快照最后确认于
2025/12/02 19:13
3 个月前
查看原文
questionExpected scoreActual score
T1100100
T2100100
T3100100
T4100100
T510088
T610010
T710040
T800

错题总结

T5:

思路

我们可以用ST表来维护前缀和。
我们先来看下这段代码：
CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,lg[N],m,f[N][30],a[N],ans,sum[N];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		f[i][0]=sum[i];
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
		f[i][0]=sum[i];
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=25;j++){
		for(int i=0;i+(1<<j)-1<=n;i++){
			f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int l;
		if(i<=m)l=0;
		else l=i-m;
		int len=i-l+1;
		int j=lg[len];
		int mi=min(f[l][j],f[i-(1<<j)+1][j]);
		ans=max(ans,sum[i]-mi);
	}cout<<ans;
	return 0;
}
看这段代码，是不是感觉能AC？但实际上：
第九个测试点竟然WA了！！！
然后我们下载测试点看一看：

in:

CPP
5
-1 -1 -1 -1 -1

out:

CPP
-1
然而，我们上面的那段代码输出的是0，那么我们可以面向数据编程，在最后输出ans改成：
CPP
if(ans==0)
    cout<<-1;
else cout<<ans;
开个玩笑，下面才是正经的。
我们来思考一下：
题目要求：1≤k≤m1\le k \le m，也就是小Z必须要吃。而上面的代码是可以选择不吃的，所以会输出0。
所以，我们要加上一段：
CPP
bool flag=0;
int maxn=-1e18;
for(int i=1;i<=n;i++){
	if(a[i]>=0){
		flag=1;
		break;
	}
	maxn=max(maxn,a[i]);
}
if(flag==0){
	cout<<maxn;
	return 0;
}
这段代码是什么意思？如果这些蛋糕的幸运值都小于0，但必须要吃，所以就选择吃幸运值大的那一块，不然吃多块蛋糕，幸运值会越来越小。

AC code

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,lg[N],m,f[N][30],a[N],ans,sum[N];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;

	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		f[i][0]=sum[i];
	}
	bool flag=0;
	int maxn=-1e18;
	for(int i=1;i<=n;i++){
		if(a[i]>=0){
			flag=1;
			break;
		}
		maxn=max(maxn,a[i]);
	}
	if(flag==0){
		cout<<maxn;
		return 0;
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
		f[i][0]=sum[i];
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=25;j++){
		for(int i=0;i+(1<<j)-1<=n;i++){
			f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int l;
		if(i<=m)l=0;
		else l=i-m;
		int len=i-l+1;
		int j=lg[len];
		int mi=min(f[l][j],f[i-(1<<j)+1][j]);
		ans=max(ans,sum[i]-mi);
	}cout<<ans;
	return 0;
}

T6:

思路

维护树状数组，计算每个区间的逆序对个数，然后取最大值。
注意：是最大值，不是求和！！！（样例要不要这么水呀）

AC code

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,sum[N],ans,cnt;
int b[N],a[N];
map<int,int>mp;
int lowbit(int x){
	return x & -x;
}
int get_sum(int x){
	int res=0;
	while(x){
		res+=sum[x];
		x-=lowbit(x);
	}
	return res;
}
void modify(int x,int val){
	while(x<=n){
		sum[x]+=val;
		x+=lowbit(x);
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	int idx=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++){
		int x=lower_bound(b+1,b+idx+1,a[i])-b;
		ans=max(ans,get_sum(idx)-get_sum(x));
		modify(x,1);
	}cout<<ans+1;
	return 0;
}

T7:

考试结束还差11min的时候想到了二分+ST表，于是在最后2min的时候写出了下面的代码：
CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,sumf[N],sums[N],f[N][25],lg[N];
struct node{
	int f,s;
}a[N];
int ans=1e18;
bool check(int l,int r){
	int fr=sumf[r],fl=sumf[l-1];
	if(fr-fl>=m)return 1;
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].f>>a[i].s;
		sumf[i]=sumf[i-1]+a[i].f;
		f[i][0]=a[i].s;
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int l=1,r=i,mid;
		while(l<=r){
			mid=l+r>>1;
			if(check(l,r)){
				l=mid+1;
				int len=i-mid+1,j=lg[len];
				ans=min(ans,max(f[l][j],f[i-(1<<j)+1][j]));
			}
			else r=mid-1;
		}
	}cout<<ans;
	return 0;
}
样例也过了，结果只有40分。
但其实，这题只是一道二分答案的题目。

AC code

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int f[N],s[N],n,m;
bool check(int x){
	int sum=0;
	for(int i=1;i<=n;i++){
		if(s[i]>x)sum=0;
		else sum+=f[i];
		if(sum>=m)return 1;
	}return 0;
}
int ma,ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>f[i]>>s[i];
	for(int i=1;i<=n;i++)ma=max(ma,s[i]);
	int l=1,r=ma,mid;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...