自动搬运

查看原文

来自洛谷，原作者为

	素质玩家孙1超 天道酬勤！

搬运于2025-08-24 21:45:28，当前版本为作者最后更新于2020-10-19 14:06:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

别的题解的做法都好正经啊，

我来一发 random_shuffle 的题解。

题意：一个平面上有好多点，分别为 $G$ 和 $H$ ，求不包含 $G$ 且包含 $H$ 最多的子矩阵，并输出包含多少个 $H$ 和所有情况下最少的面积。

我一看到 $n \leq 500$ 就想到了那个神奇的 random_shuffle 。

如果你不知道 random_shuffle ，这个函数就是c++内置的随机打乱一个数组的函数。

那么直接考虑答案基于排列顺序的假贪心。

我们直接按照数组里面的排列顺序加入点，若这个点加入了后子矩阵中包含了至少一个 $G$ ，那么就不加入这个点，否则贪心加入。

这个算法的效果：大概平均几十次随机之后就可以搞出正确答案，然而如果按照1s来算最多可以跑大约 $1$W 次左右，显然是随随便便就 $AC$ 掉了。

用二位树状数组优化一次随机的复杂度是 $O(n\times \log ^2(n))$ 。 ($n \leq 500$ )

代码：

#include<bits/stdc++.h>
using namespace std;
inline int R()
{
	char c;int res,sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;res=c-'0';
	while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	return res*sign;
}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
const int Maxn=505;
struct point 
{
	int x,y;
}a[Maxn],b[Maxn];
#define lowbit(x) (x&-x)
int n,ans=1,M=0,top1,top2,V[Maxn*2][Maxn*2];
void up(int x,int y)
{
	for(int i=x;i<=1001;i+=lowbit(i))
	for(int j=y;j<=1001;j+=lowbit(j))
	V[i][j]++;
}
inline int sum(int x,int y)
{
	int res=0;
	for(int i=x;i>0;i-=lowbit(i))
	for(int j=y;j>0;j-=lowbit(j))
	res+=V[i][j];
	return res;
}
inline void work()
{
	random_shuffle(a+1,a+top1+1);
	int Mix=a[1].x,Max=a[1].x,Miy=a[1].y,May=a[1].y;
	int p1,p2,p3,p4,res=1;
	for(int i=2;i<=top1;i++)
	{
		p1=Mix;p2=Max;p3=Miy;p4=May;
		Mix=min(Mix,a[i].x);Max=max(Max,a[i].x);
		Miy=min(Miy,a[i].y);May=max(May,a[i].y);
		int p=sum(Max,May);
		p+=sum(Mix-1,Miy-1)-sum(Mix-1,May)-sum(Max,Miy-1);
		if(p){res--;Mix=p1;Max=p2;Miy=p3;May=p4;}
		res++;
	}
	if(res==ans)
	{
		M=min(M,(Max-Mix)*(May-Miy));
	}
	else if(res>ans)
	{
		ans=res;
		M=(Max-Mix)*(May-Miy);
	}
}
int main()
{
	n=R();int x,y;
	for(int i=1;i<=n;i++)
	{
		x=R()+1;y=R()+1;
		char c;
		while((c=getchar())!='H'&&c!='G');
		if(c=='H') 
		{
			a[++top1].x=x;
			a[  top1].y=y;
		}
		else 
		{
			b[++top2].x=x;
			b[  top2].y=y;
			up(x,y);
		}
	}
	for(int i=1;i<=1000;i++)work();
	printf("%d\n%d\n",ans,M);
}