最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 【BZOJ3885】【Usaco2015 Jan】Cow Rectangles 某奇怪的最大子矩形

    广告:

    #include <stdio.h>
    int main()
    {
    puts("转载请注明出处[vmurder]谢谢");
    puts("网址:blog.csdn.net/vmurder/article/details/44095063");
    }

    题意:

    坐标系上给出n个点,分”H”和”G”,1个整点坐标上最多1个点。
    现在求1个不包括”G”的包括尽可能多”H”的子矩形,然后在保证”H”最多的情况下还要问最小面积。
    输出”H”的最大数量,和保证”H”最多时的最小矩形面积。

    题解:

    我们发现由于坐标有限制[0,1000] (注意有”0”!!!),所以它是1个矩形。

    第1问:

    首先我们可以参照极大子矩形的做法算出所有的极大子矩形,然后保护1个fi,j表示[1,i][1,j]这个矩形内有多少”H”点,对1个矩形O(1)时间就能够算出”H”个数。

    第2问:

    以后我们可以把每一个极大子矩形过剩的边角砍掉来算面积。
    我们可以进行2分,看4个方向都能砍多少,check判的是矩形内”H”的个数是不是为0。

    固然,左右其实可以均摊O(1)算出来,诶我现在才发现都已加了logn了,左右消减还写甚么O(1)啊,噗Qwq。
    那就不说了,想知道的自己去看代码吧。

    还有就是下面不需要削。
    不写了不写了,不懂的留言吧。

    代码:

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define N 1010
    #define inf 0x3f3f3f3f
    using namespace std;
    int map[N][N],f[N][N];
    struct Data
    {
    int H,h; // 最高距离、最近白点
    int l,r; // 左右有效距离
    }s[N];
    int ansa,ansb=inf;
    int q[N];
    inline int getans(int a,int b,int c,int d){return f[d][b]-f[d][a]-f[c][b]+f[c][a];}
    inline int getarea(int a,int b,int c,int d)
    {
    int l=c,r=d,mid,ans;
    while(l<=r)
    {
    if(r-l<=3)
    {
    ans=l;
    for(int i=r;i>=l;i--)
    if(getans(a,b,c,i)==0)
    {ans=i;break;}
    break;
    }
    mid=l+r>>1;
    if(getans(a,b,c,mid)==0)l=mid;
    else r=mid-1;
    }
    return (b-a-1)*(d-ans-1);
    }
    int main()
    {
    int i,j,k;
    int a,b,c;
    scanf("%d",&c);
    char ss[5];
    while(c--)
    {
    scanf("%d%d%s",&a,&b,ss),a++,b++;
    if(ss[0]=='H')map[a][b]=1; // 可
    else map[a][b]=2; // 否
    }
    for(i=1;i<=1001;i++)
    {
    int temp=0;
    for(j=1;j<=1001;j++)
    {
    if(map[i][j]==1)temp++;
    f[i][j]=f[i-1][j]+temp;
    }
    }
    for(i=1;i<=1001;i++)s[i].h=inf;
    int l,r;
    for(i=1;i<=1001;i++)
    {
    for(j=1;j<=1001;j++)
    {
    if(map[i][j]==2)s[j].H=0,s[j].h=inf;
    else {
    s[j].H++;
    if(map[i][j]==1)s[j].h=1;
    else s[j].h++;
    }
    s[j].l=s[j].r=j;
    }
    l=1,r=0;
    for(j=1;j<=1001;j++)
    {
    while(l<=r&&s[q[r]].H>=s[j].H)s[j].l=s[q[r--]].l;
    while(s[j].l<j&&s[s[j].l].h>s[j].H)s[j].l++;
    q[++r]=j;
    }
    l=1,r=0;
    for(j=1001;j;j--)
    {
    while(l<=r&&s[q[r]].H>=s[j].H)s[j].r=s[q[r--]].r;
    while(s[j].r>j&&s[s[j].r].h>s[j].H)s[j].r--;
    q[++r]=j;
    }
    for(j=1;j<=1001;j++)
    {
    int ret=getans(s[j].l-1,s[j].r,i-s[j].H,i);
    if(ret>=ansa)
    {
    int temp=getarea(s[j].l-1,s[j].r,i-s[j].H,i);
    if(ret==ansa)ansb=min(ansb,temp);
    else ansa=ret,ansb=temp;
    }
    }
    }
    printf("%d
    %d
    "
    ,ansa,ansb);
    return 0;
    }
    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » 【BZOJ3885】【Usaco2015 Jan】Cow Rectangles 某奇怪的最大子矩形

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级