Celery's Blog

0%

挑战程序设计竞赛-day12

发表于 Valine：

折半枚举（双向搜索）

POJ 2785：4 Values whose Sum is 0

1580266159037

从四个数列中选择的话总共有n4n^4种情况，所以全都判断一遍是不可行的。

所以对半分成AB和CD考虑。从2个数列中选择的话只有n2n^2种组合，就可以快速解决了。从2个数列中选择的话只有n2n^2种组合，所以可以进行枚举。先从A,B中取出a, b后，为了使总和为0则需要从C,D中取出c+d=−(a+b)c + d = -(a + b)。因此先将C，D中取数字的n2n^2种方法全部枚举出来，将这些和排好序，这样就可以运用二分搜索了。这个算法的复杂度是O(n2logn)O(n^2logn)

有时候，问题的规模比较大，无法枚举所有元素的组合，但能够枚举一半元素的组合。此时，将问题拆成两半后分别枚举，再合并他们的结果这一方法往往非常有效。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 5010;
// 输入
int n;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int CD[MAXN * MAXN];

void solve() {
    // 枚举从C和D中取出数字的所有方法
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            CD[i * n + j] = C[i] + D[j];
        }
    }
    sort(CD, CD + n * n);
    long long res = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            int cd = -(A[i] + B[j]);
            // upper_bound是查找第一个大于等于自己的数的位置，lower_bound是查找第一个大于自己的数的位置
            res += upper_bound(CD, CD + n * n, cd) - lower_bound(CD, CD + n * n, cd);
        }
    }
    printf("%lld\n", res);
}


int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
    }
    solve();
}

坐标离散化

1580266867195

本来这道题可以用深度优先搜索的方法来求解被分割出的区域个数。但这个问题中，w和h最大为1000000，所以没办法创建w×hw \times h 的数组，因此，利用坐标离散化来解决。

1580266902031

如上图，将前后没有变化的行列消除后并不会影响区域的个数。

数组里只需要存储有直线的行列以及其前后的行列就足够了，这样的话大小最多6n×6n6n \times 6n就足够了。

因此就可以创建出数组并利用广度搜索（深度搜索可能会爆栈）就能求出区域的个数了。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
// MAXN表示最多输入的直线的条数
const int MAXN = 100;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
// 输入
int W, H, N;
int X1[MAXN], X2[MAXN], Y1[MAXN], Y2[MAXN];

// 填充用
bool fld[MAXN * 6][MAXN * 6];

// 对 x1, x2进行坐标离散化，并返回离散化之后的宽度
int compress(int *x1, int *x2, int w) {
    vector<int> xs;
    for(int i = 0; i < N; i++) {
        for(int d = -1; d <= 1; d++) {
            int tx1 = x1[i] + d, tx2 = x2[i] + d;
            if(1 <= tx1 && tx1 <= W) {
                xs.push_back(tx1);
            }
            if(1 <= tx2 && tx2 <= W) {
                xs.push_back(tx2);
            }
        }
    }
    sort(xs.begin(), xs.end());
    // unique操作之后，会将不一样的数字全部放在vector的头部(假设共有n个)，然后返回一个iterator，指向n+2的位置
    // 再erase之后，即将重复的数字全部去除
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for(int i = 0; i < N; i++) {
        // 等式右侧表示在xs中查找与x1[i]值相同的元素的下标，即更新之后的下标 
        x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
        x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
    }
    return xs.size();
}

void solve() {
    // 坐标离散化
    W = compress(X1, X2, W);
    H = compress(Y1, Y2, H);

    // 填充有直线的部分
    memset(fld, 0, sizeof(fld));
    for(int i = 0; i < N; i++) {
        for(int y = Y1[i]; y <= Y2[i]; y++) {
            for(int x = X1[i]; x <= X2[i]; x++) {
                fld[y][x] = true;
            }
        }
    }

    // 求区域的个数
    int ans = 0;
    for(int y = 0; y < H; y++) {
        for(int x = 0; x < W; x++) {
            if(fld[y][x]) continue;
            ans++;

            // 宽度优先搜索
            queue<pair<int, int> > que;
            que.push(make_pair(x, y));
            while(!que.empty()) {
                int sx = que.front().first, sy = que.front().second;
                que.pop();
                for(int i = 0; i < 4; i++) {
                    int tx = sx + dx[i], ty = sy + dy[i];
                    if(tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
                    if(fld[ty][tx]) continue;
                    que.push(make_pair(tx, ty));
                    fld[ty][tx] = true;
                }
            }
        }
    }
    printf("%d\n", ans);
}

Ps：这里再提一下关于lower_bound和upper_bound的用法

lower_bound()和upper_bound()都在利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中：

lower_bound(begin, end, num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin，得到数字在数组中的下标。

upper_bound(begin, end, num):从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。

在从大到小的排序数组中，重载upper_bound()和lower_bound()

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。