[后缀自动机parent树+虚树]2022牛客暑期多校训练营1 B【Spirit Circle Observation】题解
题目概述Spirit Circle Observation解题报告找性质题最烦了.jpg。首先建SAM，考虑一个直观的做法。直接考虑枚举SAM里的节点，然后在节点上考虑 $a999\cdots$...
[线段树合并/分裂]2022牛客暑期多校训练营1 F【Cut】题解
题目概述Cut解题报告这题思路是不难的，但是如果没写过类似的就会巨难写（细节比较多）……把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值线段树的顺序进行排列（正序或者倒序...
[背包回退+二进制状压DP+NTT]2022牛客暑期多校训练营1 H【Fly】题解
题目概述Fly解题报告首先想到DP：$f_{i,j,0/1/2}$ 表示前 $i$ 个二进制位（从低位到高位），到 $i$ 这位时背包大小为 $j$ ，并且状态为 $0$ 小于 $1$ 相等 $...
[生成函数+多项式除法求系数]2021牛客暑期多校训练营8 H【Scholomance Academy】题解
题目概述Scholomance Academy解题报告伪装成数论题的多项式全家桶题。首先我们可以把 $\varphi(n)$ 拆成 $\prod\varphi(p_i^{a_i})$ ，因此不难...
[差分+二分+主席树]2021牛客暑期多校训练营7 K【xay loves sequence】题解
题目概述xay loves sequence解题报告先对数组差分，令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+1$ 和 $-1$ ，所以不难发现...
[线段树+复杂度分析+差分+树状数组]2021牛客暑期多校训练营7 B【xay loves monotonicity】题解
题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题，定义 $Find(p,l,r,i)$ 表示在 $[l,r]$ 的节点 $p$ 前...
[期望DP+分治FWT]2021牛客暑期多校训练营6 D【Gambling Monster】题解
题目概述Gambling Monster解题报告显然是个期望DP，倒着考虑正常一点（因为在 $n-1$ 处结束，步数为 $0$ ），所以我们倒着DP。定义 $f(i)$ 表示 $i$ 走到 ...
[矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解
题目概述Starch Cat解题报告正解是猫树，但是我不会，所以我选择黑科技。首先我们能想到一个比较暴力的做法，每次询问 $x,y$ 路径上的最大独立集，就是求 $x\to LCA(x,y),y...
[二进制分块]2021牛客暑期多校训练营3 I【Kuriyama Mirai and Exclusive Or】题解
题目概述Kuriyama Mirai and Exclusive Or解题报告第一种操作没什么好讲的，我们关注第二种。这种加法和异或混合的一般都只能考虑按位统计贡献。考虑 $[L,R]$ 第 $...
