CF547E Mike and Friends
Codeforces Luogu 分析 考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。 将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。 代码 // =================================== /...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
Codeforces Luogu 分析 考虑 AC 自动机，则相当于将 trie 树上 $[l,r]$ 内的串对应的链加 $1$，然后查询 fail 树上 $k$ 子树内的和。 将每个询问拆成两个（$[1,l-1]$ 和 $[1,r]$），并将所有询问离线、排序，用树状数组维护 fail 树上子树和即可。 代码 // =================================== /...
Luogu LOJ 分析 设 $f(\alpha)$ 为正多边形旋转角度为 $\alpha$ 时的最短时间，容易发现 $f(\alpha)$ 是单谷的，因此可以三分 $\alpha$。 考虑如何计算 $f(\alpha)$。二分 $f(\alpha)$ 的值 $t$，如果某艘飞船在 $t$ 时间内能够到某个位置则它们可以匹配，判断是否存在完美匹配即可。 这样子可能过不了，考虑一些优化。我们预...
Luogu LOJ 分析 暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。 考虑用 KD-Tree 优化模拟过程。 我们把每个圆看作它的外接矩形，然后对于当前删去的圆在 KD-Tree 上递归，如果圆与矩形没有交则不会更新，可以直接返回。 然后建树时按方差选维度就可以过了。 代码 // =================================== // ...
Luogu LOJ 分析 设第一个部落的领地为 $A$，第二个部落的领地为 $B$。 假设 $B$ 移动了 $\vec{v}$ 后 $A$ 和 $B$ 仍有交，说明存在 $a\in A,b\in B$，满足 $b+\vec{v}=a$ 即 $\vec{v}=a-b$。 构造 $A$ 和 $-B$ 的闵可夫斯基和 $C$，问题变为判断 $\vec{v}$ 是否在 $C$ 内，二分出极角相邻的点...
Luogu LOJ 分析 显然，所有学生跑到指定位置后，相对位置不改变会最优。 那么最终会有一部分学生向左跑，一部分学生向右跑，而且两部分一定是分开的。 考虑建立一棵以位置为下标的主席树。 设 $rk_i$ 表示 $i$ 是当前区间中的学生中编号第 $rk_i$ 小的。若当前递归的区间是 $[l,r]$ ，分四种情况： 没有学生，直接返回 $0$ 。 全部向左跑，直接返回 $\sum a_...
Luogu 分析 先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。 考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直...
LOJ 分析 注意到 不妨假装 $f(2)=1$，于是就可以 Min_25 筛了。 考虑到在 Min_25 筛的第二步即求 $S(n,j)$ 时，如果 $j=1$ 则质数部分算了 $2$ 的贡献，直接加上 $2$ 即可。 代码 // =================================== // author: M_sea // website: http://m-s...
设 $f$ 为积性函数，且其在质数处的取值 $f(p)$ 是关于 $p$ 的多项式，且其在质数的幂的取值 $f(p^c)$ 能快速计算，则 Min_25 筛可以在 $\mathcal{O}(\frac{n^{\frac{3}{4}}}{\log n})$ 的时间复杂度内算出 $\sum_{i=1}^nf(i)$。 思路 为了方便，设 $\mathrm{P}$ 为质数集，$p_i$ 为第 $...
Luogu 分析 首先那个规定的意思是如果往左走就要把左边所有没治愈的村庄治愈。 可以发现整个过程可以划分成若干段，每段以任意顺序治愈后回到该段的起点，再治愈下一段。 考虑 DP。设 $dp_i$ 表示治愈前 $i$ 个村庄的最小死亡人数。记 $s$ 为 $a$ 的前缀和，$w_{i,j}$ 为从 $i$ 出发治愈 $[i,j]$ 中所有村庄再回到 $i$ 的最小死亡人数，容易得到转移 边...
Luogu 分析 容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。 第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到 第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$...