Codeforces Round #248 (Div. 1)——Nanami's Digital Board
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #248 (Div. 1)——Nanami's Digital Board，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1481字，纯文字阅读大概需要3分钟。
内容图文
- 题意：
给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;
}
Codeforces Round #248 (Div. 1)——Nanami's Digital Board
原文：http://www.cnblogs.com/hrhguanli/p/4038918.html
内容总结
以上是互联网集市为您收集整理的Codeforces Round #248 (Div. 1)——Nanami's Digital Board全部内容，希望文章能够帮你解决Codeforces Round #248 (Div. 1)——Nanami's Digital Board所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】