2024.11.11 模拟赛

Whitely · 2024-11-12 14:12:34 · 题解

2024.11.11 模拟赛

A

给定非负权有向图，定义 d(i,x,y) 为 x\to y 中间（不含端点）不经过 i 最短路，不存在则 -1，求 \sum_{1\le i,x,y\le n}d(i,x,y)，要求 O(n^3\log n)。

Sol

考虑 Floyd，第一层处理 k 相当于允许中途经过 k，想到前后缀合并 Floyd。考虑合并两个 Floyd 的复杂度，设两组点大小分别 p,q(p\le q)，只能做到 O(p(p+q)^2)，考虑用若干个长为 2^k 的区间覆盖 [1,n]-i。

可以借助线段树的结构，处理到 [l,r] 时拓展过 [1,n]-[l,r] 中所有点，处理到 [i,i] 时即为答案。每一轮中，拓展左区间所有点递归右区间，再拓展右区间所有点递归给左区间即可，这里处理 i 指处理以 i 中转的路径。

B

给定带边权无向图，定义 f(i,j) 为 i\to j 异或最长路，每次询问 l,r 求 \sum_{l\le i<j\le r}f(i,j)，n,m,q\le 2\times 10^5,0\le w<2^{61}。

Sol

异或并没有当前最优即为全局最优的性质，考虑简化无向图的结构，取出一棵生成树，每条非树边对应一个环，则 i\to j 最优路径异或和为 dis_i\oplus dis_j 再异或上若干个环的异或和，可以线性基处理，此处 dis_i 表示树根到 i 树上路径的异或和。

设 \operatorname{Min}(x) 为 x 在所有环边权异或和构成的线性基中异或得到的最小值，\operatorname{Max}(x) 同理，则所求即为 \sum_{l\le i<j\le r}\operatorname{Max}(dis_i\oplus dis_j)，不同 (i,j) 之间这个值似乎并无关联。

Trick: \operatorname{Max}(x\oplus y)=\operatorname{Min}(x)\oplus \operatorname{Max}(y)。

Proof: 设 \operatorname{LHS}=z,\operatorname{Min}(x)=X,\operatorname{Max}(y)=Y，线性基为 b_{0\dots 64}，则不存在某一位 i，使得 b_i\neq 0，且 X_i=1 或 Y_i=0 或 z_i=0。

• 对于 b_i\neq 0 的位，满足 z_i=X_i\oplus Y_i。
• 对于 b_i=0 的位，x,y,x\oplus y 这一位都不会改变，同样满足。

下面说一种不需要上述性质的做法，因为你只需要 ^1\operatorname{Max}(dis_i\oplus dis_j) 的值，不妨改变 dis_i 的值到 d_i，使 ^1 值不变的情况下与 d_i,d_j 的关系更加明显。

需要满足 ^1 不变，想到用 dis_i 在线性基中异或若干个值，尝试简化 ^1 为 d_i\oplus d_j\oplus b_{0\dots 64}，则需要满足所有 b_k\neq 0 的位均有 d_{i,k}=d_{j,k}，使这个值为 0，想到 d_i=\operatorname{Min}(dis_i)，若 \exist b_k\neq 0,d_{i,k}\neq 0，可以异或变小。

回到原问题，只需要知道 d_{l\dots r} 内每一位为 1 的数的个数即可计算答案，复杂度 O(q\log V+n\log V)。

C

给一棵树，带点权，所有边初始未解锁，三种操作：

1. 解锁一条路径上每条边。
2. 撤销到上次操作 1 之前的状态。
3. 计算从 u 开始只经过解锁边可以到达的所有点点权之和。