[CF][区间标记方法][暴力] codeforces 1028C Rectangles

比赛时候wa到哭,后来发现优化错了,把优化去掉玄学AC(这可是三个for啊这复杂度)

后来想一下,之所以能玄学过,就是因为题目保证了一定有解,如果无解的话那三个for还真有可能跑一遍,不说三个了两个跑一遍都够呛。。

我这里的玄学算法就是,对横纵坐标分别标记,当一个点在纵方向上被至少n-1个举行覆盖的时候才考虑这个横坐标,然后在这个横坐标上的所有纵坐标,也只有当被至少n-1个覆盖到的时候才考虑它,当然这只是必要条件而不是充分条件,然后对于一个要考虑的点遍历所有矩形(没错就是这么暴力)如果有超过1个没覆盖到这个点就退出直接不考虑。。。就这么超级暴力+剪枝,玄学过了cf的所有数据,emmm

#include 
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int maxn =132674*2+10;

int h[2*maxn+5],v[2*maxn+5];
int cx[2*maxn+5],cy[2*maxn+5];
int rec[maxn][4];

int n,cnt1,cnt2;
int HashX(int m)
{
    return lower_bound(cx+1,cx+1+cnt1,m)-cx;
}
int HashY(int m)
{
    return lower_bound(cy+1,cy+1+cnt2,m)-cy;
}
int main()
{
    int x1,y1,x2,y2;
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        cx[++cnt1]=x1,cx[++cnt1]=x2;
        cy[++cnt2]=y1,cy[++cnt2]=y2;
        rec[i][0]=x1,rec[i][1]=y1,rec[i][2]=x2,rec[i][3]=y2;
    }
    sort (cx+1,cx+1+cnt1);
    sort (cy+1,cy+1+cnt2);
    cnt1=cnt2=1;
    for (int i=2; i<=2*n; i++)
        if (cx[i]!=cx[cnt1])
            cx[++cnt1]=cx[i];
    for (int i=2; i<=2*n; i++)
        if (cy[i]!=cy[cnt2])
            cy[++cnt2]=cy[i];
    for (int i=1; i<=n; i++)
    {
        x1=HashX(rec[i][0]);
        y1=HashY(rec[i][1]);
        x2=HashX(rec[i][2]);
        y2=HashY(rec[i][3]);
        h[x1]++;
        h[x2+1]--;
        v[y1]++;
        v[y2+1]--;
    }

    for(int i=1; i<=cnt1+5; i++)
        h[i]+=h[i-1];
    for(int i=1; i<=cnt2+5; i++)
        v[i]+=v[i-1];

    for (int i=1; i<=cnt1; i++)if(h[i]>=n-1)
        for (int j=1; j<=cnt2; j++)if(v[j]>=n-1)
        {
            int tx=cx[i],ty=cy[j],flag=0;
            for (int i=1; i<=n; i++)
            {
                if(txrec[i][2]||tyrec[i][3])
                    flag++;
                if(flag>1)
                    break;
            }
            if(flag<=1)
            {
                cout<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据