Chaos Slover 补档计划 - 最大子矩阵

2015.12.01 18:15 Tue| 2 visits oi_2016| ChaosSlover补档计划| Text

JDFZOJ1237 VIJOS-P1055 奶牛浴场

水题就是要 1A。

我们将坏点按照 x 轴排序,枚举处在矩形的左边界上的坏点,然后向右扫一遍,再枚举处在右边界上的坏点,向左扫一遍,最后处理一下横贯整个平面的矩形就好了。时间复杂度 O(N^2)。(其实这道题的数据是及其弱的。)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

int l, w, n, ans;
pair<int, int> p[5005];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> l >> w >> n;
    for (int i = 1; i <= n; ++i)
        p[i].first = read(), p[i].second = read();
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        int d = 0, u = w;
        for (int j = i + 1; j <= n; ++j)
        {
            ans = max(ans, (p[j].first - p[i].first) * (u - d));
            if (p[j].first == p[i].first) continue;
            if (p[j].second >= p[i].second) u = min(u, p[j].second);
            if (p[j].second <= p[i].second) d = max(d, p[j].second);
        }
        ans = max(ans, (l - p[i].first) * (u - d));
    }
    for (int i = n; i >= 1; --i)
    {
        int d = 0, u = w;
        for (int j = i - 1; j >= 1; --j)
        {
            ans = max(ans, (p[i].first - p[j].first) * (u - d));
            if (p[j].first == p[i].first) continue;
            if (p[j].second >= p[i].second) u = min(u, p[j].second);
            if (p[j].second <= p[i].second) d = max(d, p[j].second);
        }
        ans = max(ans, (p[i].first) * (u - d));
    }
    for (int i = 1; i <= n; ++i)
        swap(p[i].first, p[i].second);
    sort(p + 1, p + n + 1);
    for (int i = 2; i <= n; ++i)
        ans = max(ans, l * (p[i].first - p[i - 1].first));
    ans = max(ans, l * p[1].first);
    ans = max(ans, l * (w - p[n].first));
    cout << ans << endl;
    return 0;
}

BZOJ3039 玉蟾宫

悬线法,时间复杂度 O(NM),只与矩形的面积有关。预处理出非坏点与它上方的第一个坏点确定出的上下边界所能拓展出的最大的矩形的左右边界。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n, m, ans;
int a[N][N], u[N][N], l[N][N], r[N][N];

int main()
{
    cin >> n >> m;
    char str[5];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%s", str), a[i][j] = str[0] == 'F' ? 1 : 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j]) u[i][j] = u[i - 1][j] + 1;
    for (int i = 1; i <= n; ++i)
        for (int last = 0, j = 1; j <= m; ++j)
            if (a[i][j]) l[i][j] = max(last + 1, l[i - 1][j]);
            else last = j;
    for (int i = 1; i <= m; ++i)
        r[0][i] = m;
    for (int i = 1; i <= n; ++i)
        for (int last = m + 1, j = m; j; --j)
            if (a[i][j]) r[i][j] = min(last - 1, r[i - 1][j]);
            else r[i][j] = m, last = j;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j])
                ans = max(ans, u[i][j] * (r[i][j] - l[i][j] + 1));
    cout << ans * 3 << endl;
    return 0;
}

BZOJ1057 [ZJOI2007]棋盘制作

既然格子是黑白相间的,那么我们就把 (i+j)&1 的格子反色,求最大子矩阵。然后全部反色再求一遍。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

#define N 2005
#define sqr(x) ((x) * (x))

int n, m, ans1, ans2;
int a[N][N], u[N][N], l[N][N], r[N][N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void getans()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j]) u[i][j] = u[i - 1][j] + 1;
    for (int i = 1; i <= n; ++i)
        for (int last = 0, j = 1; j <= m; ++j)
            if (a[i][j]) l[i][j] = max(last + 1, l[i - 1][j]);
            else last = j;
    for (int i = 1; i <= m; ++i)
        r[0][i] = m;
    for (int i = 1; i <= n; ++i)
        for (int last = m + 1, j = m; j; --j)
            if (a[i][j]) r[i][j] = min(last - 1, r[i - 1][j]);
            else r[i][j] = m, last = j;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j])
                ans1 = max(ans1, sqr(min(u[i][j], r[i][j] - l[i][j] + 1))),
                ans2 = max(ans2, u[i][j] * (r[i][j] - l[i][j] + 1));
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            a[i][j] = read() ^ ((i + j) & 1);
    getans();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            a[i][j] ^= 1;
    memset(u, 0, sizeof u);
    memset(l, 0, sizeof l);
    memset(r, 0, sizeof r);
    getans();
    cout << ans1 << '\n' << ans2 << endl;
    return 0;
}