FST王者

编辑于 2021-11-26 18:03

牛客挑战赛54题解

A 小䓤的01串

将该01串重复两次，即可操作包含起点和终点相连的区间了。举个例子，对于字符串"abcdef"而言，我们重复两次可以得到"abcdefabcdef"，那么"dfeab"区间可以通过取下标[3,7]得到。
显然合法染***间的长度一定是 $n/2$ 。我们可以通过前缀和达成 $O(1)$ 查询，或使用队列等数据结构达成 $O(1)$ 转移。总复杂度 $O(n)$

B 小䓤的一个数字

枚举操作二的次数，假设为 $t$ 次，则此时对二进制数为 $1$ 的位 $x$ 的代价为区间 $\min\limits_{i=x-t}^x a_i$ 。

C 小䓤的一些数字

$k\geqslant 3$

容易发现 $\sqrt[k]{i}$ 的取值最多有 $10^6$ 种于是我们每段暴力跳即可
$k=2$

就转为求 $\displaystyle \sum_{i=0}^n \lfloor\sqrt i\rfloor$
- 法一
  
  容易发现 $\lfloor\sqrt{i}\rfloor=j$ 的 $i$ 有 $2j+1$ 个，故分零块整块处理。具体的，令 $m=\max\{x|(x+1)^2-1\leqslant n\}=\lfloor\sqrt{n+1}\rfloor-1$ ,则 $\displaystyle ans=\sum_{i=1}^m i(2i+1)+m(n-(m+1)^2+1)=\frac{(m+1)(m+1)(2m+1)}{3} +\frac{m(m+1)}{2}+(m+1)(n-(m+1)^2+1)$
- 法二
  
  引入一个结论:
  $\sum_{i=0}^{n-1}\lfloor\sqrt i\rfloor =n\lfloor\sqrt n\rfloor-\frac{1}{3}\lfloor\sqrt n\rfloor^3-\frac{1}{2}\lfloor\sqrt n\rfloor^2-\frac{1}{6}\lfloor\sqrt n\rfloor$
  证明来自《Concrete Math》:
  $\sum_{i=0}^{n-1}\lfloor\sqrt i\rfloor \\=\sum_{i,j}[1\leqslant j \leqslant \sqrt i][0\leqslant i<\lfloor\sqrt n\rfloor^2] \\=\sum_{j=1}^{\lfloor\sqrt n\rfloor-1}[j^2\leqslant i<\lfloor\sqrt n\rfloor^2] \\=\sum_{j=1}^{\lfloor\sqrt n\rfloor-1}(\lfloor\sqrt n\rfloor^2-j^2) \\=n\lfloor\sqrt n\rfloor-\frac{1}{3}\lfloor\sqrt n\rfloor^3-\frac{1}{2}\lfloor\sqrt n\rfloor^2-\frac{1}{6}\lfloor\sqrt n\rfloor$
  由此问题得到解决

D 小䓤的质因数

操作后，只剩一种质因子，只需要算出每种质因子最后剩余的概率。

设 $\sum c_i=m$ ， $f_i$ 表示一种质因子的次幂为 $i$ ，最后剩余这种质因子的概率，则 $f_0=0,f_m=1$ 。

手动高斯消元可以做到 $\mathcal O(\sum c_i)$ ，发现高斯消元的式子为 $f_i=\frac{(f_{i-1}+f_{i+1})}{2}$ ，可以得道 $f$ 为等差数列，结合 $f_0$ ， $f_1$ 的初值， $f_i=\frac{i}{m}$ 。

复杂度为 $\mathcal O(n\log n)$ 。

E 小䓤的石头

按关键字排序后，问题变为对于定的左端点找到最小的合法右端点。

考虑双指针贪心，注意到问题不可撤销使用对顶栈技巧:即维护两个对顶栈，后一个栈维护的顺序和前一个栈维护的顺序相反，前一个栈空的时候就暴力重构。合并是朴素的。

然后模仿albus要第一个出场技巧每次插入/合并时高斯消元就可以处理本质可重K小异或和。

复杂度为 $\mathcal O(n\log^2(\max a_i))$ 。

F 小䓤的树

以最小值为根，一定满足父节点小于子节点。

将点权转化到边权上，设 $a_x>a_y$ ，则加入 $(x,y)$ 的贡献为 $a_x+a_y*(dis(x,y)+1)$ ， $a_x$ 可以直接加入贡献，剩下的部分变为对每个 $x$ 找到 $y$ 为新树的父亲使得 $a_y*(dis(x,y)+1)$ 最小。

可以用点分治处理 $dis(x,y)$ ，将 $a_y*(dis(x,y)+1)$ 转化为以 $dis(x,y)$ 为变量， $a_y$ 为斜率的直线，即可用李超线段树计算最小代价。

复杂度为 $\mathcal O(nlog^2n)$ 。

G 小䓤的凸包

题目大意为给定 $n,x,y,a,b$ 求

$\sum_{i=1}^n\sum_{j=1}^n \left[\frac{i}{j}\leqslant \frac{x}{y}\right][i\perp j]i^aj^b$

首先化式子，下设 $S_k(n)=\sum\limits_{i=1}^n i^k$ 。

$\begin{aligned} ans=&\sum_{i=1}^n\sum_{j=1}^n \left[\frac{i}{j}\leqslant \frac{x}{y}\right]i^{a}j^{b}[i\perp j] \\=&\sum_{i=1}^n\sum_{j=1}^n i^{a}j^b\left[i\leqslant \frac{xj}{y}\right]\sum_{d|i,d|j}\mu(d) \\=&\sum_{d=1}^n\mu(d)d^{a+b}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j^b\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} i^a\left[id\leqslant \frac{xjd}{y}\right] \\=&\sum_{d=1}^n\mu(d)d^{a+b}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j^bS_a(\lfloor\frac{xj}{y}\rfloor) \end{aligned}$

设 $S_a(x)=\sum\limits_{i=0}^a A_ix^i$ ，可以用各种方式求出 $\{A_i\}$ 。