BZOJ2532 | CERC2010 Casting Spells

首先跑马拉车。

然后对于每个位置 i 我们求出他的回文对称半径 r_i 。比如说图上假设 i 是回文子串的中心(如果是偶数长度那就是中心的右侧),然后红色位置是子串的右末端,那么 r_i 就是:

然后有了 r_i 之后我们考虑合法的串长什么样子:

于是我们的任务就是找到满足以下条件的 j

  •  j+r_j \geqslant i
  •  j \geqslant i-\frac{r_i}{2}

然后就可以了。那么这里有一个 O(n \log n) 的搞法:从左到右枚举 i ,并同时维护两个集合:一个是当前所有满足条件 [1] 的 j 的位置集合,这个集合以 r_j+j 排序,并记录每个 r_j+j 对应的 j

另一个集合维护所有当前的合法位置 j ,并按照 j 排序。

每次扫到一个 i 只需先清空位置集合所有 r_j+j < ir_j+j 和合法集合对应的 j

然后求合法集合里 i - \frac{r_i}{2} 的后继即可。

 

JLOI2008 CODES

一天半,唉。。真该AFO了。

首先考虑我们可以DP,设状态 dp[i][j] 表示 第 i 个字符串  还需要匹配长度为 j 的前缀   可以得到的最短答案。

转移:

转移就是枚举一个字符串 i_0 来与之匹配。记忆化搜索非常好写。注意讨论两种情况:

  1. i_0比当前前缀长
  2. i_0比当前前缀短

用 dp[i0][?] + 匹配长度 去更新dp[i][j]。(?是因为我懒得讨论了……代码里有)

数据范围很小,暴力匹配即可。

注意事项:

第一个细节就是字符串可以重复利用;

第二个细节是让dp[i][0]=0 其余为 +\infty

第三个细节就是最后统计答案和DP过程中别忘记比较字典序。

字典序:

 answ[i][j] 保存当前 dp[i][j] 对应的具体方案,

更新 dp[i][j] 顺便更新 answ[i][j] 即可。

每次遇到 dp[i0][?]+len  dp[i][j] 相等的情况,判定字典序,然后更新 answ[i][j] 即可。

最后的答案是 dp[i][len[i]]

O(\text{跑得过})

#洛谷 P1026 统计单词个数

垃圾题……照样处理一发区间[i,j]有多少单词然后枚举区间起点i转移就行了。

 

题目描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)。

单词在给出的一个不超过6个单词的字典中。

要求输出最大的个数。

输入输出格式

输入格式:

每组的第一行有二个正整数(p,k)

p表示字串的行数;

k表示分为k个部分。

接下来的p行,每行均有20个字符。

再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)

接下来的s行,每行均有一个单词。

输出格式:

一个整数,分别对应每组测试数据的相应结果。

提供一组卡了我好久的数据,注意区间[i,j]的长度。。。

Testdata.in

10 4
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
1
aaaaa

Testdata.out

193

比分割字串稍难了一点……主要难在倒推k[i][j] ([i,j]有多少单词),写个模拟就行了吧大概……