https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=1696
今天还做回以前做过的一道题。
这题主要是离散化，然后将点的个数转化为前缀和。
View Code
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <iostream>
5 #include <vector>
6 #include <map>
7
8 using namespace std;
9 typedef vector<int> VI;
10
11 #define REP(i, n) for (int i = 0; i < (n); i++)
12 #define REP_1(i, n) for (int i = 1; i <= (n); i++)
13 #define INC(i, a, b) for (int i = (a); i <= (b); i++)
14 #define DEC(i, a, b) for (int i = (a); i >= (b); i--)
15 #define PB push_back
16 #define _clr(x) memset(x, 0, sizeof(x))
17 #define SZ(x) ((int) (x).size())
18 #define ALL(x) (x).begin(), (x).end()
19
20 const int N = 111;
21 VI X, Y;
22 map<int, int> NX, NY;
23 int x[N], y[N];
24 int mat[N][N], preSum[N][N];
25
26 void input(int n) {
27 NX.clear();
28 NY.clear();
29 X.clear();
30 Y.clear();
31 REP(i, n) {
32 cin >> x[i] >> y[i];
33 X.PB(x[i]);
34 Y.PB(y[i]);
35 }
36 sort(ALL(X));
37 sort(ALL(Y));
38 int t = unique(ALL(X)) - X.begin();
39 while (SZ(X) > t) X.pop_back();
40 REP(i, t) {
41 NX[X[i]] = i + 1;
42 }
43 t = unique(ALL(Y)) - Y.begin();
44 while (SZ(Y) > t) Y.pop_back();
45 REP(i, t) {
46 NY[Y[i]] = i + 1;
47 }
48 _clr(mat);
49 REP(i, n) {
50 mat[NX[x[i]]][NY[y[i]]] = 1;
51 }
52 // REP_1(i, SZ(X)) {
53 // REP_1(j, SZ(Y)) {
54 // cout << mat[i][j];
55 // }
56 // cout << endl;
57 // }
58 }
59
60 int work() {
61 int nx = SZ(X), ny = SZ(Y), mx = 0;
62 if (nx <= 1 || ny <= 1) return max(SZ(X), SZ(Y));
63 REP_1(i, nx) {
64 REP_1(j, ny) {
65 preSum[i][j] = preSum[i - 1][j] + mat[i][j];
66 }
67 }
68 // REP_1(i, nx) {
69 // REP_1(j, ny) {
70 // cout << preSum[i][j];
71 // }
72 // cout << endl;
73 // }
74 int sum, mn;
75 REP_1(x1, nx) {
76 INC(x2, x1 + 1, nx) {
77 sum = 0;
78 mn = 999999;
79 REP_1(y, ny) {
80 mx = max(mx, sum + preSum[x2][y] - preSum[x1 - 1][y] - mn);
81 mn = min(mn, sum - preSum[x2 - 1][y] + preSum[x1][y]);
82 sum += mat[x1][y] + mat[x2][y];
83 }
84 }
85 }
86 return mx;
87 }
88
89 int main() {
90 // freopen("in", "r", stdin);
91 int n, cas = 1;
92 while (cin >> n && n) {
93 input(n);
94 cout << "Case " << cas++ << ": " << work() << endl;
95 }
96 return 0;
97 } ——written by Lyon