赶牛入圈(跑的飞快,53ms)
首先,正方形边长越大,包含的三叶草数量只会更多不会更少,即满足单调性,可以进行二分答案,接下来要求解的就是:给定三叶草数$n$和正方形边长$k$,求是否存在一个正方形包含不少于$c$棵三叶草
考虑正方形边长已知,那么枚举左上角的点就可以知道整个正方形了,预处理二维前缀和容斥一下就$O(P^2logP)$解决了(P是三叶草坐标值域大小)。
但问题不是这么简单-三叶草的坐标是$[1,10000]$中的整数,所以会时间空间双起飞。$n\le 500$,那么离散化即可将空间控制到$O(n)$大小。
那么问题又来了-离散化之后二维前缀和变得非常奇怪,因为离散化之后的值和$k$没有直接关系了(而且和另外几篇题解重复了)
同样是先二分答案,然后枚举离散化后起始行$start$,则离散化后终止行$end=prex(start+k-1)$,$prex(val)$表示不超过val的最大的出现过的坐标离散化后编号(可见代码,语文太差了呜呜呜,反正就是在$O(logn)$的时间里求出终止行)
然后直接双指针扫一下,更具体的:
1. 建立指针$l=r=1,$当前矩阵中三叶草数量$s=0,[l,r)即表示当前处理的纵坐标区间$
2. 推进$r$直到$l,r$间的距离超过$k$,同时将$r$一段的三叶草数量加入$s$
3. 如果$s\ge k$,则存在一个正方形包含不少于$c$棵三叶草,返回check成功
4. 将$l$推进一步,同时将$l$一段的三叶草数量减掉
5. 重复234直至$l$超过离散化后不同的数的数量
用对列做前缀和快速计算指针推进导致的$s$变化,时间复杂度$O(logn\times n\times(logn+n))=O(n^2logn)$只跑了$53ms$。(好像如果二维前缀和那个可能会再多一个log?)
代码当然是要贴的,我说的确实不够清楚
#include<iostream>
#include<cstdio>
#include<algorithm>
typedef long long ll;
typedef std::pair<ll,ll> pll;
#define MAXN 511
ll a[MAXN][MAXN],c,n,cntx,cnty;//列的前缀和,c,n,x离散化后不同的数的个数,y离散化后不同的数的个数
ll fx[MAXN],fy[MAXN];
pll p[MAXN];
ll placex(ll val)//val在x坐标上离散化后的值
{
return std::lower_bound(fx+1,fx+cntx+1,val)-fx;
}
ll placey(ll val)//val在y坐标上离散化后的值
{
return std::lower_bound(fy+1,fy+cnty+1,val)-fy;
}
bool check(ll k)//是否存在边长为k的正方形包含不少于$c$棵三叶草
{
for(ll start=1;start<=cntx;++start)
{
ll end=placex(fx[start]+k-1);
while(end>cntx||fx[end]>fx[start]+k-1)--end;//找end
//printf("k=%lld s=%lld t=%lld\n",k,start,end);
ll l=1,r=1,s=0;//双指针
while(l<=cnty)
{
while(r<=cnty&&fy[r]-fy[l]+1<=k)
{
s+=a[end][r]-a[start-1][r];
++r;
}
if(s>=c)return 1;
s-=a[end][l]-a[start-1][l];
++l;
}
}
return 0;
}
int main()
{
scanf("%lld%lld",&c,&n);
for(ll i=1;i<=n;++i)
{
ll x,y;
scanf("%lld%lld",&x,&y);
fx[i]=x,fy[i]=y;
p[i]=pll(x,y);
}
std::sort(fx+1,fx+n+1),std::sort(fy+1,fy+n+1);//离散化
cntx=std::unique(fx+1,fx+n+1)-fx-1;
cnty=std::unique(fy+1,fy+n+1)-fy-1;
for(ll i=1;i<=n;++i)
++a[placex(p[i].first)][placey(p[i].second)];
for(ll i=1;i<=cntx;++i)//对列做前缀和
for(ll j=1;j<=cnty;++j)
a[i][j]+=a[i-1][j];
unsigned l=1,r=10000,mid;//二分答案
while(l<r)
{
mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld",r);
return 0;
}
emmm没看你的方法不过我按照常规方法写的
36ms
“考虑正方形边长已知,那么枚举左上角的点就可以知道整个正方形了”
点不一定在左上角吧,比如4个点可以在正方形边的中点上
这句话确实有问题 但是题解没用这种做法