水题记录(三)

10 / 10

CQOI2016 K远点对

题意:求出平面内$N$个点,欧几里得距离下的第$K$远点对距离的平方。

题解:拿个优先队列维护$k$个值,Kdtree剪剪枝就做完了。(不开long long 爆零到怀疑人生

Substrings

题意:求一个序列中长度为$i$的出现次数最多的子串

题解:SAM模板题,基排算$Right$然后更新即可,复杂度$O(n)$。

Longest Common Substring

题意:计算LCS。

题解:对$A$串建立SAM,$B$串在SAM上找。对于一个点$i$,计算从$i$开始向前的最大长度$L$,答案为$min(L,max(s))$。在SAM上如有这个转移边$len=len+1$,不然就跳$parent$。

SubString

题意:在线维护(1)在给定串后插入字符串(2)询问s在串中出现次数

题解:考虑对串建立SAM,要做的事情就是询问这个点right集合大小。考虑插入一个字符需要更新这个点到根的路径,而且还要支持Link和Cut节点。

所以可以使用LCT维护SAM的parent树,维护子树和即可。

询问的时候记得pushdown….(ps:超多bug调到想死,调了三天….感觉我的LCT还是有点问题..就是个代码题,思维难度较低。

LCS 2

题意:求多个串的$LCS$

题解:同上,只不过在每个状态的$max$中间取$min$,对于每个状态都要记录,对于一个状态$s$,它的结果也可以作为它的$parent$的结果,需要更新,不然WA#10。

DZY Loves Math

题意:令$f(x)$表示数$x$的分解质因数后指数幂的$max$。求$\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$

题解:数学题,根据套路,设$g(x)$表示$gcd(a,b)=x$的方案数。
$$
ans = \sum_{x=1}^{min(a,b)}g(x) \times f(x)\
$$
令$G(n)$表示$gcd(a,b)$为$n$倍数的方案数。
$$
G(n) = \lfloor \frac{a}{n} \rfloor \times \lfloor \frac{b}{n} \rfloor \
G(n) = \sum_{n| d}g(d)\
g(n) = \sum_{n|d} \mu(\frac{d}{n}) \times G(d)\
g(n) = \sum_{n|d} \mu(\frac{d}{n}) \times \lfloor \frac{a}{d} \rfloor \times \lfloor \frac{b}{d}\rfloor \
ans = \sum_{n=1}^{min(a,b)}f(n) \times \sum_{n|d} \mu(\frac{d}{n}) \times \lfloor \frac{a}{d} \rfloor \times \lfloor \frac{b}{d}\rfloor\
ans =\sum_{d=1}^{min(a,b)}\lfloor \frac{a}{d} \rfloor \times \lfloor \frac{b}{d}\rfloor \sum_{n|d}\mu(\frac{d}{n}) \times f(n)
$$
$ g(d)=\sum_{n|d}\mu(\frac{d}{n}) \times f(n)$这个东西是可以$O(n)$预处理的。


$$
n=\prod{a_i} ^ {p_i}\
d=\prod{b_j} ^ {p_j}\
$$
如果$\frac{d}{n}$包含平方数,也就是$|p_i-p_j| > 1$,那么$\mu(\frac{d}{n})=0$

(1)存在一个$p_i \neq p_j$,一定有$g(d) = 0$。

证明:考虑到对于$\mu({\frac{n}{d}})$每个质数最多只能使用一次,因此$mu$的值和质数使用的奇偶性有关。

把$a_i$分为两个部分一个部分是最大的集合A,另一个是最大的非集合部分B,B中奇偶性方案数相等,得到的和都是0

(2)所有$p_i = p_j$,一定有$g(d) = -1^n$。同上,$f$都可以消掉。最后剩下$\prod a_i ^ {p_i – 1}$,所以答案就是$\mu(\prod a_i^{p_ i – 1}) = -1^n$

于是可以分块计算,总复杂度$O(T * \sqrt n)$

POI2014 Hotel

题意:求一棵树上三元组$(i,j,k)$使得两两距离相等的方案数

题解:注意到$n$比较小,可以接受$n^2$的复杂度,不妨暴力DP。枚举一个中心点,要求的是他的子树中三个深度为$i$的数目,我们可以每次$dfs$一次,然后DP出一个点深度为$k$的方案数,两个点深度为$k$的方案数,转移即可。

POI2007 Zap

题意:求$\sum_{i=1}^{a} \sum_{j = 1}^{b} gcd(i,j)=k$的方案数

题解:
$$
\sum_{i=1}^{\lfloor \frac{a}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{b}{k} \rfloor } gcd(i,j)=1\
\sum_{i=1}^{\lfloor \frac{a}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{b}{k} \rfloor } \sum_{d | gcd(i,j)} \mu(d)\
\sum_{d = 1}^{min(\lfloor \frac{a}{k} \rfloor,\lfloor \frac{b}{k} \rfloor)}\mu(d) \times \lfloor \frac{\lfloor \frac{a}{k} \rfloor}{d} \rfloor \times \lfloor \frac{\lfloor \frac{b}{k} \rfloor}{d} \rfloor
$$
分块计算即可。

陌上花开

题意:三维偏序

题解:复习一下CDQ,学习了一种更好理解的写法,这个题貌似还可以KDTree?简而言之就是先按$x$值sort,然后分治的时候按照$y$排序,用树状数组处理前面对后面的影响。

HNOI2018 寻宝游戏

题意:给出$n$个长度为$m$的二进制数,可以在两个数之间填入“或”和“与”,$q$次询问使得答案为$x$的方案数

题解:把每一位分开考虑,把从最下面的作为最高位,每一列组成一个二进制数$c$。同样的,从最后一个操作开始,把或看成”0“,与看成”1“,组成一个二进制数$x$。我们发现,如果$x<c$,这位的答案为$1$,否则为$0$。于是我们把每一位的二进制数排序,然后找到一个断点,左边都是0,右边都是1。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*