Advertisement

NKOJ 2244 奶牛阵列(KMP+哈希)

阅读量:

2244奶牛阵列

问题描述

复制代码
    每天早晨约翰的奶牛都会在挤奶的时候排成阵列,即站成R(1<=R<=10000)行C(1<=C<=75)列的矩阵。我们知道,约翰是奶牛专家,他打算写一本关于喂养奶牛的书,他发现,当奶牛按不同血统标记以后,整个大矩阵就像由很多小矩阵无缝拼接的一样。
    
    请帮助约翰找到面积最小的模型矩阵,使他能拼出整个大矩阵,当然,模型矩阵的尺寸不一定能整除大矩阵,也就是说你可以用若干个模型矩阵,拼出一个包含大矩阵的更大的矩阵。

输入格式

复制代码
    第一行, 两个整数R和C
    接下来是由大写字母构成的R*C的矩阵

输出格式

复制代码
    一个整数,表示最小模型矩阵的面积。

样例输入

复制代码
    2 5
    ABABA
    BABAB

样例输出

复制代码
    4

提示

复制代码
    样例说明:
    模型矩阵如下:
    AB
    BA
    拼出的大矩阵如下:
    ABABAB
    BABABA

本题usaco官方数据很弱,很多错解可以AC,下面提供两种正确思路。

思路一:

首先必须明确小矩阵之间不能发生重叠的情况, 因此我们需要关注

全部评论 (0)

还没有任何评论哟~