20241012 模拟赛

20241012 模拟赛

A. 组合

一眼转化成前缀相减的形式，然后注意到 \(a,b,c\le 2000\)，于是 \(O(n^2)\) 预处理就做完了。

B. 原神

先考虑暴力一点的想法。考虑枚举最靠右的瓶子 \(i\)，再枚举选的瓶子的个数 \(k\)，那么这时无论在前面选了哪些数，答案都会异或上 \(\sum_{j=i-k+1}^{i}a_j\)。这时选数的方案数就是 \(C_{i-1}^{k-1}\)。根据 \(x\ xor\ x=0\)，得出只有 \(C_{i-1}^{k-1}\) 为奇数时才会对答案造成贡献，但此时 \(C_{i-1}^{k-1}\) 会很大，难以判断，而且枚举的复杂度也难以接受。

根据 Lucas 定理，\(C_{i-1}^{k-1}\equiv 1(\bmod 2)\) 当且仅当 \((k-1) \& (i-1)=k-1\)，也就是说在二进制下 \(k-1\) 是 \(i-1\) 的子集。那么每次枚举 \(i\) 的时候，直接枚举 \(i-1\) 的子集就能快速找到所有能造成贡献的 \(k\)。时间复杂度为枚举子集的复杂度，\(O(3^{\log_2n})\)。实际计算量约为 \(2.1\times10^8\)，可以通过。

C. 公交

容易想到对 \(d\) 做前缀和得到 \(s\)。那么询问的式子就形如 \(\min(s_i+vm_i)\)。

大佬说这种形式的求值可以转化为凸包上二分。将每个 \((m_i,s_i)\) 当作平面直角坐标系中的一个点，求出下凸壳。因为斜率为 \(-v\) 的直线在经过点 \((m_i,s_i)\) 时纵截距为 \(s_i+vm_i\)，所以我们只要想象一条斜率为 \(-v\) 的直线从最下方往上平移，那么遇到的第一个点就是作为答案的点。考虑这个点具有什么性质，通过画图可以发现，这个点一定在下凸壳上。记下凸壳上的点为 \(a_i\)。那么连接 \(a_{i-1}\) 与 \(a_i\) 的直线的斜率一定小于 \(-v\)，连接 \(a_i\) 与 \(a_{i+1}\) 的直线的斜率一定大于 \(-v\)。根据这个性质就可以先求出一个凸包，查询时直接二分就能找到答案。

对于这题，我们对序列分块，每次修改 \(d_i\) 时，将 \(i\) 所在的块暴力修改 \(s\) 的值并重构凸包，后面的块直接打一个标记就行了，因为一个块内所有 \(s_i\) 增加相同的值时，就相当于所有点整体上移，对二分并不会造成影响。修改 \(m_i\) 时，也是直接重构整个块即可。查询时，对每个块的凸包二分取最优即可。

设块长为 \(B\)，则时间复杂度为 \(O(qB\log B+\frac{qn\log B}{B})\)，当 \(B=\sqrt n\) 时为 \(O(q\sqrt n\log n)\)。

D. 树

20pts做法

最大的问题在于如何求解 \(f\)。观察样例解释可以发现，当答案最优时，每个节点的权值一定是与它相连的点的权值的平均值。证明不会。根据这个性质，我们就可以列出若干个多元一次方程，直接高斯消元求解即可，\(O(n^4)\)。

根据这个性质，经过一些思考应该可以做到 \(O(n^2)\)，但是遗憾的仍然只有 20pts。

还可以根据一些不等式直接推出每个节点权值的表达式。因为 \(n\leq15\) 时树最多 4 层，直接手算即可。

满分做法

可以找规律或经过复杂推导得出（记 \(s_i\) 为子树和，\(len_i\) 为子树内叶子节点数，\(u\) 不为叶子）：

证明不会。维护不会。