题解 P3117 【[USACO15JAN]Cow Rectangles G】

素质玩家孙1超 · 2020-10-19 14:06:52 · 题解

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

我来一发 random_shuffle 的题解。

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

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

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

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

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

这个算法的效果：大概平均几十次随机之后就可以搞出正确答案，然而如果按照1s来算最多可以跑大约 1W 次左右，显然是随随便便就 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);
}