UOJ #103. 【APIO2014】Palindromes (回文自动机模板题)

http://uoj.ac/problem/103

题意:

给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 s,求所有回文子串中的最大存在值。

思路:

回文自动机,也叫回文树,但其实并不是树2[……]

Read more

SPOJ SUBLEX Lexicographical Substring Search ( 后缀自动机)

http://www.spoj.com/problems/SUBLEX/en/

题意:

给一个字符串,每次询问字典序第k大的不重复子串。

思路:

先做个拓扑dp,求出SAM上,一个状态到种态的路径数。

拓扑dp其实就是按照拓扑序的dp啦…

然后从SAM的初始态开始,每次字典序从小到大[……]

Read more

SPOJ LCS Longest Common Substring (后缀自动机模板题)

题意:

给出2个字符串(2.5E5),问最长公共子串的长度。

思路:

拿一个串建SAM

由于SAM上的任何一个状态,都对应一个或者若干个子串,然后拿另一个串在SAM上面跑就行了

20171110UPdate:我好像说得太简略了。。

参考clj的冬令营讲稿:

  • 给两个长度小于1[……]

Read more

SPOJ CIRUT – CIRU2 (多个圆交,求交任意次的面积,模板题)

题目链接

题意&思路:

给出n个圆

求恰好k个圆相交的面积,k属于1..n

 

先放个别人的代码。。。

我真是体会到了。。。软件工程这门课的重要性。。。

这代码真是烂得印象深刻。。。几何题全是面向过程?

circle和point 类写在一起。。。感觉所有糟糕的写法这[……]

Read more

spoj DQUERY – D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接
题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。

思路:离线处理+线段树的做法不多说了:

之后补一个主席树的做法

先来补一个莫队的做法。

因为a[i]<=1E6,可以很[……]

Read more

hit oj 2687 Candy (线段树动态维护最大连续子段)

题目链接

题意:给出n个数,m个修改,每次修改后询问整个区间的最大连续子段。

思路:考虑一段区间,分成左右两个子区间,这段区间的最大子段有三种情况:只在左区间中,只在右区间中,既在左区间中又在右区间中。前两种很好维护,对于后一种,我们新增加线段树的两个域,mxl,mxr,分别表示一个区间[……]

Read more

light oj 1080 Binary Simulation (线段树lazy标记,区间更新,单点查询)

题目链接

题意:给出一个长度为n的数列,每个位置是0或者1,给出q个操作,操作有两种类型,分别是将一段区间中反转,和询问当前某位置是0还是1

思路:lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数,初始为0.然后查询的时候,根据被翻转次数的奇偶性确定答案。[……]

Read more

light oj 1045 Digits of Factorial (k进制数的位数)

题目链接
题意:求n!在k进制表示下有多少位。
思路:答案为[ log(1)+log(2)+…+log(N) ]+1  其中log的底数都是K

由于有多组数据,预处理一个log的前缀和。

 

&nbs[……]

Read more

spoj SUBST1 – New Distinct Substrings(后缀数组)

题目连接

题意:求所有不同的子串个数。

思路:后缀数组。和上一道题一样,就是数据范围变成了 5E4…1A

 

 

 

 

spoj DISUBSTR – Distinct Substrings (统计字串个数,后缀数组)

题目链接

题意:给出一个字符串,问所有不同的字串的个数。

思路:直接求比较困难。我们考虑,假如组成字符串的所有字符都不相同,那么就没有相同的字串,假设字符串的长度为n,那么长度为1的子串有n个,为2的有n-1个。。。为n的有1个,一共就是n*(n+1)/2个。。但是实际上会有重复的。。。[……]

Read more

light oj 1422 – Halloween Costumes (区间dp)

light oj 1422 题目链接

题意:

按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来,但是一旦脱下来,这件衣服就报废了。问最少需要几件衣服。

 

思路:没有思路。我连这题是dp都看不出来。。知道是dp也一点思路都没。。虽然这[……]

Read more