国庆第三天

第二题

【解法一】

题意：给 
N
N 个学生，身高体重构成坐标 
(
A
i
,
B
i
)
∈
[
1
,
5000
]
2
(A 
i

,B 
i

)∈[1,5000] 
2
 。若选出一队，使任意两人的身高差和体重差都 ≤ 
K
K，等价于这批点全部落在同一条边长 
K
+
1
K+1 的轴对齐正方形里；求这种正方形能覆盖的最多点数。

想法：把平面离散成 5000×5000 网格，先统计每格点数 
G
[
x
]
[
y
]
G[x][y]。构造二维前缀和 
S
S，则任意窗口 
[
x
,
x
+
K
]
×
[
y
,
y
+
K
]
[x,x+K]×[y,y+K] 内点数

c
n
t
=
S
x
+
K
,
y
+
K
−
S
x
−
1
,
y
+
K
−
S
x
+
K
,
y
−
1
+
S
x
−
1
,
y
−
1
.
cnt=S 
x+K,y+K

−S 
x−1,y+K

−S 
x+K,y−1

+S 
x−1,y−1

.
遍历左下角 
(
x
,
y
)
(x,y)(范围 
1
 ⁣
∼
 ⁣
5000
−
K
1∼5000−K) 取最大 
c
n
t
cnt 即答案。
复杂度：前缀和与枚举各 
O
(
500
0
2
)
O(5000 
2
 )≈2.5×10⁷；内存 
500
1
2
5001 
2
 int≈25 MB。

// 081 - Friendly Group（★5）
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a); i <= (int)(b); ++i)
const int AA = 5000;
int G[AA + 2][AA + 2];
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, K;
  cin >> N >> K;
  for (int i = 0, a, b; i < N and cin >> a >> b; ++i)
    ++G[a][b];  // 先把 cnt 填进去，稍后原地转成二维前缀和
  REP(x, 1, AA) REP(y, 1, AA) {
    G[x][y] += G[x - 1][y] + G[x][y - 1] - G[x - 1][y - 1];
  }
  int ans = 0;
  REP(x1, 1, AA - K) REP(y1, 1, AA - K) {
    int x2 = x1 + K, y2 = y1 + K;
    ans =
        max(ans, G[x2][y2] - G[x1 - 1][y2] - G[x2][y1 - 1] + G[x1 - 1][y1 - 1]);
  }
  cout << ans << '\n';
  return 0;
}
// AC 100

【解法二】
分析：如果是只有身高或者体重一种属性，那么求长度
K
K的区间的最大元素数量可以用滑动窗口或者前缀和。现在是两个互不相关的属性，那么可以用二维前缀和。

#include <bits/stdc++.h>
using namespace std;
const int NN = 5e3;
int S[NN + 1][NN + 1];
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, K; cin >> N >> K;
  for (int i = 0, a, b; i < N; i++)
    cin >> a >> b, S[a][b]++;
  for (int i = 1; i <= NN; i++)
    for (int j = 1; j <= NN; j++)
      S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
  int ans = 0;
  for (int i = K + 1; i <= NN; i++)
    for (int j = K + 1; j <= NN; j++)
      ans = max(ans, S[i][j] - S[i - K - 1][j] - S[i][j - K - 1] + S[i - K - 1][j - K - 1]);
  cout << ans;
  return 0;
}