【LuoguP1169 bzoj1057】[ZJOI2007]棋盘制作
2024-09-04 18:10:57
首先把矩阵转化一下,把横纵坐标和为偶数点的值取反,这样就转化成求最大的'0'或'1'矩阵。
这道题每个数字是在格子内的,不能在边界包含障碍点。
求最大的0矩阵时,把1作为障碍点。求1同理。
然后求最接近的就可以用树状数组求解啦~
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N=,Inf=(int)1e9;
int n,m,a1,a2;
int a[N][N],l[N][N],r[N][N],last[N][N],cl[N][N],cr[N][N]; int minn(int x,int y){return x<y ? x:y;}
int maxx(int x,int y){return x>y ? x:y;} void add(int x,int y,int d)
{
for(int i=y;i<=m;i+=(i&(-i))) cl[x][i]=maxx(cl[x][i],d);
for(int i=y;i>=;i-=(i&(-i))) cr[x][i]=minn(cr[x][i],d);
} int get(int x,int y,int tmp)
{
if(tmp==)
{
int ans=;
for(int i=y-;i>=;i-=(i&(-i))) ans=maxx(ans,cl[x][i]);
if(ans==) return ;
else return ans+;
}
else
{
int ans=Inf;
for(int i=y+;i<=m;i+=(i&(-i))) ans=minn(ans,cr[x][i]);
if(ans>=Inf) return m;
else return ans-;
}
} void solve(int tmp)
{
memset(cl,,sizeof(cl));
memset(cr,,sizeof(cr));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(a[i][j]==tmp) add(i,j,j);
}
memset(l[],,sizeof(l[]));
memset(r[],,sizeof(r[]));
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(a[i][j]==tmp) continue;
if(a[i-][j]==tmp)
{
l[i][j]=get(i,j,);//debug
r[i][j]=get(i,j,);//debug
last[i][j]=i-;
}
else
{
l[i][j]=maxx(l[i-][j],get(i,j,));
r[i][j]=minn(r[i-][j],get(i,j,));
last[i][j]=last[i-][j];
}
int xx=r[i][j]-l[i][j]+;
int yy=i-last[i][j];
a1=maxx(a1,minn(xx,yy)*minn(xx,yy));
a2=maxx(a2,xx*yy);
}
}
} int main()
{
freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
a1=;a2=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
if((i+j)%==) a[i][j]^=;
}
solve();
solve();
printf("%d\n%d\n",a1,a2);
return ;
}
最新文章
- js 获取鼠标选中值
- 在yii框架中如何连接数据库mongodb
- tmux常用命令
- LeetCode Alien Dictionary
- [转载]在线文档预览方案-Office Web Apps
- os模块
- JavaWeb学习总结(一)—JavaWeb开发入门及环境搭建
- XML HTML
- Differential Geometry之第二章曲线的局部理论
- JavaScript---网络编程(4)-Date、Math、Global和自定义对象
- flushall()函数的用法
- opencv中Mat类型数据操作与遍历
- ArcGis ToolBar为灰色
- 2017寒假零基础学习Python系列之 印子
- +function ($) { ";use strict";;}(window.jQuery);全面分析
- linux常用命令及使用技巧(二)
- appium自动化测试 环境搭建
- 【struts2】<;package>;的配置
- ASP.NET Core 如何设置发布环境
- linux任务计划cron