BZOJ Water Problem Sol.

解水题,水题解,题解水。

3621

已知一个三角形经过旋转缩放后得到另一个三角形。显而易见这是一个中心仿射变换。给出这两个三角形各点坐标,求仿射中心。

Sol.

变换矩阵为

$$ \left[ \begin{matrix} a\cos\alpha &a\sin\alpha\\ -b\sin\alpha & b\cos\alpha \end{matrix}\right] $$

联立解一下,用第三组点验证即可。一共 $ 3! $ 。仿射中心就是这个变换下的不动点。

换另一个角度,考虑复数乘法的几何意义:幅角相加,模长相乘(由欧拉公式显然)。这不就包含了平移缩放的全部信息吗!

对每一个点显然有 $ T(A'-P)=A-P $ ,其中 $ T $ 为变换复系数, $ P $ 为变换中心,$ A, A' $ 为变换后前的点。

Inspiration

二维平面的旋转缩放可以使用复数运算代替矩阵。

3631

对一棵树给出遍历顺序,问所有点的遍历次数,最后一个访问的点少计一次。点数 $ \le 3\times10^5 $ .

Sol.

树上差分后树 DP 统计前缀和。

一个点可能会被计两遍,再遍历一遍减去就好。

Inspiration

树上差分然后树 DP 计算前缀和。

3759

至多 $20$ 个箱子。每次可以打开任意一些箱子,或是取某个打开的箱子中的任意个石子。无法操作者输,问先手是否必胜。

Sol.

考察先手必败的情况:当前打开的箱子的异或和为零,且未打开的箱子不存在一个子集异或和为零。

只需注意到在这种情况下先手无论怎么动后手都有策略移动到 SG 值为零的局面。

维护线性基查看是否初始局面存在异或和为零的子集即可。

3884

求模 $ p \le10^7 $ 意义下 $ 2 $ 的无穷阶幂塔的值.

Sol.

记 $ f(p) := \mod p $ 意义下的答案,则根据拓展欧拉定理有

$$ f(p)\equiv 2^{f(\varphi(p))+\varphi(p)} \pmod p $$

并不会证为什么 $ \varphi $ 的嵌套是 $ \log $ 阶的.

以及吐个槽,这个式子在模意义下收敛,但没有模意义就是个未定式. 高一或者再之前没学和式的一般理论的时候懵逼了好久为什么这题可做.

5091

$ n $ 点 $ m $ 边无向图. 每个点度数为 $ d _u $ . 以概率 $ d_i\over2m $ 随机选一个点为起点,重复 $ k $ 次从当前点等概率选一条边出去,在终点 $ v $ 采 $ a_v $ 的果子. 求果子数期望. $ n\le10^6,m\le2\times10^6 $ .

Sol.

设 $ f_{i,j} $ 为走 $ i $ 步到 $ j $ 点的概率,有 $ f_{i,j}=\sum_v {f_{i-1,v}\over d_v} $ .那么 $ f_{0,j}={d_j\over2m} $ .

注意到 $ f_{1,j}=\sum_v {f_{0,v}\over d_v}={d_j\over 2m} $ .

同理可得 $ f_{i,j}={d_j\over2m},\forall i $ .

答案 $ \mathbb E=\sum_{i=1}^n \sum_{j=1}^k f_{j,i} a_i={k\over2m}\sum_{i=1}^nd_ia_i $ .

5301

给一个长度 $ 10^5 $ 的数列和 $ k $ 。$ q\le10^5 $ 组询问,区间 $ [L,R] $ 内多少个子序列的异或和是 $ k $ .

Sol.

没什么好说的……都是询问就考虑莫队……处理出前缀和后意味着在 $ l-1..r-1 $ 之中找一个 $ a_r\oplus k $ 的数个数。维护个桶就好了……

我好像……两年没打过莫队了……从原理一步一步想要怎么打的……这都能 1A.

听说对序列分块会被卡??这出题人真没良心。

标签: none

添加新评论