A,B,C:都很简单，不说了。

D:一棵树，给出树的结构，以及从树根到某个深度为偶数的节点的路径和，问能否构造一种所有节点点权和最小的树，输出最小点权和。

好久没玩cf了，竟然还能涨分（虽然我用的小号Orz)

三题，D应该是数学+DP…数学实在是忘干净了。。。

前面三题大体还好，都是1A,不过因为没有提前配置环境。。耽误了一些时间。。。

题目链接:http://codeforces.com/contest/1015/problem/B

题意: 给出字符串s和字符串t，问一个将s变为t的策略。 可以做的变换为，交换s中相邻的字符串，该操作最多不能超过4000次，字符串长度最大为50.

题目链接

题意:有n个数，现在要分成2个集合，使得2个集合中，仅出现1次的数的个数相同，问是否有解，以及具体的分法。

思路:

一开始考虑出现多个的数的思路麻烦了，比如对于出现2次的某个数x，与其一个集合中分得一个，使得两个结合中，仅出现1次的数的个数各+1，还不如都放在同一个集合中，使得仅出现1次的数的个数不增加。

emmm 最后一场，果然还是写点什么记录一下吧。

DAY 0

到宾馆已经晚上八点了，惊讶得发现宾馆和15年来参加regional的是同一个，于是戳了下当时和我们一起来的@Always队的三个已经毕业的学长，求了波rp2333

http://codeforces.com/gym/100548

题意：

切换面板：标签 标签 添加新标签  回文自动机、 给2个字符串，问2个字符串中，相等并且都是回文串的对数。

思路：

构建2个PAM.然后奇偶起点分别跑dfs即可。

2160: 拉拉队排练

Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 1938  Solved: 743 [Submit][Status][Discuss]

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨 …

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

题意：

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

思路：

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

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。 输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

http://acm.hdu.edu.cn/showproblem.php?pid=3948

题意：

给一个字符串，问本质不同的回文子串的个数。

思路：

考虑回文自动机。

我们知道，对于PAM上的一个节点，表示的就是一个本质不同的回文串。

UPDATE: 弃用了这种代码风格,新的写法见下面。

http://uoj.ac/problem/103

题意：

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

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

题目链接：http://codeforces.com/problemset/problem/123/D

题意：

如果字符串y在字符串x中出现n次，那么F(x,y)=n*(n+1)/2

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

题意：

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

思路：

考虑SAM的性质。

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

http://acm.hdu.edu.cn/showproblem.php?pid=4416

题意：

给出一个字符串A和n个字符串B,问A的子串中，不在任何一个B中出现的本质不同的子串有多少。

思路：

还是根据len搞事情

我们知道，如果不加任何条件，SAM中一个节点所表示的本质不同的子串数量是st[i].len - st[st[i].link].len

http://acm.hdu.edu.cn/showproblem.php?pid=3518

题意：

给一个字符串，问字符串中，至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。

思路：

考虑SAM

SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。

http://acm.hdu.edu.cn/showproblem.php?pid=6059

题意：

含 N 个数字的 A 数组，求有多少个三元组 (i,j,k) 满足 i<j<k 且a[i]^a[j] < a[j]^a[k]

思路:

考虑a[i]和a[k]二进制不同位中的最高位，此时满足题意的a[j]是该位与a[i]相同，其他位任意的所有a[j]的个数。

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5558

题意：

说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i - 1]开始的所有后缀中最大匹配的公共前缀长度

思路：

这个动态的过程很容易想到SAM啊。。

题意：

求n个串的最长公共子串，n<=10

思路：

不会啊orz

先放一波参考资料&题解好了。

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

candy SPOJ 1812 LCS2 [后缀自动机 DP]

首先参考下2个串的LCS的做法spoj-lcs

http://acm.hdu.edu.cn/showproblem.php?pid=4819

题意：

给你一个n*n的矩阵， 每个点是一个数字， Q个操作，每次选择一个子矩阵， 把中心元素替换成子矩阵中最大值和最小值之和的二分之一。

思路:

显然是一个二维线段树…..

http://acm.hdu.edu.cn/showproblem.php?pid=4436

题意：

给出n个仅由数字组成的字符串，问n个字符串的所有不同子串的和。

思路：

SAM水题

从初始状态开始，走过所有路径，就是该SAM表示的所有的（不重复）子串。