当前位置：首页 > news >正文

网站建设体会心得利用论坛推广网站

news 2025/9/17 21:15:54

网站建设体会心得,利用论坛推广网站,wordpress修订版本插件,通过qq群可以进行友情链接交换A 大富翁很有意思的题 ∑x∈A∑y∈B[x支配y]−∑x∈A∑y∈B[y支配x]−∑x∈Awx\sum_{x\in A}\sum_{y\in B}[x支配y]-\sum_{x\in A}\sum_{y\in B}[y支配x]-\sum_{x\in A}w_x∑x∈A∑y∈B[x支配y]−∑x∈A∑y∈B[y支配x]−∑x∈Awx ∑x∈A∑y[x支配y]−∑x∈A∑y[y支…

A 大富翁
很有意思的题
$∑x∈A∑y∈B[x支配y]−∑x∈A∑y∈B[y支配x]−∑x∈Awx\sum_{x\in A}\sum_{y\in B}[x支配y]-\sum_{x\in A}\sum_{y\in B}[y支配x]-\sum_{x\in A}w_x$
$=∑x∈A∑y[x支配y]−∑x∈A∑y[y支配x]−∑x∈Awx=\sum_{x\in A}\sum_{y}[x支配y]-\sum_{x\in A}\sum_{y}[y支配x]-\sum_{x\in A}w_x$
$=∑x∈Asizx−∑x∈Adepx−∑x∈Awx=\sum_{x\in A}siz_x-\sum_{x\in A}dep_x-\sum_{x\in A}w_x$
这样每个点的贡献就确定了
排序后取奇数位

C 快速最小公倍数变换
考虑把贡献改写成一个只跟 $r_i$ 相关，只跟 $r_j$ 相关，只跟 $r_i+r_j$ 相关的三个数的乘积
设 $v_p(x)$ 表示质数 $p$ 在 $x$ 质因数分解中的指数大小， $M_p$ 表示所有 $v_p(a_i)$ 的最大值， $m_p$ 所有 $v_p(a_i)$ 的非严格次大值
考虑算出 $M_p$ 在操作之后的改变值 $ΔMp\Delta M_p$
$ΔMp=([vp(ri)=Mp]+[vp(rj)=Mp])(mp−Mp)+max⁡(vp(ri+rj)−Mp,0)\Delta M_p=([v_p(r_i)=M_p]+[v_p(r_j)=M_p])(m_p-M_p)+\max(v_p(r_i+r_j)-M_p,0)$
证明
当 $v_p(r_i)=M_p]=0,[v_p(r_j)=M_p]=0$ 时，显然满足
当 $v_p(r_i)=M_p]=1,[v_p(r_j)=M_p]=0$ 时， $v_p(r_i+r_j)=v_p(r_j)<M_p$ ，满足
当 $v_p(r_i)=M_p]=0,[v_p(r_j)=M_p]=1$ 时，与上种情况类似
当 $v_p(r_i)=M_p]=1,[v_p(r_j)=M_p]=1$ 时， $m_p=M_p$ ，满足
然后就能用 $n tt$ 优化了