牛客第六場 H-Hopping Rabbit

給出平面上的n個矩形，一只兔子從$(x_0+0.5,y_0+0.5)$出發(fā)，每一次可以平行于x軸或y軸跳躍d的距離，求出一個初始位置使得不管怎么跳都不會跳入到矩形中。
數(shù)據(jù)范圍n,d<=1e5,平面坐標(biāo)在-1e9到1e9當(dāng)中

容易想到轉(zhuǎn)化，變?yōu)榱诉@樣的問題：在一個d*d的矩陣當(dāng)中進(jìn)行矩形覆蓋，求出最后有沒有點沒有被覆蓋到，如果存在則求出它。

但是這個問題卡住了，最后沒有想出來做法。后面聽說了線段樹的解決方法，覺得這類型的方法值得去研究一下。

對于每個矩形，取出其上邊和下邊，然后從下往上遍歷，遇到一個下邊，便在線段樹的(x1, x2)區(qū)間進(jìn)行+1；遇到一個上邊，邊-1。在操作之后，如果線段樹的最小值的0的話，那么說明這一行上有一個空格，這里就可以作為初始位置。

這個題有點碼，不過都是比較基礎(chǔ)的，還算是好寫。

#include <bits/stdc++.h> using namespace std;const int N = 1e5 + 10, inf = 1e9; int n, k, tot = 0;struct trap {int x1, y1, x2, y2; }; trap a[N << 2];struct line {int y, l, r;bool flag; }; line b[N << 3];trap build(int x1, int y1, int x2, int y2) {trap temp;temp.x1 = x1;temp.y1 = y1;temp.x2 = x2;temp.y2 = y2;return temp; }line buildline(int y, int l, int r, bool flag) {line temp;temp.y = y;temp.l = l;temp.r = r;temp.flag = flag;return temp; }inline int mo(long long x) {x = (x + (long long)k * inf) % k;if (x == 0) x = k;return x; }struct tree {int l, r, mn, lazy; }; tree t[N << 2];void buildtree(int l, int r, int x) {t[x].l = l; t[x].r = r;t[x].mn = t[x].lazy = 0;if (l == r) return;int mid = (l + r) >> 1;buildtree(l, mid, x << 1);buildtree(mid + 1, r, x << 1 | 1);return; }void pushdown(int x) {t[x << 1].mn += t[x].lazy;t[x << 1].lazy += t[x].lazy;t[x << 1 | 1].mn += t[x].lazy;t[x << 1 | 1].lazy += t[x].lazy;t[x].lazy = 0; }int query(int l, int r, int x) {if (l <= t[x].l && t[x].r <= r)return t[x].mn;if (l > t[x].r || t[x].l > r)return inf;if (t[x].lazy != 0)pushdown(x);return min(query(l, r, x << 1), query(l, r, x << 1 | 1)); }void change(int l, int r, int x, int d) {if (l <= t[x].l && t[x].r <= r){t[x].mn += d;t[x].lazy += d;return;}if (l > t[x].r || t[x].l > r)return;if (t[x].lazy != 0)pushdown(x);change(l, r, x << 1, d);change(l, r, x << 1 | 1, d);t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn); }bool cmp(const line &a, const line &b) {return a.y < b.y; }int main() {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while (T --){bool flag = false;cin >> n >> k;buildtree(1, k, 1);for (int i = 1; i <= n; i ++){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;if (y2 - y1 >= k && x2 - x1 >= k)flag = true;else{if (y2 - y1 >= k){x1 = mo(x1); x2 = mo(x2 - 1);if (x1 <= x2)a[++ tot] = build(x1, 1, x2, k);else{a[++ tot] = build(x1, 1, k, k);a[++ tot] = build(1, 1, x2, k);}}else if (x2 - x1 >= k){y1 = mo(y1); y2 = mo(y2 - 1);if (y1 <= y2)a[++ tot] = build(1, y1, k, y2);else{a[++ tot] = build(1, y1, k, k);a[++ tot] = build(1, 1, k, y2);}}else{x1 = mo(x1); x2 = mo(x2 - 1); y1 = mo(y1); y2 = mo(y2 - 1);if (x1 <= x2){if (y1 <= y2)a[++ tot] = build(x1, y1, x2, y2);else{a[++ tot] = build(x1, y1, x2, k);a[++ tot] = build(x1, 1, x2, y2);}}else{if (y1 <= y2){a[++ tot] = build(x1, y1, k, y2);a[++ tot] = build(1, y1, x2, y2);}else{a[++ tot] = build(x1, y1, k, k);a[++ tot] = build(1, y1, x2, k);a[++ tot] = build(x1, 1, k, y2);a[++ tot] = build(1, 1, x2, y2);}}}}}if (flag){cout << "NO";return 0;}for (int i = 1; i <= tot; i ++){b[i * 2 - 1] = buildline(a[i].y1, a[i].x1, a[i].x2, 1);b[i * 2] = buildline(a[i].y2 + 1, a[i].x1, a[i].x2, 0);}sort (b + 1, b + 2 * tot + 1, cmp);int p = 1;for (int i = 1; i <= k; i ++){while (b[p].y == i){if (b[p].flag)change(b[p].l, b[p].r, 1, 1);elsechange(b[p].l, b[p].r, 1, -1);p ++;}int mn = t[1].mn;if (mn == 0){for (int j = 1; j <= k; j ++){if (query(j, j, 1) == 0){cout << "YES\n";cout << j << " " << i;return 0;}}}}cout << "NO";}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客第六场 H-Hopping Rabbit的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。