联系我们 - 广告服务
您的当前位置:官网首页 > 资讯 > 热评 >

长乐国庆集训Day5

来源: 编辑: 时间:2019-10-08
导读: 通往藏宝库的通道打开了,走下一段长长的楼梯,钻过一条矮矮的地道,你和小可可终于来到了藏宝库的门前。随之而来的就是最后一个挑战,只要能打开宝库的门,里面的宝藏就是......

通往藏宝库的通道打开了,走下一段长长的楼梯,钻过一条矮矮的地道,你和小可可终于来到了藏宝库的门前。随之而来的就是最后一个挑战,只要能打开宝库的门,里面的宝藏就是你们的了。

宝库的门依然是通过机关打开,这个门很奇怪,是一个正方形,被划分成许多大小一致的正方形的小方格,这些方格不是红色就是白色,猛看上去这些方格组成了许多凯发网址娱乐红十字状的标志。根据藏宝图记载,只要找到门上最大的红十字,按下它中心的方格,宝库的门就能打开了。

红十字标志也是一个正方形,边长为*,其中k为非负整数。它的四条边与门的边平行,而且恰由门上的*个小方格组成。这里,红十字标志是以白色为底色,红色为十字的颜色。假设用1表示红色,用0表示白色。对应到计算机处理的数据中,就是除了正中列与正中行全为1外,其余方格均为0。

以下是几种不同大小的标志:

1*1:

1

 

3*3

010

111

010

 

5*5

00100

00100

11111

00100

00100

小可可被这个机关难到了,现在只有靠你了,请你帮助他在这个门上找到一个最大的红十字标志,输出它的边长即可。

本题输入量巨大,推荐使用以下输入方法:

scanf scanf;

for

for

a[i][j] = s[i][j] - '0';

其中n是宝库的门的边长,s是字符数组,a[i][j]是第i行第j列的数值。

对于每个询问输出一行表示答案。

5
00011
01011
11100
01001
00010
3 

对于30%的数据,n 100。

对于50%的数据,n 500。

对于100%的数据,n 2000。

用sum纪录子矩阵的值。

对于以为中心且长度为k的矩阵,如果是红十字,那么以为中心且长度为k-2的矩阵必然也是红十字。

所以可以枚举红十字的中心,求出以为中心的最大红十字的边长,具体可以用二分实现。

责任编辑:

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

网友评论:

在“\templets\demo\comments.htm”原来的内容全部删除,插入第三方评论代码,如果不需要评论功能,删除comments.html里面的内容即可
推荐使用友言、多说、畅言(需备案后使用)等社会化评论插件

Copyright © 2018 凯发网址娱乐凯发网址娱乐-凯发网娱乐下载-凯发网娱乐官方网站 All Rights Reserved Power by DedeCms
本站所有资讯来源于网络 如有侵权请联系QQ:9490489
Top