[THUPC2021 初赛] 方格游戏 题解

· · 题解

题意

小 F 和小 H 在玩游戏。今天，他们在一个 N \times M 的棋盘上玩游戏。小 H 想考考小 F 的数学能力，但小 F 天生数学就不好，所以想请你帮忙。

为了加大难度，小 H 会在棋盘里面加入 P 个矩形障碍物。每个矩形障碍物用 U、D、L、R 来表示，即在第 U 行到第 D 行以及在第 L 列到第 R 列之间的所有格子都变成了障碍物。小 H 保证所有矩形障碍物互不相交，并且所有非障碍物格子之间都能够直接或者间接互达，若两个非障碍物格子有公共边，那么它们直接互达并且它们的距离为 1 。

现在每一局游戏中，小 F 在棋盘中挑选一个非障碍物格子 X，小 H 也挑另外一个非障碍物格子 Y，这一局游戏 (X,Y) 的得分就是 X 到 Y 的最短路径。小 F 需要计算出所有可能的游戏中的得分和，答案模 1,000,000,007。

注意两局游戏中只要挑选的两个格子相同则视为同一局游戏，即 (X, Y) 等同于 (Y, X)。

第一行三个整数 N(1 \leq N \leq 1,000,000,000)，M(1 \leq M \leq 1,000,000,000)，P(0 \leq P \leq 100,000)。

接下来有 P 行，每行四个正整数，U_i，D_i (1<U_i \leq D_i<N)，L_i，R_i(1<L_i \leq R_i<M)，表示第 i 个矩形障碍物。

对于任意两个不同的矩形障碍物 i 和 j，都满足 D_i+1<U_j 或者 D_j+1<U_i，以及 R_i+1<L_j 或者 R_j+1<L_i。

只有一行一个正整数，即所有游戏的得分和模 1,000,000,007。

距离为 1 的有 8 种。

距离为 2 的有 8 种。

距离为 3 的有 8 种。

距离为 4 的有 4 种。

总共得分为 64 。

题解

分类讨论题。 终于见到阳间的分类讨论题了， md模拟赛里面的我就没对过 。

纪念第一个自己推出来的分类讨论， 虽然好像并没有什么难度

考虑先不考虑障碍物直接求每两两之间不考虑障碍物的最短路， 然后减去障碍物里面到外面的， 然后加上绕路的部分， 一点一点讨论。

不考虑障碍物的两两最短路之和

考虑对于横坐标和纵坐标分别枚举长度计算贡献得到 :

\sum_{i = 0}^{n - 1}m^2(n -i)i + \sum_{i = 0}^{m - 1}n^2(m - i)i = \frac{m^2(n^3 - n) + n^2(m^3 - m)}{6}

计算障碍物内外的最短路之和

只考虑当前一个障碍物， 当前障碍物为 (l_x, r_x, l_y, r_y) 分别表示横纵坐标。

先考虑横坐标的贡献， 记 S1(n) = \sum_{i = 1}^ni, S2 = \sum_{i = 1}^ni^2。

\sum_{i = l_x} ^{r_x}\sum_{j = 1}^n|j - i|m(r_y - l_y + 1)

令 m(r_y - l_y + 1) = C 最后乘上。

\sum_{i = l_x} ^{r_x}\sum_{j = 1}^n|j - i| = \sum_{i = l_x}^{r_x}\sum_{j = 1}^{i - 1} i - j + \sum_{i = l_x}^{r_x}\sum_{j = i +1}^{n} j - i = \sum_{i = l_x}^{r_x}i(i - 1) - \sum_{i = l_x} ^ {r_x} \frac{i(i - 1)}{2} - \sum_{i = l_x}^{r_x}(n - i)i + \sum_{i = l_x}^{r_x}\frac{(n - i)(i + 1 + n)}{2}

所以 x 轴的贡献是 ：

\frac{1}{2} \times C \times [(r_x - l_x + 1) \times (n^2 + n) + 2 (S2(r_x) - S2(l_x - 1)) - (2n + 2)(S1(r_x) - S1(l_x - 1))]

同理 y 轴的贡献就是 ：

\frac{1}{2} \times C \times [(r_y - l_y + 1) \times (m^2 + m) + 2 (S2(r_y) - S2(l_y - 1)) - (2m + 2)(S1(r_y) - S1(l_y - 1))]

计算障碍物到自己里面的最短路之和

就是一开始的计算全局不考虑障碍物的路径长度之和的做法。

计算当前障碍物里面到外面所有障碍物路径之和

有一个经典的操作。

同样把 x 轴和 y 轴分开考虑， 以 x 轴为例。

我们把矩形按照 x 轴排序， 维护之前的点数和 cnt 以及 x 坐标和 sum_x，记当前障碍的点数为 c， 当前的障碍的 x 坐标和是 s 。

把答案加上 cnt \times s - sum_x\times c 即可。

计算绕远路的部分

同样不妨考虑 x 轴的贡献， 设障碍物的宽为 l ， 左边有 L 个数， 右边有 R 个数， C = L \times R 。可以写出答案 ：

\sum_{i = 1}^l\sum_{j = 1}^l2\times \min(i, l - i + 1, j, l - j + 1)

不妨设 l 为偶数， t = \frac{l}{2} 。

\sum_{i = 1}^l\sum_{j = 1}^l2\times \min(i, l - i + 1, j, l - j + 1) =4\times \sum_{i = 1}^t\sum_{j = 1}^t2 \min (i, j) = 4\times ((2t + 1)\frac{t(t+ 1)}{2} - \frac{t(t + 1)(2t + 1)}{6})

考虑 l 是奇数的情况， 只要加一个 (l +1)^2\times \frac{1}{2} 即可， 具体只要观察一下会多出来哪些东西就好了。

code