题解 P7149 【[USACO20DEC] Rectangular Pasture S】

我来一发纯暴力的吧，不用什么树状数组，也不用（手动）离散化和前缀和，直接暴力肝就好。 ### 1. 思路 显然，每行、每列都至多只有一个点。对行坐标排序，滤掉没有牛的行（这实际上相当于离散化）。设 $a[i]$ 代表第 $i$ 行的那头牛所在的列坐标。 考虑下侧木板在第 $i$ 行，上侧木板在第 $j$ 行的情况。**为了避免相同情况重复计算（即围栏形状不同，但圈住的牛相同），第 $i$ 行的牛和第 $j$ 行的牛必须被圈住**。 - 如果第 $j$ 行的牛在第 $i$ 行的牛左边（即 $a[i] > a[j]$）： - 任何一头在 **第 $i$ 行与第 $j$ 行之间，在第 $j$ 行的牛左边** 的牛，即满足 **$i<k<j,a[k]<a[j]$ 的 $k$**，都可以作为左侧围栏所在位置的选项（如果不满足此条件，则第 $j$ 行的牛无法被圈住）；当然，第 $j$ 行的牛本身（$a[j]$）也可以作为左侧围栏所在位置的选项。 - 任何一头在 **第 $i$ 行与第 $j$ 行之间，在第 $i$ 行的牛右边** 的牛，即满足 **$i<k<j,a[k]>a[i]$ 的 $k$**，都可以作为右侧围栏所在位置的选项（如果不满足此条件，则第 $i$ 行的牛无法被圈住）；当然，第 $i$ 行的牛本身（$a[i]$）也可以作为右侧围栏所在位置的选项。 - 第 $j$ 行的牛在第 $i$ 行的牛右边（即 $a[i] < a[j]$）的情况同理。 所以，下侧木板在第 $i$ 行，上侧木板在第 $j$ 行的所有可能，即为 **左侧围栏选项总数** $\times$ **右侧围栏选项总数**。 我们只需在枚举 $i,j$ 的过程中，维护： - 对于第 $i$ 行的牛，在第 $i$ 行与第 $j$ 行之间，有多少头牛在它的左边/右边； - 对于第 $j$ 行的牛，有第 $i$ 行与第 $j$ 行之间，有多少头牛在它的左边/右边； 顺带累加答案，即可轻松完成此题。 时间复杂度为 $O(N^2)$。 ### 2. 代码实现 ```cpp #include <iostream> #include <algorithm> using namespace std; typedef long long ll; #define MAXN 2505 ll N; // 每头牛的行/列坐标 pair<ll, ll> x[MAXN]; // 先算上空集 ll ans = 1; // l[j]代表【第j行的牛】与【当前第i行的牛】之间，有多少头牛在【第j行的牛】左边 // r[j]同理 ll l[MAXN], r[MAXN]; int main() { cin >> N; for (int i = 0; i < N; i++) cin >> x[i].first >> x[i].second; // 按行坐标排序 sort(x, x + N); // 枚举i for (ll i = 0; i < N; i++) { ans++; // lt代表【第i行的牛】与【当前第j行的牛】之间，有多少头牛在【第i行的牛】左边 // rt同理 ll lt = 0, rt = 0; for (ll j = i - 1; j >= 0; j--) { // 根据【第i行的牛】与【第j行的牛】的相对位置，累加答案，更新计数 if (x[i].second > x[j].second) { ans += (rt + 1) * (l[j] + 1); r[j]++; lt++; } else { ans += (lt + 1) * (r[j] + 1); l[j]++; rt++; } } } cout << ans << endl; return 0; } ```