decoqwq

编辑于 2019-08-26 20:06

+ 关注

【题解】牛客NOIP暑期七天营-提高组5

先对各位道歉QAQ，听说T2数据好像有点锅..T2 T3本身设立的正解好像没人写QAQ，由于出题人考虑不周没卡hash，向大家道歉啦QAQ

T1数据修改后范围并未修改，实在抱歉QAQ

T1 abs

这道题显然先将所有数字对d取模，记上一个数为last，当前数为x，则 $ans=\sum\limits min(abs(x-last),min(abs(x+d-last),abs(x-d-last)))$

这道题就做完了

T2 gcd

对于 $30\%$ 的数据，暴力即可

对于 $60\%$ 的数据，可以考虑 $n\sqrt n$ 枚举质因数，容斥原理即可

对于 $100\%$ 的数据，本来正解是莫比乌斯反演，然而好像没卡掉调和级数的做法QAQ

$ans = \prod_{i = 1}^n\prod_{j = i + 1}^{n}gcd(a_i, a_j)$

先考虑枚举gcd
$ans = \prod_{d = 1}d^{\sum_{i = 1}^n \sum_{j = i + 1}^n[gcd(a_i, a_j)=d]}$
通过一些转化把下标的相对顺序去掉
$f(d) =\sum_{i = 1}^n \sum_{j = i + 1}^n[gcd(a_i, a_j)=d] \\ 2f(d) +\sum_{i = 1}^n[a_i= d]= \sum_{i = 1}^n \sum_{j = 1}^n[gcd(a_i, a_j)=d]$
然后套路反演
$o(d)=\sum_{i = 1}^n\sum_{j = 1}^n[gcd(a_i, a_j) = d]$
然后用一些方法把枚举下标变成枚举值域
$o(d) = \sum_{i = 1}^p\sum_{j = 1}^p[gcd(i, j) = d]cnt_icnt_j \\ \sum_{i = 1}^{\lfloor\frac{p}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{p}{d}\rfloor}[gcd(i, j) = 1]cnt_{id}cnt_{jd} \\ \sum_{i = 1}^{\lfloor\frac{p}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{p}{d}\rfloor}\sum_{x|i,j}\mu(x)cnt_{id}cnt_{jd} \\ \sum_{x = 1}\mu(x)\sum_{i = 1}^{\lfloor\frac{p}{dx}\rfloor}cnt_{ixd}\sum_{j = 1}^{\lfloor\frac{p}{dx}\rfloor}cnt_{jxd} \\ \sum_{x = 1}\mu(x)(\sum_{i = 1}^{\lfloor\frac{p}{dx}\rfloor}cnt_{ixd})^2 \\ g(x) = \sum_{i = 1}^{\lfloor\frac{p}{x}\rfloor}cnt_{ix}可以n\log n预处理 \\ g^{2}(x) = g(x)^2 \\ o(d) = \sum_{x = 1}\mu(x)g^2(dx)$

然后实际上就可以枚举dx的乘积，这个时候x和d只需要枚举约数预处理就可以了

这个时候总的复杂度是 $O(n\log n)$

T3 str

Task1

首先我们考虑解决掉双倍友好这个双倍的问题，实际上对于一个双倍友好串我们可以直接分成前一部分和后一部分来进行统计，然后再把前后的友好程度乘起来计算答案

然后实际上我们需要知道的就是S[i, i +|T| - 1]这个串和T的友好程度

然后直接暴力枚举字符串S[i,i+|T| - 1]然后枚举k算友好程度就可以了

Task2

枚举串算友好程度在这里显然不是最优的方式，我们考虑枚举断点k统计贡献

枚举完断点k我们就可以知道实际上友好串的条件转化成了

S[i, k] = T[n - k + i, n],S[k + 1, i + |T| - 1] = T[1, n - k + i - 1]

不难发现前面的条件是S的某一个前缀的一个后缀等于T的一个后缀

后面的条件是S的某一个后缀的一个前缀等于T的一个前缀

然后就可以用算lcp的方式算出点k向前后最多能延伸多长

不妨设左边可以延伸到l，右边可以延伸到r

那么就可以发现字符串S[l,r]的所有长度为|T|的子串都有一个合法的段点k

在这里可以用到差分的思想处理出a[i]表示以a为左端点的串友好程度，b[i]表示以i为右段点的友好程度

用后缀数组/后缀自动机求lcp可以做到 $O(n\log n)$ 的复杂度

Task3

因为数据范围很大，所以直接用后缀数组是不行的

考虑到这里我们只需要求出一个串本身和另一个串的所有后缀的lcp（前缀可以reverse转化成后缀），就可以用扩展kmp算法

扩展kmp算法专门用来求字符串T和S的每一个后缀的lcp

并且因为扩展kmp的复杂度是线性的所以可以通过所有部分分

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(16) 回帖

加载中...

话题同步到我的动态回帖