多校 A 层冲刺 NOIP2024 模拟赛 04

多校A层冲刺NOIP2024模拟赛04

T 02表示法

签到题

记得有一道普及题是没加高精的原吧...

将原数高精除变为二进制，然后记搜就好了。

T 子串的子串

签到题

注意到 \(n\) 很小支持 \(O(n^2)\) 的操作，可以直接预处理出所有 \(l,r\) 的个数，预处理方式可参考数颜色一题，对于相同的子串只记录随靠右的贡献。对于判断前驱可以 \(hash\) + \(unordered_map\) 由于串比较多，考虑聪明一点记录前驱，可以按长度分组做，这样每组最多有 \(O(n)\) 个子串 \(hash\) 冲突概率大大降低，常数也就变小了。

时间复杂度为 \(O(wn^2+q)\)。

T 魔法咒语

trie树，计数题

首先用 trie 树对所有前后缀去重，直接正反插入一遍就好了。

现在考虑怎样拼接前后缀才能做到不重不漏，发现如果直接拼接会计重是因为一个前缀的后缀与一个后缀的前缀相等，导致拼接时结果相同结果的断点有多个，考虑枚举前缀，对于一个前缀在其 trie 树中所对应的结点，不将结点子树中已有字符的贡献加入，这样就保证了上述情况只会计算一次，但是会有一种情况会算漏，即刚好以子树中存在的字符为结尾，直接特判记录单个后缀字符即可，以及特判长度为 1 的串就行了。

时间复杂度为 \(O(w\sum |s|)\)，\(w\) 为字符集大小 。

T 表达式

crt，线段树

首先看到有一些数据点的模数很小，从而产生以模数为值域，预处理出一段区间内这个值域内数从左到右依次计算这个区间最后的值，这个东西显然是具有结合律的，可以上线段树。

但是对于其他点来说时间复杂度直接爆炸了，每一次区间合并时间复杂度都是 \(O(P)\) 的。

注意到题目给出的模数并不是一个质数，考虑拆解模数，然后分别做上述相同的操作，最后 crt 合并就行了。前 3 个点依旧需要暴力。

时间复杂度为 \(O(Snlogn)\)，\(S\) 为模数拆解后的和。

p