后缀自动机·基本概念

以下全文转载自hihocoder,今天看了一遍突然就懂了,难道我以前看的都是假文章?
小Hi:今天我们来学习一个强大的字符串处理工具:后缀自动机(Suffix Automaton,简称SAM)。对于一个字符串S,它对应的后缀自动机是一个最小的确定有限状态自动机(DFA),接受且只接受S的后缀。

阅读全文

2017年多校联训9 部分题解

Tips

仅含题解,代码详见github喜欢的话点个star

阅读全文

hdu 6158 The Designer

题解

比赛之后有大佬说这题可以用圆的反演来做,学习了一下。

以两个大圆的切点为反演中心,任取一个反演半径,两个大圆会变成两条平行线。再考虑小圆的反演,由于相切的性质不变,小圆的反演圆就是一列夹在平行线中间的小圆。

阅读全文

hdu 6156 Palindrome Function

题意

定义函数 $f(n,k)$,当 $n$ 在 $k$ 进制表示为回文数时,$f(n,k)=k$;否则 $f(n,k)=1$ 。求 $\sum_{i=L}^{R}\sum_{j=l}^{r}f(i,j)$ 。($1 \leq T \leq 10^5, 1 \leq L \leq R \leq 10^9, 2 \leq l \leq r \leq 36$)

阅读全文

2017年多校联训8 部分题解

Tips

仅含题解,代码详见github喜欢的话点个star

阅读全文

hihocoder 1553 区间统计

题意

#1553 : 区间统计 中文题。

阅读全文

hdu 6129 Just do it

题意

有一个长度为 $n$ 的整数序列 ${a_n}$,对其做 $m$ 次前缀异或和,求最终的序列。

题解

对这个过程手动模拟几行,注意不要消去,可以发现第 $m$ 次第 $i$ 个数的结果包含了 $C_{m-1+i-j}^{i-j}$ 次第 $j$ 个数($j\le i$) 。

阅读全文

hdu 5893 List wants to travel

题意

给出一棵树,要求支持:

  1. 询问从u到v整条路径有几段边权(相同边权连成一段);
  2. 修改从u到v整条路径的边权。

阅读全文

hdu 5901 Count primes

题意

输出[1..n]的质数个数 (1 <= n <= 1e11) 。时间限制6s,空间限制64M 。

题解

很显然,要用线性筛的话时间和空间都不够。

阅读全文

2017年多校联训3 部分题解

Tips

仅含题解,代码详见github喜欢的话点个star

阅读全文