Timeline

Timeline

08:10-08:20

通看一遍题目，感觉除了 C 都不是很可做的样子，

08:20-08:40

把 A 暴力打了

08:40-08:45

好好好，C 一开始看的时候看错题意了，又变得不太可做了

08:45-09:00

把 C 暴力打了

09:00-09:20

把 B 暴力打了

09:20

D 最小的点居然还有 1e3 /jk GG

Summary

  1. A 这么简单居然没想出来 /cf

  2. 别摆。

  3. 对于 n≤1000n\leq 1000 的稠密图，跑 Dijkstra 时要用邻接矩阵建图跑最短路。

Problem

T1

有一张 nn 点 mm 条含权无向边的图，每个点都有一辆出租车，每辆出租车最远可以开的距离为 did_i，花费 cic_i 的代价，给定起点和终点，最小化代价，无法到达输出 −1-1。

1≤n≤1000,1≤di,ci≤1091\leq n\leq 1000,1\leq d_i,c_i\leq 10^9

Solution

从每个点 ii 跑一遍 Dijkstra，若到某个点 jj 的距离 distj≤didist_j\leq d_i 则说明从此点可到 jj，连一条权值为 cic_i 的有向边，然后再从起点跑一遍 Dijkstra 即可。

时间复杂度 O(n2log⁡n)\mathcal{O}(n^2 \log n)。

T2

有 mm 件物品，有 nn 个人都分别拍下了 22 件物品，对于第 ii 个人来说，第一件物品 ∈[1,li]\in [1,l_i]，第二件物品 ∈[ri,m]\in [r_i,m]，问所有可能情况对 998244353998244353 取模后的结果。

m≤3000m\leq 3000

Solution

将问题转化为往 n×mn\times m 的网格上填点，每列只能填一个点，对于第 ii 行，[1,li][1,l_i] 列和 [ri,n][r_i,n] 列个恰好有一个点。

设 fi,j,kf_{i,j,k} 为考虑前 ii 列，有 jj 个右区间未满足，有 kk 列未填点的方案数，转移时考虑这一列是否用来匹配右区间，同时 kk 可以直接算出来，故省去一维。

左区间怎么办？转移时的条件就已经满足了当前的左区间。

时间复杂度 O(nm)\mathcal{O}(nm)。

T3

给出 nn 个区间 [li,ri][l_i,r_i]，∀i∈[1,n]\forall i\in [1,n]，询问前 ii 个区间的并集中有多少对数满足两数异或和的二进制表示下有奇数个 11。

n≤105,1≤li≤ri≤232−1n\leq 10^5,1\leq l_i\leq r_i\leq 2^{32}-1

Solution

先搬出来两个结论：

  1. 两数异或和的二进制表示下 11 的个数的奇偶性只和两数本身二进制下 11 的个数的奇偶性有关，因为每次异或都只会抵消掉偶数个 11，所以我们只需要知道当前有多少个数字二进制下有奇数个 11，二进制下有偶数个 11 即可。

  2. 前 xx 个数中二进制表示下 11 的个数为奇数的数有 x2+(x mod 2or⁡popcount⁡(x) mod 2)\frac{x}{2}+(x\bmod 2 \operatorname{or} \operatorname{popcount}(x)\bmod 2) 个，数学归纳法可证。

那么建一棵动态开点的线段树，维护区间中二进制表示下 11 的个数为奇数和偶数的数的数量即可。

时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。

T4

有一棵 nn 节点的树和 mm 个数 did_i，三个人轮流任意选一个点占据直到所有的点都被选完，接下来每个人各自占据的点中，若两点之间的距离在 did_i 中，则可以删除一个病毒，问三个人分别期望能删除多少个病毒。

n≤50000,m≤10n\leq 50000,m\leq 10

Solution

一个人若占据了 xx 个点，那么方案数为 CnxC_{n}^{x}，占据某个固定点对的方案数为 Cn−2x−2C_{n-2}^{x-2}，那么占据某个固定点对的概率为 Cn−2x−2Cnx=x(x−1)n(n−1)\frac{C_{n-2}^{x-2}}{C_{n}^{x}}=\frac{x(x-1)}{n(n-1)}。

用点分治看每个 did_i 的点对数量有多少，期望即为数量乘上概率。

时间复杂度 O(nmlog⁡n)\mathcal{O}(nm\log n)。