「ZJOI2007」「LuoguP1169」棋盘制作(并查集
题目描述
国际象棋是世界上最古老的博弈游戏之一,和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想,棋盘是一个8×88 \times 88×8大小的黑白相间的方阵,对应八八六十四卦,黑白对应阴阳。
而我们的主人公小Q
,正是国际象棋的狂热爱好者。作为一个顶尖高手,他已不满足于普通的棋盘与规则,于是他跟他的好朋友小W
决定将棋盘扩大以适应他们的新规则。
小Q
找到了一张由N×MN \times MN×M个正方形的格子组成的矩形纸片,每个格子被涂有黑白两种颜色之一。小Q
想在这种纸中裁减一部分作为新棋盘,当然,他希望这个棋盘尽可能的大。
不过小Q
还没有决定是找一个正方形的棋盘还是一个矩形的棋盘(当然,不管哪种,棋盘必须都黑白相间,即相邻的格子不同色),所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积,从而决定哪个更好一些。
于是小Q
找到了即将参加全国信息学竞赛的你,你能帮助他么?
输入输出格式
输入格式:
包含两个整数NNN和MMM,分别表示矩形纸片的长和宽。接下来的NNN行包含一个N ×MN \ \times MN ×M的010101矩阵,表示这张矩形纸片的颜色(000表示白色,111表示黑色)。
输出格式:
包含两行,每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积,第二行为可以找到的最大矩形棋盘的面积(注意正方形和矩形是可以相交或者包含的)。
输入输出样例
说明
对于20%20\%20%的数据,N,M≤80N, M ≤ 80N,M≤80
对于40%40\%40%的数据,N,M≤400N, M ≤ 400N,M≤400
对于100%100\%100%的数据,N,M≤2000N, M ≤ 2000N,M≤2000
题解
某天中午去吃超好吃的鱼粉,路上,一位选手问我们,
你知道悬线法是什么吗?!
我不知道,于是我问他是干嘛的,于是他洋洋洒洒的摆出了这道题。
我kiao,这不就是我校传了好几届的最大矩阵题吗?!
然后我把那道题改造了一下,成功AC。
————————————
跟原题不同的是,我们传承前缀和时的条件改为此位和上一位不同。
并且和左右接通时,判断是否不同。如果相同就不连。
/*
qwerta
P1169 [ZJOI2007]棋盘制作
Accepted
100
代码 C++,1.5KB
提交时间 2018-10-14 21:34:02
耗时/内存
29ms, 688KB
*/
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define R register
int s[];
int a[];
struct emm{
int nod,v;
};
struct cmp{
bool operator()(emm qaq,emm qwq){
return qaq.v<qwq.v;
}
};
priority_queue<emm,vector<emm>,cmp>q;
int siz[],fa[];
bool sf[];
int fifa(int x)
{
if(fa[x]==x)return x;
return fa[x]=fifa(fa[x]);
}
inline void con(int x,int y)
{
int u=fifa(x),v=fifa(y);
siz[u]+=siz[v];
fa[v]=u;
return;
}
inline int read()
{
char ch=getchar();
int x=;
while(!isdigit(ch))ch=getchar();
if(isdigit(ch)){if(ch=='')x=;ch=getchar();}
return x;
}
int main()
{
//freopen("a.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
int ansz=,ansc=;
for(R int i=;i<=n;++i)
{
for(R int i=;i<=m;++i)
{
int x=read();
if(a[i]+x==)s[i]++;
else s[i]=;
a[i]=x;
q.push((emm){i,s[i]});
}
for(R int i=;i<=m;++i)
fa[i]=i,siz[i]=,sf[i]=;
a[]=a[m+]=;
while(!q.empty())
{
int i=q.top().nod,x=q.top().v;q.pop();
sf[i]=;
if(a[i-]+a[i]==&&sf[i-])
con(i-,i);
if(a[i]+a[i+]==&&sf[i+])
con(i,i+);
int fi=fifa(i),mi=min(siz[fi],x);
ansz=max(ansz,mi*mi);
ansc=max(ansc,siz[fi]*x);
}
}
printf("%d\n%d",ansz,ansc);
return ;
}
最新文章
- android 项目学习随笔十一(ListView下拉刷新提示)
- Mysql-学习笔记(==》权限管理 十 三)
- 机器人学 —— 机器人感知(Gaussian Model)
- 实例源码--Android自定义Gallery动画效果
- (原+转)Eclipse中Android调用OpenCv
- hdu5338 ZZX and Permutations
- MySQL长短密码
- PHP操作MySQL数据库之天龙八部 -- 七贱下天山 -- 六脉神剑
- linux shell 判断文件是否存在等符号
- spring-boot-devtools在Idea中热部署方法
- idea用到的快捷键
- 04 Zabbix核心概念回顾
- SpringBoot中配置起动时的数据库初始化角本
- 阻止ajax缓存方法
- 如何在Linux中tomcat下运行一个web项目
- windows 下安装nodejs 要怎么设置环境变量
- zabbix的日常监控-自动发现端口并监测(服务器开启的所有端口或监控指定端口)(十三)
- OpenMeetings(4)----新用户注册
- mvc结合web应用实例分析
- nvm安装