[主席树二分+复杂度分析]牛客IOI周赛28-提高组 C【下克上の天邪鬼】题解
题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想，不难想到利用这个 $\lfloor{a_i\over 2}\rf...
[Min25筛]2021牛客暑期多校训练营6 G【Hasse Diagram】题解
题目概述Hasse Diagram解题报告考虑 $f(n)$ 的递推式，但是如果只考虑单个素数，很明显会数重复，因此一次性考虑完一个素数，即 $p^k$ 。对于 $n\over p^k$ 的所有...
[分治+矩乘NTT]2022牛客暑期多校训练营（加赛）L【Lndjy and the mex】题解
题目概述Lndjy and the mex解题报告首先不难发现长度为 $len$ 的区间的方案数是相同的，因此只需要考虑区间长度而不需要考虑区间位置（乘 $n-len+1$ 即可）。然后考虑长度...
[离线+后缀自动机+LCT]2022牛客暑期多校训练营（加赛）C【Cmostp】题解
题目概述Cmostp解题报告建出SAM，考虑离线，每次添加一个前缀节点 $p_i$ 的时候，就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点改为 $i$ 。查询 $[L,R]...
[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解
题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线，建出可持久化树，如果用并查集维护图的连通性，会发现不...
[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
题目概述Suffix Sort解题报告一直在想Hash，然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组，$a_i$ 表示 $S_i$ 与上一个相同字符的...
[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
题目概述Striking String Problem解题报告神仙题，根本想不到。记 $n$ 为 $S$ 长度，$m$ 为 $T$ 长度，$U_i$ 表示 $S[l_1,r_1]+\cdots+...
[三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解
题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题：不难发现按照 $x$ 排序后，只有 $y$ 递降的那些点是有用的，其他点肯定都被包含在了某些点中。假设前一...
[离线+Trie+倍增]2022牛客暑期多校训练营2 F【NIO with String Game】题解
题目概述NIO with String Game解题报告感觉赛时榜都歪飞了……这题明明不难却只有20个队过。由于对 $t_i$ 只有单字符加的操作，因此最终所有 $t_i$ 长度和不会很长，可以...
[树上解方程+组合数化简]2022牛客暑期多校训练营3 D【Directed】题解
题目概述Directed解题报告这题竟是脑子题……显然这是个树上解方程的题目，设 $D_x$ 为 $x$ 的度数，$fa$ 为 $x$ 的父亲，$u$ 为 $x$ 儿子：$$
f_{x}={1\...
