Wannafly模拟赛 A.矩阵(二分答案+hash)

矩阵

时间限制:1秒 空间限制:131072K

题目描述

给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。

输入描述:

第一行两个整数n, m代表矩阵的长和宽;
接下来n行,每行m个字符(小写字母),表示矩阵;

输出描述:

输出一个整数表示满足条件的最大正方形的边长。

示例1

输入

5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl

输出

3

备注:

对于30%的数据,n,m≤100;
对于100%的数据,n,m≤500;

题目链接:https://www.nowcoder.com/acm/contest/submit/f8363c912a4c48a28b80f47e7102b6b8?ACMContestId=2&tagId=4

思路:二分答案mid,然后检验是否存在两个相同的mid*mid的正方形

检验方法:

首先对于每个位置,求出它开始长度为mid的横行的hash值

然后对于hash值再求一次竖列的hash值

将第二次求出的hash值排序,如果存在两个相同的hash值则可行

下面给出AC代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 inline ll read()
  5 {
  6     ll x=0,f=1;
  7     char ch=getchar();
  8     while(ch<'0'||ch>'9')
  9     {
 10         if(ch=='-')
 11             f=-1;
 12         ch=getchar();
 13     }
 14     while(ch>='0'&&ch<='9')
 15     {
 16         x=x*10+ch-'0';
 17         ch=getchar();
 18     }
 19     return x*f;
 20 }
 21 inline void write(ll x)
 22 {
 23     if(x<0)
 24     {
 25         putchar('-');
 26         x=-x;
 27     }
 28     if(x>9)
 29         write(x/10);
 30     putchar(x%10+'0');
 31 }
 32 char dp[521][521];
 33 ll n,m;
 34 ll p1[520],p2[520];
 35 ll p[555][555];
 36 ll h[250010];
 37 inline bool checked(ll x)
 38 {
 39     //
 40     for(ll i=1;i<=n;i++)
 41     {
 42         ll ans=0;
 43         for(ll j=1;j<x;j++)
 44         {
 45             ans=ans*(ll)('a')+dp[i][j];
 46             p[i][j]=0;
 47         }
 48         for(ll j=x;j<=m;j++)
 49         {
 50             ans=ans*(ll)('a')-p1[x]*dp[i][j-x]+dp[i][j];
 51             p[i][j]=ans;
 52         }
 53     }
 54     //
 55     ll GG=0;
 56     for(ll i=x;i<=m;i++)
 57     {
 58         ll PP=0;
 59         for(ll j=1;j<x;j++)
 60         {
 61             PP=PP*(ll)('a'+(ll)(('A'+1)/2+1))+p[j][i];
 62         }
 63         for(ll j=x;j<=n;j++)
 64         {
 65             PP=PP*(ll)('a'+(ll)(('A'+1)/2+1))-p2[x]*p[j-x][i]+p[j][i];
 66             h[GG]=PP;
 67             GG++;
 68         }
 69     }
 70     sort(h,h+GG);
 71     for(ll i=1;i<GG;i++)
 72     {
 73         if(h[i-1]==h[i])
 74             return true;
 75     }
 76     return false;
 77 }
 78 int main()
 79 {
 80     n=read();
 81     m=read();
 82     memset(p,0,sizeof(p));
 83     for(ll i=1;i<=n;i++)
 84     {
 85         scanf("%s",dp[i]+1);
 86         for(ll j=1;j<=m;j++)
 87         {
 88             dp[i][j]=dp[i][j]-('a'-1);
 89         }
 90     }
 91     ll l=1;
 92     ll r=min(n,m);
 93     memset(p1,0,sizeof(p1));
 94     memset(p2,0,sizeof(p2));
 95     p1[0]=1;
 96     p2[0]=1;
 97     for(ll i=1;i<=r;i++)
 98     {
 99         p1[i]=p1[i-1]*(ll)('a');
100         p2[i]=p2[i-1]*(ll)('a'+(ll)(('A'+1)/2+1));
101     }
102     ll mid;
103     ll k;
104     while(l<=r)
105     {
106         mid=(l+r)/2;
107         if(checked(mid))
108         {
109             l=(k=mid)+1;
110         }
111         else
112             r=mid-1;
113     }
114     write(k);
115     return 0;
116 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Unity Shader

Shader初学笔记:vertex/fragment渲染过程

#pragma vertex vert //对应下面的vert函数,得到转换坐标系后的顶点信息

6124
来自专栏钱塘大数据

R语言的常用函数速查

一、基本 1.数据管理 vector:向量 numeric:数值型向量 logical:逻辑型向量character;字符型向量 list:列表 data....

3089
来自专栏赵俊的Java专栏

Python Numpy 快速入门

1413
来自专栏数值分析与有限元编程

一维变带宽存储刚度矩阵

我们知道,集成之后的整体刚度矩阵是一个对称的稀疏带状矩阵,如图1所示。这样的矩阵包含大量的0元素,占用大量的存储空间。为了节约存储空间,可采取一些方法对刚度矩阵...

4016
来自专栏程序生活

Leetcode-Easy 832. Flipping an Image

862
来自专栏小樱的经验随笔

MATLAB命令大全+注释小结

一、常用对象操作:除了一般windows窗口的常用功能键外。 1、!dir 可以查看当前工作目录的文件。   !dir& 可以在dos状态下查看。 2、who ...

3344
来自专栏偏前端工程师的驿站

代数几何:点,线,抛物线,圆,球,弧度和角度

一, 笛卡尔坐标系                         ? 笛卡尔坐标系是数学中的坐标系,而计算机中则采用屏幕坐标系统. ? 而三维坐标系则没有一个...

2438
来自专栏机器学习算法工程师

经典算法题之Maximal Square

作者:叶 虎 编辑:邓高锦 Maximal Square是道非常有意思的算法题。它是一个典型的动态规划问题,同时也是2017京东面试题,2016华为机考题...

4099
来自专栏算法channel

机器学习储备(10):numpy之RandomState() 和 axis

1 RandomState RandomState是一个伪随机数发生器,这是一个numpy的类,其中包括的方法有:rand,randint,uniform 等。...

3426
来自专栏Python小屋

详解Python科学计算扩展库numpy中的矩阵运算(1)

首先解答上一篇文章中使用with关键字让你的Python代码更加Pythonic最后的习题,该题答案是False,原因在于内置函数sorted()的参数reve...

2864

扫码关注云+社区