[sdoi2008]Sandy的卡片

2015年4月10日2,6097

时限 0.5s

Sandy和Sue的热衷于收集干脆面中的卡片。

然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型。

每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。

Sandy的卡片数远远小于要求的N,于是Sue决定在Sandy的生日将自己的卡片送给Sandy,在Sue的帮助下,Sandy终于集够了N张卡片,但是,Sandy并不清楚他可以兑换到哪个等级的人物模型,现在,请你帮助Sandy和Sue,看看他们最高能够得到哪个等级的人物模型。

输入:

第一行为一个数N,表示可以兑换人物模型最少需要的卡片数,即Sandy现在有的卡片数

第i+1行到第i+N行每行第一个数为第i张卡片序列的长度Mi,之后j+1到j+1+Mi个数,用空格分隔,分别表示序列中的第j个数

输出:

一个数k,表示可以获得的最高等级。

输入样例:

2

2 1 2

3 4 5 9

输出样例:

2

数据范围:

30%的数据保证n<=50

100%的数据保证n<=1000

题解

出题人:

注意到是公共最长子串,所以以第一个串为基本串,枚举答案串的开头和结尾,然后再在每个剩余的串中寻找,如果每个串中都包含,显然是个可行解.

这样做的时间复杂度过高,只能过掉30%的数据.

将这个算法优化,仅仅枚举答案串的开头,用kmp去寻找每个串最多能匹配基本串的长度,取最小值,即可行解.这样算法复杂度为O(NM^2),可以得到满分.

使用后缀数组,可以将算法复杂度进一步优化,将所有串连接,二分答案按照m对后缀分组,判断是否有一组有n个后缀其首字母属于不同的串

sa

 

  • whx2015年4月26日 下午5:38 回复

    bzoj上似乎并没有这道题,黄学长是怎么找到这道题的TAT

    #1  
    • hzwer2015年4月26日 下午6:50 回复
      admin

      我从不知道什么地方的模拟赛拿到的

      #11
  • whx2015年4月26日 下午5:43 回复

    “两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。”这是什么意思TAT

    #2  
    • hzwer2015年4月26日 下午6:50 回复
      admin

      就是差分完一样

      #21
  • lizeren2016年2月13日 下午8:28 回复

    黄学长,您的kmp是wrong answer,从codevs上测得。后缀数组是re,改大数组的范围把所有100005改成1000005才能AC

    #3  
  • Steven妹子2016年10月24日 上午8:13 回复

    这道题保证每个串都是递增的吗?差分以后有负的 怎么办

    #4  
    • rapiz2017年3月11日 下午4:27 回复

      不怎么办。不需要特判负数。

      #41