hdu 3948 | 2011 Multi-University Training Contest 11 The Number of Palindromes (回文自动机模板题)

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

题意:

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

思路:

考虑回文自动机。

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

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

那么sz-2就是本质不同的回文子串个数了orz(减掉2是因为PAM有2个根,这2个根不表示回文串)

 

对于新的代码风格,节点数标号是从0到siz,其中标号为0和标号为1的是2个根。

因此答案是siz-1

新的代码风格:

 

 

hdu 4416 Good Article Good sentence (后缀自动机)

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

题意:

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

思路:

还是根据len搞事情

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

现在加了限制条件。

那么该状态中,有一些长度的字符串就会不满足条件。

我们考虑对母串A构建SAM

那么只需要维护B的所有串,对于某个状态能匹配的最大长度,设为maxlen,那么 长度为[maxlen+1,st[i].len]的字符串可以贡献答案。

如果maxlen为0,则该状态所表示的所有本质不同的子串都可以贡献答案。

维护最大匹配长度 可以参考   spoj-lcs2 解题报告 

有所不同的是不需要在每一个B中都匹配,只需要至少一个匹配就行了,因此是取所有串的最大匹配长度即可。

 

hdu 3518 Boring counting (后缀自动机)

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

题意:

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

思路:

考虑SAM

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

考虑其right集合,如果right集合中最大的r设为rightmost,最小的r设为leftmost.

那么如果rightmost-leftmost+1 > st[i].len ,说明什么呢?

说明该状态所表示的最长的字符串能够至少放下两个而不重叠。

即从[leftmost-st[i].len+1,leftmost]一段 和 从[rightmost-st[i].len+1,rightmost]一段。

如果最长的能放下,那么其他的也一定能放下。因此对答案贡献为st[i].len – st[st[i].link].len

如果rightmost-leftmost+1<=st[i].len,也就是rightmost-leftmost<st[i].len

这个时候长的字符串因为重叠了不能出现2次,但是短的字符串仍然可以贡献答案。

考虑如下图:

此时对答案的贡献为rightmost-leftmost+1 – (st[st[i].link].len+1),化简得到rightmost-leftmost-st[st[i].link].len

综合2种情况,SAM中每个节点对答案的贡献是 min(rightmost-leftmost,st[i].len)-st[st[i].link].len

需要注意的是只有在st[i].link存在并且rightmost-leftmost>st[st[i].link].len 时 才更新答案

leftmost可以在构建的时候直接求出,rightmost用拓扑序更新下即可。

 

hdu 6059 | 2017 Multi-University Training Contest – Team 3 Kanade’s trio (trie)

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]的个数。

我们可以从1..n,依次插入a[k]到trie中,插入时,顺便用num[i][j]统计二进制第i位为j的数的个数。

当要插入a[k]时,a[1]..a[k-1]已经插入到了trie中。

trie上统计当某个节点,该位为0的数的个数和该为为1的数的个数。

需要注意这样统计出的数并不能保证i<j (但是可以保证i<k。。。)

因为我们的trie需要额外维护一部分ext.具体解释见代码注释。

 

 

hdu 5558 | 2015ACM/ICPC亚洲区合肥站 G Alice’s Classified Message (后缀自动机)

题目链接:

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

题意:

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

思路:

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

所以就一边匹配。。一边构建SAM就好了。。

需要注意的是,如果有多个最长,需要输出最左边的位置。

因此多维护一个leftmost,表示某个字符串第一次出现的结尾的位置。

 

 

 

 

hdu 4819 2013 Asia Regional Changchun G (四叉树|| 二维线段树单点更新 模板题)

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

题意:

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

 

思路:

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

然而菜鸡如我,并没有写过二维线段树啊?

那怎么办呢

一首《凉凉》送给自己

 

 

然而我们还有四叉树2333

2A,写错一个地方。第一次写四叉树,orz

 

然后又写了一个二维线段树的版本,借鉴了kuangbin的写法,改成了自己习惯的代码风格。

果然常数差好多。。。(据说是因为四叉树退化得厉害QAQ

第三个是四叉树的做法,第二个是kuangbin 的 树套树版本的二维线段树

第一个是我改写kuangbin代码之后的代码。

可以看出,四叉树虽然好写好理解一点,但是时间上不太优秀啊….

 

hdu 4436 | 2012 Asia Tianjin Regional Contest str2int (dp+后缀自动机,多串建立)

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

题意:

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

思路:

SAM水题

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

因此只需要从根节点按照拓扑序(这回是根据len从小到大)转移好了。

考虑num[i]表示从SAM中的init状态到i状态能表示的子串的数量。

dp[i]表示从SAM中的init状态到i状态所表示的子串对应的和(也就是到该节点的子串的答案)

那么对于SAM中一个u->v(其中u和v是状态,设转移边为j,j属于0..9)的转移

num[v]+=num[u]

dp[v] = dp[u] * 10 + num[u] * j

初始根节点num[rt]=1,表示唯一的空串。

需要注意,前缀0的数不考虑,所以SAM中 init状态不转移0这条边。

 

hdu 4777 Rabbit Kingdom (树状数组+预处理)

https://vjudge.net/problem/47450/origin

题意:

有一个含有n个数的序列,m个询问。问 [l, r] 区间内与所有数都互质的数有几个?

思路:

想到了预处理每个数最左最右的,最远的互质的数的范围。。

之后对于询问区间[l,r],我们要知道 对于 i>=L && i <= R 并且 a[i].l<=L,a[i].r>=R的i的个数…

没有想到怎么维护,gg

 

转载一段题解:

先算出每个数的有效范围,l[i],r[i]代表与第i个数一直互质到的最左端和最右端。这个处理方法是,预处理出一张因子表。然后对每个输入的数,判断其因子出现的最接近它的位置。从左到右扫一遍求出l[i],从右到左扫一遍求出r[i];我们还需要用一个vector记录下左边界为i时的所有数。

我们思考一个范围内,当一个数的l[i]和r[i]都在范围之外时,这个数会被统计在内。反过来讲就是一个范围在一个数的边界之内,当前的数会被统计到范围之内。

我们先对问题进行离线处理,先根据问题的左边界排序。我们需要维护一个树状数组来统计和增减值。

然后我们按照i从1到n扫一遍,i代表的意义是左边界。

1. 当扫到第i个数时,我们统计左边界为i+1的问题(这样范围一定满足左边界,因为右边界接下来也进行了处理,所以可以直接统计)。

2.  我们还需要更新第i个数。i的意义是左边界,因为之后统计的问题左边界都大于i,都满足。所以我们找到所有左边界为i的数,将其+1处理。然后右边界-1处理。这样如果问题的边界大于右边界的话,这个数就不会统计在内。

3.  最后处理完i后,因为以后问题的左边界都大于i,所以第i个数不会再被统计了,所以我们要除去第i个数的影响,就是把其右边界+1(自身为什么不处理,因为处不处理都一样,不会在涉及到它本身了)

 

转载又一段题解:

先预处理出来每个数的贡献区间,每个数的贡献区间是 [左边最近不互质数的位置,右边最近不互质数的位置] ,现在问题就转化为了求区间 [L, R] 中有几个数的贡献区间能完整覆盖 [L, R] 区间。但是数据范围挺大的,可以考虑用树状数组离线处理来达到优化的目的。先对所有的查询进行排序 (按照L升序排列) ,然后从左到右依次处理。我们用树状数组区间和sum [L, R] 表示区间[L, R]中符合题意的有多少个数。假设现在需要查询 [L, R] 区间,我们可以考虑贡献区间L[i]<L的数,可以在i位置加 1,然后在R[i]位置减1。这样处理的话必须要保证L[i]小于查询区间L的值,以及i要在查询区间内。所以我们每次向后移动的时候,要在树状数组中减去当前位置的数对树状数组的影响,也就是进行操作 i 位置减1,R[i]位置加1. 分析到这里这个题目就变成了一个比较水的利用树状数组进行点更新,区间查询的题目了,也可以用线段树搞的。

 

hdu 6048 | 2017 Multi-University Training Contest – Team 2 D Puzzle (结论题)

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

题意:

 

有 n * m – 1 个数,每次选择第 1,p + 1,p * 2 + 1…..
的顺序选择数,先按左到右,再按从上到下的顺序填入n * m 的格子,空格子可以和相邻的数字交换位置,问最后能否在格子中形成 1~ n * m – 1的数按从左到右,从上到下的顺序。

思路:

傻逼结论题。

根据九宫格问题的结论:将矩阵中的数按先从左到下右再从上到下排成一列,其逆序对如果为偶数则一定有解,否则一定无解

根据九宫格问题的结论:将矩阵中的数按先从左到下右再从上到下排成一列,其逆序对如果为偶数则一定有解,否则一定无解

根据九宫格问题的结论:将矩阵中的数按先从左到下右再从上到下排成一列,其逆序对如果为偶数则一定有解,否则一定无解

然后我们可以观察发现,按照题目中填数的策略

按照填入的顺序,每个数对逆序对的贡献分别是0,p-1,2(p-1)… 0,p-1,2(p-1)…

注意到当总数小于等于p时,所有数对逆序对就没有贡献了。

然后直接算等差数列就好了。

$$ sum = na_{1} + \frac{n(n-1)}{2}*d $$

由于首项一直为0,所以只要算后面那部分就好了。

 

 

hdu 4782 | 2013 Asia Chengdu Regional Contest B (模拟)

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

题意:

将格式混乱的html代码输出成标准格式。

思路:

模拟。

说下细节:

  • 遇到open tag,先打印,后dep++
  • 遇到close tag,先dep–,再打印
  • 遇到空标签,直接在当前深度打印
  • 遇到空白字符时,只有当前面出现了text以及后面也出现了text的时候才打印。也就是说第一个string和最后一个string都是紧邻标签的。

最坑的一点是…虽然题目给了数据组数,但是在</html>所在行的同一行,可能出现下一组的开始<html>

最坑的一点是…虽然题目给了数据组数,但是在</html>所在行的同一行,可能出现下一组的开始<html>

最坑的一点是…虽然题目给了数据组数,但是在</html>所在行的同一行,可能出现下一组的开始<html>

说好的多组数据呢…

 

 

hdu 4622 | 2013 Multi-University Training Contest 3 Reincarnation (后缀自动机)

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

题意:

给一个字符串,给出若干询问,每组询问给一个区间[l,r],问区间中本质不同的字符串的个数。

思路:

观察发现,有10000组查询,字符串的长度最多才2000,所以可以预处理一波。

我们先考虑如何处理整个区间中,本质不同的子串数量。

考虑SAM,由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串,同时后缀自动机是最简的,所以问题也就变成了从初始状态开始不同路径的数量

每个节点 u 表示的子串长度在 [min[u],max[u]]范围内.

又由于max(u.fail) = min(u)-1

因此u表示的子串的长度就是变成了(max[u.fail],max[u] ]  (注意区间,是左闭右开)

由于每个长度的串都出现了一次,因此这个状态子串的个数就是max[u] – max[u.fail]

如果是统计整个串的本质不同的串的个数,那么buildSAM之后统计一下就行了。

现在是询问区间。

问题变成了,从[l,r]到[l,r+1],答案的改变是什么。

在SAM上添加一个字符之后,SAM当前的状态变成了cur,那么实际上,对答案的贡献,就是初始状态到新的状态cur的不同路径数目。

也就是max[cur]-max[cur.fail]

 

 

HDU 5970 | 2016 CCPC HeFei onsite J 最大公约数 (打表找规律)

题意:

有这样一个有关最大公约数的函数:
函数 f(x, y):

给出三个正整数n,m,p,你需要计算:

$$ \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{i*j}{f(i,j))} \right \rfloor $$

 

n <= 666,666,666, m <= 666, p <= 666,666,666。

 

思路:

打表找规律。

但是找规律也要按照基本法

观察到m比较小,对于固定的j,容易看出f(i,j)和f(i+j*k,k)是等价的。

比赛的时候没做出来,因为纠结取整的问题…

解决办法竟然是….通过循环节观察orz

转载一篇靠谱的题解:

一开始,我自己假设先不考虑c。那么就变成了ΣΣi/gcd*j/gcd=Σj/gcd*Σi/gcd,如此一来,由于m比较小,我就可以枚举j,然后对应求出j所有的因子作为gcd,gcd确定之后再根据容斥来统计i/gcd的和。具体统计方法和15年沈阳regional的frog那题类似,用n的因子来进行暴力的容斥。但是很显然这样子很难把c的影响带进来,而且这里的c还要向下取整,更加的麻烦。

于是打表找规律,首先很容易知道f(i,j)=f(i+kj,j)。根据这个,在不考虑向下取整的情况下,对于同一个j,我们就可以列出一个等差数列,其中首项是i*j/f(i,j),公差为j*j/f(i,j)。但是这里要考虑这个向下取整。我们设i为模9为7的数j为9,可以打出如下i*j/f(i,j)的表,括号内为相邻值的差:

可以发现,每c组i*j/f(i,j)是一个循环节,也就是说可以看作c个等差数列,然后对于每一个等差数列,它的首项我们可以暴力算出,而公差也很容易求出。利用等差数列求和公式可以很快速的计算出结果。复杂度的话,我们需要枚举j和在j剩余系下的i,然后还有c个等差数列,复杂度为O(m^2logN)在接受范围之内。具体见代码:

 

以及。。膜真的很浪费生命啊?

一开始取了5个%,TLE,4个%,50%概率AC,3个%就比较稳得过了…

一个%大概300ms orz

 

 

 

hdu 6038 | 2017 Multi-University Training Contest – Team 1 E Function (置换群找循环节)

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

题意:

给出两个序列 a 和 b ,求满足  f[i]= b_{f[a[i]]} 的函数个数。

思路:

分别找两个序列的循环节,这一点是比较容易想到的。

由于点都在0..n-1 或者0..m-1,因此没必要建图跑dfs找循环节,直接while就可以了。

然后发现一个循环节如果符合条件,那么对答案的贡献是循环节长度。

但是没有想清楚,什么才是符合条件的循环节。

结论是,b的循环节长度当且近当是A的循环节的长度的因子时,b的这个循环节会对答案贡献其长度的大小。

对于A的每个循环节,都是互不影响的。

而且我们只关心循环节的长度。

因此O(n)和O(m)的时间,处理出所有循环节的长度。

然后分别枚举累计答案即可。

但是我怎么感觉。。。这复杂度不太对啊。。。。

对于O(1E5)的序列。。我好像可以构造出1E5个长度为1的循环节?

那么1E5 * 1E5,1E10的复杂度了。。。

然而看了下官方题解。。。发现给出的复杂度分析是O(n+m)

?????????????????????

所以这是说。。。数据保证O(n*m) < O (n+m)了么。。。

这是面向数据解题。。还是说我哪里想错了啊。。。orz

 

 

 

 

hdu 6034 2017 Multi-University Training Contest – Team 1 B Balala Power! (贪心)

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

题意:

有一个仅由小写字母组成的字符串,要求将a..z的字母,对应到0..25,每个数字只能被一个字母对应,得到一个26进制的数,现在问这个数最大是多少。注意不允许有前导0,除非这个数本身就是0.

 

思路:

贪心。看哪个字母的权值最大。

可以用类似高精度加法的方式处理。

对于前导0的部分,用一个bool标记首位(如果字符串长度为1就不标记)

对于26个高精度数的排序,可以用交换id的技巧。

以及,如果排序之后,发现权值最小的数被对应到数字0,但是又在某个长度大于1的字符串的首字母位置出现过。

我初始想当然得,把该字母和最小的可以出现在首位的字母交换….

然而这很错啊?

实际上,更优秀做法是,找到第一个可以出现在首位的字母,然后从该字母后面到结尾,依次前移一位,最后把这个可以出现在首位的字母放在最后。

比如这组数据:

7
abcdefghijklmnopqrstuvwxyz
zz
yy
xx
ww
uu
vv

 

权值按照从大到小排列

z u v w x y t 显然不如  u v w x y z t  优

 

 

 

 

 

 

hdu 6043 | 2017 Multi-University Training Contest – Team 1 K KazaQ’s Socks (循环节)

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

题意:

n双袜子标号1到n,初始在抽屉里,每天早晨穿一双标号最小的袜子,晚上把脏袜子放到盆里,如果放完之后喷子里已经有了n-1双脏袜子,那么就要洗,然后在第二天晚上放回抽屉里。问第k天穿的是标号为几的袜子。

思路:

手写了几个发现对于n双袜子,标号出现的情况是:

1,2,3…n,1,2,3…n-2,n-1,1,2,3…n-2,n

所以特判k<=n的情况然后算循环的次数即可。