猫史档案馆

其时我也是登了Luogu才想起今天是情人节的qaq

我留了三道题目特意在今天才A掉（Ynoi切不动），其中包含了很多有价值的方法技巧，给大家做个讲解，希望能够帮助到大家。

 

 

 

T1

 

www.luogu.com.cn/problem/P3353

这题题解通道关闭了，所以我没有事先写题解，在这里花一分钟口胡一下。

我们看到这其实就是一个固定的区间求区间和最大值的问题，当然可以用线段树做，但是不带修改还是离线直接出答案的，所以前缀和算法就行了。

唯一的一个坑点就是星星可以重合。这里特判一下即可。

关于前缀和算法我们之前已经尝试过使用Kitten实现了（进阶Kitten串讲），所以大家应该有了足够的理解。我们很好写出代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,w,x[100005],b[100005],maxn=-1,zd,s[100005];
int main(){
	n=read(),w=read();
	for(int i=1;i<=n;i++){
		int _1=read(),_2=read();
		x[_1]+=_2,zd=max(zd,_1);
	}
	for(int i=1;i<=zd;i++)s[i]=s[i-1]+x[i];
	for(int i=1;i<=zd-w+1;i++)maxn=max(maxn,s[i+w-1]-s[i-1]);
	printf("%d",maxn);
	return 0;
}

 

 

 

T2、T3

 

www.luogu.com.cn/problem/P7286

www.luogu.com.cn/problem/P7291

这俩题题面是一样的，只是一个加强版一个普通版，因此我们尝试使用两种方法。

题面有大图懒得放，所以跳过背景直接讲题。

这题的普通版题解也不让写了，所以也没有事先写题解。我接着口胡。

我们按照大小为第一关键字、位置为第二关键字从大到小排序。

排序之后，我们从前往后依次扫描 i，首先很明显 min(kx,ky) 的结果肯定是 ki。所以此时我们只需让 i+y 最大即可。那么我们用一个变量 y 来存储。最后两个结果乘起来，每次取最大值。

时间复杂度 O((n log n)+n)，瓶颈在于排序。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const ll SIZE=10000005;
struct node{ll val,w;}k[SIZE];
ll n,ans,y,cnt=1;
bool cmp(node a,node b){
	if(a.val==b.val)return a.w>b.w;
	return a.val>b.val;
}
int main(){
	n=read();
	for(ll i=1;i<=n;i++)
		k[i].val=read(),k[i].w=i,ans=max(ans,i*k[i].val);
	sort(k+1,k+n+1,cmp);
	while(cnt<n){
		y=max(y,k[cnt].w);
		ans=max(ans,k[++cnt].val*(k[cnt].w+y));
	}
	printf("%lld",ans);
	return 0;
}

 

 

数据加强之后这份代码过不去了，怎么办？

当然是要考虑如何不排序能求出结果啦qaq

终于有我写的题解了，放出来：

使用 ans 实时记录答案，用 y 记录第二个变量，从后往前枚举第一个变量 i。

卡常题，过不过看评测机心情。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const ll SIZE=10000005;
ll n,ans,y,k[SIZE];
int main(){
	n=read();
	for(ll i=1;i<=n;i++)
		k[i]=read(),ans=max(ans,i*k[i]);
	y=n;
	for(int i=n-1;i>=1;i--){
		ans=max(ans,min(k[i],k[y])*(i+y));
		if(k[y]<k[i])y=i;
	}
	printf("%lld",ans);
	return 0;
}

如何证明做法的正确性？

给一张图qaq

最后祝大家情人节快乐！

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct node{int x,b;}cl[100005];
int a[100005],n,w,ans,zd,cnt,q[100005],h=1,t,maxn,now;
void discrete(){
	for(int i=1;i<=zd;i++)
		if(a[i])cl[++cnt].x=i,cl[cnt].b=a[i];
}
int main(){
	n=read(),w=read();
	for(int i=1;i<=n;i++){
		int _1=read(),_2=read();
		a[_1]+=_2,zd=max(zd,_1);
	}
	discrete();
	for(int i=1;i<=cnt;i++){
		q[++t]=cl[i].x,now+=cl[t].b;
		while(q[t]-q[h]>=w)now-=cl[h].b,h++;
		maxn=max(maxn,now);
	}
	printf("%d",maxn);
	return 0;
}