ural 1960. Palindromes and Super Abilities (回文自动机,统计本质不同的回文串个数)

http://acm.timus.ru/problem.aspx?space=1&num=1960

题意:

给一个字符串S,依次输出字符串S的所有前缀中,本质不同的回文串个数。

思路:

考虑构建PAM是一个增量算法…所以一边构建一边输出答案就好了。。。

某一时刻本质不同的回文串个数就是sz-1 (标号是从0..sz,一共sz+1个,减去2个根,所以是sz-1)

 

 

uva 10870 – Recurrences (矩阵加速线性递推式)

uva10870题目链接

题意:

f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d

给出f[1]..f[d],a[1]..a[d],问 f[n]%m是多少。

思路:

构造矩阵,加速递推式。

趁着这道题说一下一般的构造法。

转移矩阵M(d*d)的构造方法是,最后一行倒序写a[1]..a[d], 除去第一列和最后一行外,用1填充对角线,其余的为0.

初始矩阵M1(d*1)的构造方法是从上到下,f[1]..f[d]即可。

需要注意的是

最后答案是 (M^(n-d))*M1.mat[d-1][0] (由于经常出现的是d=2的递推式,因此注意不要把此式子的d,写成不够一般化的错误的2

 

ural 1126. Magnetic Storms (单调队列模板题)

ural 1126
题意:n个数,求从第k个元素开始,求每k个元素的最大值(一共求n-k+1次)
思路:单调队列。
单调队列学习链接
其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333

说下我的理解:

单调队列的尾端(就是后进入元素的那一端)其实和单调栈类似。

首端加了个元素期限的概念,不断删除“过期”的元素。

所谓过期的元素,对于这道题来说,当我往前移动到第k+1个元素的时候,第1个元素就是过期了的元素,堆答案不会再有贡献。

理论上单调队列中的元素是<元素的期限,元素>的二元组。

而一般元素的”期限”是由下标的位置决定的,而得到下标就可以知道元素。

所以我们实际操作的时候只需要将下标存入单调队列中就行了。

那么查询最大值呢? 队首元素就是最大值。

以及,用到了stl的双端队列deque(double end queue),头文件是#include <deque>

由于每次的答案是队首元素,因此设置哨兵而使得队列不为空就使得问题变得繁琐。

所以这里不同于单调栈的写法,我们不设置哨兵,而是.empty()判断双端队列是否为空。

也正是因为这个原因,没有办法像单调栈一样写成for的样子(因为没有哨兵,初始x=dq.front()的时候可能dp中还没有元素,导致RE),而是写成while的样子。。具体见代码。

 

 

 

 

ural 1517. Freedom of Choice (后缀数组,最长公共子串)

ural1517
题意:给出两个字符串,求最长的公共字串(要求出具体的字符串是什么)

思路:依然是后缀数组,在更新长度 的时候记录起始位置即可,1A。以及,发现多开了一个完全没有必要的数组w[],这次已删。

 

20160730update:模板已更正,lrj的模板的rk[i]为0 的时候会出现re的问题…已特判。

ural 1057. Amount of Degrees (b进制数位dp)

题目链接
题意:设条件A为一个数恰好是k个互不相同的b的整数次幂的和,问某一个区间内满足条件A的数的个数是有多少个。

Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,
18 = 24+21,
20 = 24+22.

思路:数位dp..需要理解清楚恰好有k个b的互不相同的整数次幂的和这句话。

如果恰好是b的整数幂。。可以转化成b进制。。

互不相同。。说明。。所有位置上的数字要么是0,要么是1.

于是题目可以转化成求某区间内,满足一个数的b进制中恰好有k个1,其余都是0的数的个数有多少个。

然后就是数位dp的套路了。。。

注意dp数组的大小。。。应该按照位数最多的2进制考虑。。。一开始是按照10进制考虑结果只开了dp[15][15]….简直蠢哭。