MX-S3 T4 官方题解

vegetable_king · 2024-08-17 22:06:03 · 题解

出题人题解。

首先考虑一个最基本的策略：

假设我们要 check p_k \ge X 是否合法。

那么我们只需要对于所有的 1 \le l \le m, l \ne k，分别令 p_k = X, p_l = 1 - X，其他的 p 为 0，都 check 一次即可。

证明是显然的，如果我们要在 p_k = X 的情况下分配其他的 p 使得第 i 个学生的加权总分超过第 j 个学生的加权总分 (a_{i, k} < a_{j, k})，那么将剩下的 1 - X 集中在 a_{i, l} - a_{j, l} 最大的第 l 个学科上一定不劣。

于是根据上述策略，我们得到了一个单组数据 O(m^2 n \log n \log v) 并且需要二分的做法，但是答案需要输出有理数，无法二分。

考虑不排序而是直接暴力枚举 i, j, k, l (a_{i, k} < a_{j, k}, a_{i, l} > a_{j, l})，则我们得到一个不等式：

解得：

于是题意就相当于对于每个 k，求上式的最大值，这个东西显然可以暴力 O(n^2 m^2) 做。

n \le 100

发现需要最大化的分式是 \frac p{p + q} 形式的，所以我们枚举 i, j, l 确定 p = a_{i, l} - a_{j, l} 并枚举 k 最小化 q = a_{j, k} - a_{i, k}。

因为 q 只与 i, j, k 相关，并且 k \ne l，所以我们可以对每一对 i, j 枚举 k 来 O(n^2m) 预处理出最小次小的 q，即可做到 O(1) 查询 q。

于是我们得到了一个单组数据时间复杂度为 O(n^2m) 的做法。

m \le 100

实际上，如果我们先枚举了 k, l，我们就不需要对所有的 i, j 去判断了。根据比较的传递性，如果存在 o 满足 a_{i, k} < a_{o, k} < a_{j, k}，则无需考虑 i, j 这一对是否满足要求。于是我们对于某个 (k, l)，将 a_{i, k} 相等的 i 划为一类，则我们只需要考虑数值相邻的两个类。

考虑固定类别之后，a_{i, k}, a_{j, k} 都被固定了，则 \frac p{p + q} 中的 q = a_{j, k} - a_{i, k} 已经被确定，则我们为了让分式最大，应该最大化 p = a_{i, l} - a_{j, l}，而 p 是在两个类中各选取一个数作差，a_{i, l} 选最大，a_{j, l} 选最小即可。

每个点只会被一个类包含，对于每个类暴力扫一遍求出最大值与最小值，时间复杂度是 O(n) 的。

于是我们又得到了一个单组数据时间复杂度为 O(nm^2) 的做法。

结合一下

考虑数据分治，n \le m 时跑 O(n^2m)，n > m 时跑 O(nm^2)，则单组数据时间复杂度为 O(nm\min(n, m))。

设 S = nm，则 \min(n, m) \le \sqrt S。所以单组数据时间复杂度为 O(S \sqrt S)，可以通过本题。

另外，涉及到的分数分子和分母显然都不会超过 2v = 2 \times 10^8，不是 998244353 的倍数，必定存在逆元。

关于分数比大小，因为分子分母都在 int 范围内，所以可以写一个 frac 类，比大小的时候开 long long 交叉相乘就不会有精度损失。

code