2113_掃雷.1.png

2113_掃雷.2.png

code

(x, y, r) 存一顆雷或者火箭信息， 讀入一個(gè)火箭，先找(x-r, x+r), (y-r, y+r)方形區(qū)域內(nèi)的雷。再確定哪些落在圓內(nèi)。圓內(nèi)的雷按同樣的方式先方形再圓形找被引爆的雷，直到?jīng)]有雷可以引爆。

數(shù)據(jù)較大，5*10^4, 需要優(yōu)化到O(nlogn)左右?？梢越o橫坐標(biāo)x,縱坐標(biāo)y排序，查找時(shí)用二分查找。并且 0 <= x, y <= 10^9, 下標(biāo)要做壓縮。

cpp

map<int, map<int, unordered_map<int, int>>> mp, 按<x, <y, <r, count>>> 存雷。 mp[x][y][r]：(x, y) 點(diǎn)爆炸半徑為 r 有幾顆雷。

• res 存結(jié)果，可以引爆幾顆
• 讀入掃雷火箭 x, y, r。放入隊(duì)列q中。
• 每次在隊(duì)列取出第一個(gè)(x, y, r), 找可以被引爆的其他雷
• 找在(x-r, x+r), (y-r,y+r) 方形區(qū)域內(nèi)的雷，剪枝操作。
  • xiter = mp.lower_bound(x - r), 二分查找 第一個(gè)不小于 x-r 的橫坐標(biāo)
  • xed = mp.upper_bound(x + r), 二分查找 第一個(gè)大于 x+r 的橫坐標(biāo)
  • 橫坐標(biāo)范圍: [xiter->first, xed->first)
• 橫坐標(biāo)確定后找滿足條件的縱坐標(biāo)
  • yiter = xiter->second.lower_bound(y - r)
  • yed = xiter->second.upper_bound(y + r)
  • xiter->second 也就是 mp[x]
  • 縱坐標(biāo)范圍: [yiter->first, yed->first)
• 判斷炸彈(xiter->first, yiter->first)是否在引爆范圍，如果在：
  • yiter->second也就是mp[x][y], 得到key為半徑r, value為炸彈個(gè)數(shù)的unordered_map<int, int>
  • 遍歷以該點(diǎn)為圓心的炸彈for(const auto& bm:yiter->second)
  • res += bm->second也就是當(dāng)前雷的個(gè)數(shù)，
  • 將雷(xiter->first, yiter->first, bm->first)放入隊(duì)列
  • 刪除該點(diǎn)的雷：
    • 先清空縱坐標(biāo), map[x].erase(y)，yiter = xiter->second.erase(yiter)。
    • 如果mp[x]全處理完后也為空，mp.erase(x), xiter = mp.erase(xiter);
• 重復(fù)此過程，直到隊(duì)列為空。 讀入下一個(gè)掃雷火箭，直到所有火箭處理完。

#include <bits/stdc++.h>
using namespace std;

const int fff = []() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return 0; }();

bool is_in_scope(long long x1, long long y1, long long r, long long x2, long long y2) {
    return (x1 - x2) * (x1 - x2) <= r * r - (y1 - y2) * (y1 - y2);
}

int main() {
    int n, m;
    cin >> n >> m;
    map<int, map<int, unordered_map<int, int>>> mp;
    for (int i = 0; i < n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        mp[x][y][r]++;
    }
    int res = 0;
    for (int i = 0; i < m; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        queue<tuple<int, int, int>> q;
        q.emplace(x, y, r);
        while (!q.empty()) {
            x = get<0>(q.front());
            y = get<1>(q.front());
            r = get<2>(q.front());
            q.pop();
            for (auto xiter = mp.lower_bound(x - r), xed = mp.upper_bound(x + r); xiter != xed;) {
                for (auto yiter = xiter->second.lower_bound(y - r), yed = xiter->second.upper_bound(y + r); yiter != yed;) {
                    if (is_in_scope(x, y, r, xiter->first, yiter->first)) {
                        for(const auto& bm:yiter->second) {
                            res += bm.second;
                            q.emplace(xiter->first, yiter->first, bm.first);
                        }
                        yiter = xiter->second.erase(yiter);
                    } else {
                        yiter++;
                    }
                }
                if(xiter->second.empty()) {
                    xiter = mp.erase(xiter);
                } else {
                    xiter++;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

c

• struct BM mp[50003] 存炸彈信息，mp[i].key = mp[i].x * 10^9 + mp[i].y 這樣炸彈坐標(biāo)點(diǎn)就可以一維表示
• bm_sort 存炸彈下標(biāo)，根據(jù) mp[bm_sort[i]].key 排序
• 隊(duì)列q用數(shù)組和循環(huán)下標(biāo)模擬，存炸彈在mp中的下標(biāo), bg隊(duì)列頭， ed 隊(duì)列尾， 添加q[ed++]=?; ed %= 50003, 取q[bg], 刪bg = (bg + 1) % 50003, bg == ed時(shí)隊(duì)列空
• 每次讀入炸彈數(shù)據(jù)放到mp[n], 對(duì)列起始bg=0, ed=1, q[0]=n
• 隊(duì)列中每個(gè)炸彈 mp[q[bg]]
  • 依然找方形區(qū)域內(nèi)的點(diǎn)，key最小點(diǎn):(x-r, y-r), key最大點(diǎn):(x+r, y+r)。所以只要找key在這兩個(gè)范圍內(nèi)的即可。
  • 寫二分查找，在bm_sort中找 min_k <= mp[bm_sort[j]].key, mp[bm_sort[_l]] <= max_k的最邊緣值
  • 遍歷bm_sort j ~ _l的點(diǎn)，如果點(diǎn)沒有訪問過used[bm_sort[j]] == 0 并且在半徑范圍內(nèi)，標(biāo)記為已訪問，下標(biāo)放入隊(duì)列

#include <stdio.h>
#include <stdlib.h>
struct BM {
    int x, y, r;
    long long key;
} mp[50003];

long long key(int x, int y) {
    return 1000000000LL * x + y;
}

int cmp(const void* a, const void* b) {
    long long k1 = mp[*(int*)a].key, k2 = mp[*(int*)b].key;
    return k1 == k2 ? 0 : (k1 < k2 ? -1 : 1);
}

int max(int a, int b) {
    return a < b ? b : a;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int bm_sort[50003];
    int used[50003] = {0};
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &mp[i].x, &mp[i].y, &mp[i].r);
        mp[i].key = key(mp[i].x, mp[i].y);
        bm_sort[i] = i;
    }
    qsort(bm_sort, n, sizeof(int), cmp);
    int q[50003], res = 0;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &mp[n].x, &mp[n].y, &mp[n].r);
        q[0] = n;
        int bg = 0, ed = 1;
        while (bg != ed) {
            int x = mp[q[bg]].x, y = mp[q[bg]].y, r = mp[q[bg]].r;
            bg = (bg + 1) % 50003;

            long long min_k = key(max(0, x - r), max(0, y - r));
            long long max_k = key(x + r, y + r);
            int _l = 0, _r = n - 1;
            while (_l < _r) {
                int mid = (_l + _r) / 2;
                if (mp[bm_sort[mid]].key < min_k) {
                    _l = mid + 1;
                } else {
                    _r = mid;
                }
            }
            int j = _l;
            _l = 0, _r = n - 1;
            while (_l < _r) {
                int mid = (_l + _r) / 2;
                if (mp[bm_sort[mid]].key < max_k) {
                    _l = mid + 1;
                } else {
                    _r = mid;
                }
            }
            for (;j <= _l && j < n; j++) {
                int tmp_x = mp[bm_sort[j]].x, tmp_y = mp[bm_sort[j]].y;
                if (!used[bm_sort[j]] && 1LL * (x - tmp_x) * (x - tmp_x) <= 1LL * r * r - 1LL * (y - tmp_y) * (y - tmp_y)) {
                    used[bm_sort[j]] = 1;
                    q[ed++] = bm_sort[j];
                    ed %= 50003;
                    res++;
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}