Milking Grid poj-2185

    题目大意:给出一个字符矩阵,求最小覆盖矩阵(可以残余).

    注释:$1\le R\le 10^5$,$1\le C \le 75$

      想法:和bzoj1355不同的是,bz那题求的是最小覆盖子串。这题其实异曲同工。Discuss中讲的还是蛮清楚的,就是我们对于每一行单独求出Next数组,然后跑出每一行的所有的可能覆盖子串,然后用桶遍历出一个最小值即可。最后的乘积就是答案。

    最后,附上丑陋的代码... ...

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxr=10002;
const int maxc=80;
char GetRead[maxr][maxc];
int row,col;//行和列
int rnext[maxr][maxc];//rnext[i]:对应第i行字符串的next函数
int cnext[maxr];//求纵向的next,每次比较的是整行
int rlen[maxr];//rlen[i]:第i行字符串的最小循环子串的长度
int cnt[maxc];//cnt[i]:统计各宽度出现的次数
int ans_for_col,ans_for_row;//最小覆盖矩阵的宽度和高度
void rgetNext(int r,char*str)//
{
int k=0;
rnext[r][1]=0;
for(int i=1;i<col;i++)
{
while(k&&str[k]!=str[i])
k=rnext[r][k];
if(str[k]==str[i])
k++;
rnext[r][i+1]=k;
}
rlen[r]=col-rnext[r][col];
int i;
for(i=rlen[r];i<=col;i+=rlen[r])
{
cnt[i]++;
}
i-=rlen[r];
for(int j=i+1;j<=col;j++)
{
int x=0,y=j;
while(str[x]==str[y])
{
x++;y++;
}
if(y==col)
cnt[j]++;
}
} void GetNext()
{
int k=0;
cnext[1]=0;
for(int i=1;i<row;i++)
{
while(k&& strcmp(GetRead[k],GetRead[i])!=0)
k=cnext[k];
if(strcmp(GetRead[k],GetRead[i])==0)
k++;
cnext[i+1]=k;
}
ans_for_row=row-cnext[row];
} int main()
{
scanf("%d%d",&row,&col);
for(int i=0;i<row;i++)
{
scanf("%s",GetRead[i]);
}
memset(cnt,0,sizeof(cnt));
for(int i=0;i<row;i++)
{
rgetNext(i,GetRead[i]);
}
GetNext();
for(int i=1;i<=col;i++)
{
if(cnt[i]==row)
{
ans_for_col=i;
break;
}
}
printf("%d\n",ans_for_col*ans_for_row);
return 0;
}

    小结:挺好的一道题,有意义。网上大部分的题解全都是假的,很多并不极限的数据就能卡死。

最新文章

  1. 曝光最新WIN10系统32位,64位系统ghost版
  2. log4j.properties配置
  3. [原创]快速指定SQLDeveloper所使用JDK的方法
  4. wmi详解,RPC和防火墙
  5. unity编辑器的搜索框好特么坑啊,居然不支持*号通配符
  6. jquery实现抽奖
  7. Fragment生命周期与Fragment执行hide、show后的生命周期探讨
  8. 细数本地连阿里云上mysql8遇到的坑
  9. 计算机名称改名之后,tfs连接问题
  10. Mysql占用CPU过高如何优化?(转)
  11. python部分面试- 测试维度
  12. 了解cron以及使用cron定时备份MySQL
  13. 第五次spring会议
  14. left join on 和where中条件的放置位置
  15. $.extend 的相关用法
  16. 使用JQuery获取被选中的checkbox的value值 以及全选、反选
  17. web项目整合Shiro框架
  18. box-sizing与calc()与flex
  19. beego——XSRF过滤
  20. Vim中 ctags 跳转直接跳到第一个匹配行的问题

热门文章

  1. 基于busybox的Linux小系统制作 (initrd)
  2. ArcGIS For Flex报错二
  3. 真实场景的虚拟视点合成(View Synthsis)详解
  4. php 数组排序得方法
  5. Struts2【配置】知识要点
  6. Spring Data(一)概念和仓库的定义
  7. FFT/NTT 总结
  8. c# ffmpeg视频转换【转载】
  9. JavaScript实现强制重定向至HTTPS页面
  10. Scala编程快速入门系列(一)