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

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

题意:

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

思路:

考虑SAM的性质。

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

Read more

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

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

题意:

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

思路:

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

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

容易联想到拓扑排序,我们可以[……]

Read more

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

 

题意:

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

思路:

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

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

参照张天扬的论文:

把原串复制一遍到后[……]

Read more

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

题目链接

题意:

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

思路:

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

L=max(xmaxxmin,ymaxymin)
然后考虑如果正方形旋转的话,能圈住所有点的正方形边长是随[……]

Read more

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

hdu1542题目链接

题意:

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

思路:

扫描线+线段树

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

 

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

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

[……]

Read more

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

poj 3274 题目链接

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

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

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

正[……]

Read more

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

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

思路:一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针,逆时针都存了一次,那么如果有一个雪花顺时针和[……]

Read more

poj 1971 Parallelogram Counting

题目链接

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

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

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

因此统计中点的位置即[……]

Read more

poj 1200 Crazy Search (字符串哈希)

题目链接

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

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

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

nc的作用是,可以把字符串看成一个nc进制的数,这样做的好处是[……]

Read more

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

题目链接

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

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

Read more

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

poj 2443题目链接

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

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

Read more

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

题目链接

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

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

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

 [……]

Read more