注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

poj2185  

2016-08-13 11:35:09|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目大意:
       求最小覆盖矩阵。给出行R(1≤R≤10000)和C(1≤C≤75),接下来是R行C列的字符矩阵。如图:
poj2185 - 杨鸿飞 - 杨鸿飞的博客
====================================
        首先,有不少人会求每行的最小覆盖子串的最小公倍数,其实那样是不对的,反例:
        ABCDEFAB
        AAAABAAA
        7就可以了。
====================================
        然而怎么做呢?
        我们会发现列数很小,可以暴力求出每一行所有的覆盖子串,枚举循环长度233。
        求出宽度后,在以整一行来做kmp(把整一行看成一个字符)。求出那个循环节长度,就是高。
        面积相乘。
====================================

#include <cstring>
#include <cstdio>

using namespace std;

const int MLn=10000;
const int MLm=75;

char st[MLn+10][MLm+5],a[MLm+5];

int f[MLm+5],nx[MLn+10];

int main()
{
int n,m; scanf("%d%d",&n,&m);

for (int k=1; k<=n; k++)
{
scanf("%s",st[k]);

memset(a,0,sizeof a);

for (int i=1; i<=m; i++) //枚举循环节长度
{
strncat(a,st[k]+i-1,1);

int sum=0;

for (int j=0; j<m; j++)
if (a[j%i]==st[k][j]) sum++;

//puts(a); printf("%d\n",sum);

if (sum==m) f[i]++;
}
}

int w;

for (w=1; w<=m && f[w]<n; w++);

nx[0]=nx[1]=0;

int k=0;

for (int i=2; i<=n; i++)
{
for ( ; k>0 && strcmp(st[k+1],st[i])!=0; k=nx[k]);

if (!strcmp(st[k+1],st[i])) k++; //字符串比较函数

nx[i]=k;
}

int h=n-nx[n];

//printf("%d %d\n",h,w);

int Area=h*w;

printf("%d",Area);

return 0;
}


        
  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018