Codeforces Round #248 (Div. 1)??Nanami's Digital Board_html/css_WEB-ITnose

php中文网
发布: 2016-06-24 12:01:49
原创
1334人浏览过

题目连接

  • 题意:
    给n*m的0/1矩阵,q次操作,每次有两种:1)将x,y位置值翻转 2)计算以(x,y)为边界的矩形的面积最大值
    (1?≤?n,?m,?q?≤?1000)
  • 分析:
    考虑以(x,y)为下边界的情况,h=(x,y)上边最多的连续1的个数。那么递减的枚举,对于当前hx,只需要看两侧能到达的最远距离,使得h(x,ty)不大于h即可。之后的枚举得到的两侧距离大于等于之前的,所以继续之前的两侧距离继续枚举即可。
  • const int maxn = 1100;int n, m, q;int ipt[maxn][maxn];int up[maxn][maxn], dwn[maxn][maxn], lft[maxn][maxn], rht[maxn][maxn];int len[maxn];void updaterow(int r){    FE(j, 1, m)        lft[r][j] = (ipt[r][j] == 1 ? lft[r][j - 1] + 1 : 0);    FED(j, m, 1)        rht[r][j] = (ipt[r][j] == 1 ? rht[r][j + 1] + 1 : 0);}void updatecol(int c){    FE(i, 1, n)        up[i][c] = (ipt[i][c] == 1 ? up[i - 1][c] + 1 : 0);    FED(i, n, 1)        dwn[i][c] = (ipt[i][c] == 1 ? dwn[i + 1][c] + 1 : 0);}int maxarea(int s, int len[], int thes){    int l = s, r = s, ret = 0;    FED(i, len[s], 1)    {        while (l >= 1 && len[l] >= i)            l--;        while (r <= thes && len[r] >= i)            r++;        ret = max(ret, i * (r - l - 1));    }    return ret;}int main(){    while (~RIII(n, m, q))    {        FE(i, 1, n) FE(j, 1, m)            RI(ipt[i][j]);        FE(i, 1, n)            updaterow(i);        FE(j, 1, m)            updatecol(j);        REP(kase, q)        {            int op, x, y;            RIII(op, x, y);            if (op == 1)            {                ipt[x][y] ^= 1;                updatecol(y);                updaterow(x);            }            else            {                int ans = max(maxarea(y, up[x], m), maxarea(y, dwn[x], m));                FE(i, 1, n)                    len[i] = lft[i][y];                ans = max(ans, maxarea(x, len, n));                FE(i, 1, n)                    len[i] = rht[i][y];                ans = max(ans, maxarea(x, len, n));                WI(ans);            }        }    }    return 0;}
    登录后复制


    HTML速学教程(入门课程)
    HTML速学教程(入门课程)

    HTML怎么学习?HTML怎么入门?HTML在哪学?HTML怎么学才快?不用担心,这里为大家提供了HTML速学教程(入门课程),有需要的小伙伴保存下载就能学习啦!

    下载
    来源:php中文网
    本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
    最新问题
    开源免费商场系统广告
    热门教程
    更多>
    最新下载
    更多>
    网站特效
    网站源码
    网站素材
    前端模板
    关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新 English
    php中文网:公益在线php培训,帮助PHP学习者快速成长!
    关注服务号 技术交流群
    PHP中文网订阅号
    每天精选资源文章推送
    PHP中文网APP
    随时随地碎片化学习

    Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号