poj 3415 Common Substrings (后缀自动机+parent树上的lazy标记)

http://poj.org/problem?id=3415

题意:

给出两个字符串,问公共长度大于等于k的子串个数(只要两个串的位置不同就认为是不同)

思路:

考虑SAM的性质。

SAM上的一个节点所能接受的本质不同的子串个数是st[v].len – st[st[v].link].len

而这些子串,都出现了right[v]次,因为不同子串的个数就是(st[v].len-st[st[v].link].len)*right[v]

现在有了限制条件,要求长度大于等于k.

没有限制的话,SAM上的一个节点所能接受的字符串的长度范围是在[st[st[v].link].len+1,st[v].len]

那么现在范围其实就变成了[MX,st[v].len],其中MX = max{st[st[v].link].len+1,k}

对于A串构建SAM,然后B串在SAM上运行

考虑对于SAM的某个状态,B串此时的最大匹配长度为len,那么len>=MX时,满足条件的字符串的范围就变成了[MX,len] 

len<MX时无贡献。

所以该状态(v)对答案的就是  (len-MX+1)*right[v]

然而这还不算完,和之前的LCS2一样,如果SAM上的一个节点能匹配字符串B的长度大于等于k,那么该节点的祖先节点(父亲节点,父亲的父亲的节点…)

能匹配的字符串B的长度也都大于等于k…

如果我们一边匹配一边沿着parent树自底向上传递的话…复杂度n^2,一首凉凉送给自己

但是正常人会这样?.jpg

我们先打个标记,最后沿parent树自底向上把标记传递上去就行了。。

需要注意的是,此题的字符集是大小写字母都会包含…RE了2发orz

 

poj 3249 Test for Job (拓扑排序+dp)

http://poj.org/problem?id=3249

题意:

给一个DAG,现要从一条入度为0的点到一个出度为0的点,问最大点权和。

思路:

其实比较容易想到搜…不过复杂度会炸?

由于到一个点的最大点权和,需要更新完所有到达它的路线之后才能确定。

容易联想到拓扑排序,我们可以在拓扑排序的同时做dp

dp[v] = max(dp[v],dp[u]+a[v]),初始化对于入度为0的点,dp[i] = val[i].

其实拓扑+dp是一种比较一般化的套路…?

因为拓扑保证了更新顺序

 

poj 1509 Glass Beads (后缀自动机求最小循环表示)

 

题意:

给定一个循环字符串,问字典序最小的串的开始位置。

思路:

之前用poj 1509 解题报告-字符串的最小表示法   A过

字符串的最小表示法的复杂度是O(n),代码也不是很难写,不过由于最近在学SAM,所以用SAM写了一下。

参照张天扬的论文:

把原串复制一遍到后面,然后构建后缀自动机。

从初始状态开始,每次走字典序最小的转移,走|S|之后得到的就是最小循环表示。

如果求的是最小后缀,就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后,再添加一遍原串。

 

 

poj 3301 Texas Trip (三分,模板题)

题目链接

题意:

给定二维平面的n个点,要求一个面积最小的正方形,使其能覆盖所有的点。

思路:

先考虑如果水平竖直地放置正方形(边和坐标轴平行)圈住所有点的最小正方形的边长是:

L=max(xmaxxmin,ymaxymin)
然后考虑如果正方形旋转的话,能圈住所有点的正方形边长是随着角度先减后增的,有凸性,可以三分。。。
但是枚举角度计算正方形的话比较麻烦,可以选择旋转平面上的点,使得正方形仍然是水平竖直放置的,因为这样计算正方形的边长比较方便。
如果把点表示成极坐标形式:

x=r×cosθ,y=r×sinθ,θ

那么顺时针旋转 α 角度后:

x=r×cos(θα),y=r×sin(θα)

化简一下可得:

x=r×cosθ×cosα+r×sinθ×sinα=x×cosα+y×sinα
y=r×sinθ×cosαr×cosθ×sinα=y×cosαx×sinα
然后就是三分角度了。。。
三分的板子:

 


 

hdu 1542 Atlantis (线段树+扫描线求矩形面积并,模板题)

hdu1542题目链接

题意:

求n(100)个矩形的面积并。

思路:

扫描线+线段树

题目是2000年中欧区域赛的题目,虽然年代久远,但是有好几个点还是很值得学习的。

 

首先是离散化的适用范围:

之前比较常用的是将比较大的整数值离散化,常常是因为数值太大无法作为下标。

那么其实,浮点数有的时候也需要进行离散化,比如作为数组的下标,比如用来枚举。

做法上是和将较大的整数值离散化没有区别,因为遇到的题目不多,所以特意记录一下。

 

第二点是扫描线的思想:

其实扫描线的思想很早就接触过,noip2011的时候,tyvj上有一道类似的题目,不过是一唯的,当时印象深刻的是@Ocean 兄的那个比喻:

一段公路上右很多区间要收不同的费用,区间的开始给一个标记,表示该段区间对答案有贡献,区间的结束拿走该标记,表示该段区间对答案的贡献结束。

这就是扫描线的思想。

 

第三个是处理线段覆盖问题的一般做法:

通常线段树的节点处理的都是点,处理线段的时候就会比较麻烦。

  另外很重要的一点就是, 线段树都是维护一个点集, 但是对于边的问题就会变得很麻烦,  我们可以按照区间左端点建立线段树, 那么一个点表示的就不是点了, 而是起点在这个点的一个线段。  这样的话, 右区间就要相应的-1, 例如更新区间[1, 4], 就相当于更新标号为[1, 3]的线段。

这也是处理线段覆盖问题的通用方法。

对于上面引用中提到的例子中“更新[1,4],就相当于更新标号为[1,3]的线段”,是因为标号为1的节点代表区间[1,2],标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]

 

接下来具体讨论这道题目的做法:

将矩形按平行x轴方形构建扫描线(只是思想,不用实际构造),

每个矩形2条平行x轴的边分类{上边,下边}2类,如果我们从下往上“扫描”线,那么[下边]就表示了对答案贡献的开始,[下边]就表示了对答案贡献的结束。

  • 扫描线扫描的过程(建议配合代码模拟)

    以下图转载自@kk303的博客

初始状态

初始状态

这里写图片描述

扫到最下边的线, 点13更新为1

这里写图片描述

扫到第二根线, 此时S=lcnt!=0h线, 得到绿色的面积, 加到答案中去, 随后更新计数

这里写图片描述

同上, 将黄色的面积加到答案中去

这里写图片描述

同上, 将灰色的面积加到答案中去

这里写图片描述

同上, 将紫色的面积加到答案中去

这里写图片描述

 

 

 

参考资料:

HDU 1542 Atlantis(线段树:扫描线)

HDU 1542 Atlantis(线段树求矩形面积并)

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)

 

 

 

poj 2417 Discrete Logging (BSGS算法)

题目链接

题意:

Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that
BL == N (mod P)

思路:bsgs算法

详情见BSGS算法笔记

然后被map的count坑了一下? 我想判断map中某个key是否存在,用count会TLE,find也会TLE,[]可以通过….不太懂,复杂度不都是log吗,差常数?还是有人会退化?

不过似乎[]比较安全就对了。

 

poj 3274 Gold Balanced Lineup (抽屉原理?错题?)

poj 3274 题目链接

题意:给出n个数和k,每个数不超过k位二进制。现在问最长的一段区间,满足该区间中所有数相加,k个位置上的数相等。

思路:k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。

于是抽屉原理搞了一发。。一直wa..

正解是数字hash。。。

不过我拍了一下。。。如果不是我理解错了题意的话。。。我是把一份ac代码 hack掉了。。。。。

用来对拍的ac代码:

 

 
 

我的代码:

 

 
数据生成器:

 

 
出错的输入:

 

 
我的输出:

 

 
ac代码的输出:

 

 

 

 
 

poj 3349 Snowflake Snow Snowflakes (利用hash分组)

题意:有n个雪花,每个雪花有6瓣,给出每一瓣的长度,问是否有两个雪花相同。(雪花相同的条件是:存在某个顺序使得两个雪花的每一瓣长度对应相等)

思路:一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针,逆时针都存了一次,那么如果有一个雪花顺时针和逆时针相同,就会出现错误的结果(虽然这个我应该判掉了。。。但是还是WA orz)

归根结底我是没有搞定当hash相同的时候,如何判定这两个不是一组orz。

看了很多题解。。。(为什么大家这道题的代码都写得这么丑啊。。。。?

思路有:hash或者最小表示法,或者最小表示法+hash

思路是,把六瓣的长度求和,作为hash的key值。。。

然后。。。只在key相同的里面找一样的。。。

其实是根据这个和分了组。。。

因为和相同的,未必雪花一样,但是雪花的一样的,和一定相同,极大的缩小了范围。

也让我对hash有了新的理解:

hash未必可以唯一确定某个值,但是可以帮助缩小范围。

 

 

poj 1971 Parallelogram Counting

题目链接

题意:给出n(n<=1E3)个不同的点,问最多组成多少个平行四边形。

思路:这道题的关键是,对于平行四边形的判断条件,要利用平行四边形对角线的交点平分两条对角线的性质。

也就是说,如果两条线段的对角线重合,那么一定可以组成一个平行四边形。

因此统计中点的位置即可,复杂度n*n*lg(n*n)

 

 

poj 1200 Crazy Search (字符串哈希)

题目链接

题意:一个字符串,其仅由nc种字符组成,问其所有长度为n的字串里,共用多少种不同的。

思路:一开始木有懂nc种字符有什么用…

然后写了hash,发现会TLE。。。因为用到了map,被卡了个log..

nc的作用是,可以把字符串看成一个nc进制的数,这样做的好处是,得到的hash值可以尽可能的小而且保证了不同的字符串对应了不同的hash值。

然后就可以不用map而是一个数组,就变成了O(1)赋值和判断了。。。

(然而没有数据范围其实还是有点耍流氓的嫌疑。。

 

poj 2503 Babelfish (字符串hash +sscanf读入技巧)

题目链接

题意:给定一个两种语言的对照关系表…给出后一种语言中的单词,问对应的前一种语言的单词是什么。。。

思路:hash一下然后map存一下即可。。。。读入方式由于单词表和查询是根据空行分开的。。那么读入不能用scanf(因为会跳过空行),要用gets。。。然后再sscanf一下。。。

 

【叉姐的魔法训练第一课_初级魔法练习】poj 3244 Difference between Triplets (数学)

题目链接

题意:

For every pair of triplets, Ta = (Ia, Ja, Ka) and Tb = (Ib, Jb, Kb), we define the difference value between Ta andTb as follows:

D(Ta, Tb) = max {IaIb, JaJb, KaKb} − min {IaIb, JaJb, KaKb}

Now you are given N triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

思路:转化要求的式子,如果把IaIb, JaJb, KaKb 看成数轴上的点,所求的式子就变成了求三个点构成的线段的距离。

设X=IaIb,Y=JaJb,Z=KaKb,那么该距离D = (|X-Y| + |Y-Z| + |Z-X|  )/2(该式子是此题最关键的一部,可以通过画图直观得到)  

D=|(ia-ja)-(ib-jb)| + |(ja-ka)-(jb-kb)| + | (ka-za)+(kb-zb) |

设a = ia-ja,b =ja-ka,c = ka-ia,然后分别排序类似于bzoj1604_拆点求曼哈顿距离

考虑第i个a,对于其他的n-1个a,有i-1个比它小,n-i个比它大,因此对答案的贡献为(i-1)个a[i]和 (n-i)个-a[i]

b,c同理。

 

 

 

【叉姐的魔法训练第一课_初级魔法练习】poj 2443 Set Operation ( bitset加速)

poj 2443题目链接

题意:给出n个可重集…以及集合中的元素。。。现在若干查询,每个查询给出一对数x,y,询问是否存在某个集合,同时拥有x,y两个元素(x,y可以相同)

思路:由于x,y最大时10000,容易想到对每一个元素开一个集合,记录这个元素出现的集合的标号,然后用 set_intersection 来做…

就是询问的时候交一下两个集合,看是否为空,结果Tle了。。。

正解其实也是这个思路,不过用到了bitset加速一下。因为我求集合相交的时候,并不需要知道交了以后的结果,只需要知道是否为空,那么我们不妨用bitset

对每个元素开一个bitset,每个bitset上,第i位为1表示,该元素在第i个集中中出现了。

求相交的时候,只需要两个bitset 位与一下,然后看结果中是否有1出现就好了。

 

 

poj 3233 Matrix Power Series (矩阵快速幂+分治)

题目链接

题意:

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

思路: 对k进行二分。

比如,当k=6时,有:
A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
应用这个式子后,规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3,即可得到原问题的答案。

以及错误的递归方式:

screenshot-from-2016-10-19-16-12-57

无形中增加了多少次。。。。。。怎么像小学生呢。。。

screenshot-from-2016-10-19-16-12-57

正确的写法。。。

screenshot-from-2016-10-19-16-14-08

 

poj 3070 Fibonacci (矩阵加速线性递推式)

题目链接

题意:求f[n] % 10000,f为斐波那契数。

思路:按照题目给出的公式,或者按照加速线性递推式的方法都可以。。。

因为把模数的1E4手滑写成1E4+7结果调了半天也是没谁了呵呵呵呵。