官方题解（中文整理）

基于 Bing-Dong Liu 的官方题解整理。

胜负条件化简

设奶牛 \(i\) 与奶牛 \(j\) 对局。\(i\) 平均意义下战胜 \(j\)，当且仅当：

\(h_i s_j + p_i h_j + s_i p_j > h_j s_i + p_j h_i + s_j p_i\)

这就是本题最核心的不等式。

我们要统计的是“好三元组”数量：三头奶牛两两之间的胜负关系形成一个有向环。

子任务 1：暴力

当 \(N\) 很小时，直接枚举所有 \(\binom{N}{3}\) 个三元组并判断即可。

子任务 2：\(O(N^2)\)

先暂时假设不存在平局，也就是任意两头奶牛总有一方平均意义下战胜另一方。

先数坏三元组

对于一个三元组来说：

• 如果是好三元组，那么三头奶牛各赢一次
• 如果不是好三元组，那么一定存在一头奶牛战胜另外两头

记 \(\mathrm{win}_i\) 表示奶牛 \(i\) 能战胜多少头别的奶牛。那么把 \(i\) 当成“战胜另外两头”的那头奶牛时，坏三元组数量就是：

\(\binom{\mathrm{win}_i}{2}\)

所以在无平局的前提下，答案为：

\(\binom{N}{3} - \sum_{i=1}^N \binom{\mathrm{win}_i}{2}\)

如何处理平局

定义：

\(x_i = h_i - s_i,\qquad y_i = p_i - s_i\)

如果 \(x_i = y_i = 0\)，说明 \(h_i = p_i = s_i\)，这头奶牛会与所有奶牛平局，因此它不可能出现在好三元组中，可以直接忽略。

两头奶牛 \(i,j\) 平局，当且仅当：

\((h_i-s_i)(p_j-s_j) = (h_j-s_j)(p_i-s_i)\)

也就是：

\(x_i y_j = x_j y_i\)

这说明“平局”具有传递性：方向相同的点会形成若干个平局连通块。于是可以先把所有互相平局的奶牛合并成若干个组件。

接下来分三步：

1. 用一个小型 DP 统计“从这些平局组件中选出 3 头、且任意两头都不平局”的三元组数量。
2. 仍像无平局时那样，减去 \(\sum \binom{\mathrm{win}_i}{2}\)。
3. 上一步会多减去一类三元组：奶牛 \(i\) 同时战胜 \(j,k\)，但 \(j,k\) 彼此平局。把这类三元组再加回来即可。

由于需要判断每一对奶牛的胜负或平局关系，复杂度为 \(O(N^2)\)。

正解：几何化简 + 极角排序

完整数据下需要做到 \(O(N \log N)\)。

把三维概率化成二维向量

观察原不等式可知：如果给一头奶牛的 \(h,p,s\) 同时加上同一个常数，胜负关系不会改变。因此可以把每头奶牛对应成二维向量：

\((x_i,y_i) = (h_i-s_i,\ p_i-s_i)\)

于是奶牛 \(i\) 战胜奶牛 \(j\) 的条件就变成：

\(x_i y_j - y_i x_j > 0\)

这正是二维叉积大于 \(0\)。

几何上，这表示向量 \(\langle x_j,y_j \rangle\) 位于向量 \(\langle x_i,y_i \rangle\) 的逆时针半平面内。

好三元组的几何意义

把所有非零向量按极角排序。

若没有平局，则一个三元组是坏三元组，当且仅当这三个向量全部落在某个开区间长度小于 \(180^\circ\) 的半圆内；反之，它就是好三元组。

因此可以转化为一个圆上计数问题。

双指针统计

设所有向量按极角排好序后首尾相接。对每个起点向量，用双指针维护从它出发、张角严格小于 \(180^\circ\) 的最大区间。

这样就能在线性时间内求出每个起点向量“能战胜多少个后面的向量”，并据此统计所有坏三元组数量。

还要处理平局

方向完全相同的向量彼此平局，因此需要先把极角相同的向量压成一个组，记录该组大小。

随后在圆上做双指针时：

• 组内不能同时取多个点作为好三元组中的不同顶点
• 与当前方向正好相反的边界位置也需要额外处理，因为叉积为 \(0\) 表示平局而不是胜负

这些边界修正都可以在双指针过程中顺带完成。

复杂度

排序复杂度为 \(O(N \log N)\)，双指针扫描是线性的，因此总复杂度为：

\(O(N \log N)\)

可以通过全部数据。