ZOJ 3597

題意是說有n把槍，有m個靶子，每把槍只有一發子彈（也就是說一把槍最多只能打一個靶子）， 告訴你第 i 把槍可以打到第j個靶，?現在等概率的出現一個連續的P把槍，在知道這P把槍之后，你被允許選擇一個連續的Q個靶子，使得這P把槍所打到的靶子的數目最多，問打到的靶子數目的期望值是多少。

這題通過簡單的轉化就可以轉換成為另一個模型：

如果第a把槍可以打到第b個靶子，那么將其視為二位平面上的一個點(b, a)， 問題轉化為一個Q * P的矩形最多可以覆蓋多少個點。只是有一點需要注意的就是同一把槍只能打到一個靶子，所以在a相等的情況下最多只能覆蓋一個b。

?

至于如何求矩形覆蓋點的個數，我這也是第一次寫，所以查閱了有關資料。

方法是將矩形的右界作為參考點，找出參考點在哪一個區間（線段）內矩形都可以覆蓋到這個點，這樣每一個點就對應y相等的一段線段，原題就轉化成為了高度y小于P的區間內某一個位置x上的覆蓋次數的最大值，可以用線段樹的離線操作（掃描線）來完成。

?

1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define inf (-((LL)1<<40)) 17 #define lson k<<1, L, (L + R)>>1 18 #define rson k<<1|1, ((L + R)>>1) + 1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FIN freopen("in.txt", "r", stdin) 23 #define FOUT freopen("out.txt", "w", stdout) 24 #define rep(i, a, b) for(int i = a; i <= b; i ++) 25 26 template<class T> T CMP_MIN(T a, T b) { return a < b; } 27 template<class T> T CMP_MAX(T a, T b) { return a > b; } 28 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 29 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } 32 33 //typedef __int64 LL; 34 typedef long long LL; 35 const int MAXN = 51000; 36 const int MAXM = 110000; 37 const double eps = 1e-4; 38 //LL MOD = 987654321; 39 40 #define OK(i) (i > 0 && p[i - 1].y == p[i].y && p[i].x <= p[i - 1].x + Q - 1) 41 42 int T, N, M, P, Q, K; 43 struct Point { 44 int x, y; 45 bool operator < (const Point &A) const { 46 return y == A.y ? x < A.x : y < A.y; 47 } 48 }p[MAXM]; 49 50 struct SegTree { 51 LL ma[MAXN<<2], add[MAXN<<2]; 52 53 void build(int k, int L, int R) { 54 ma[k] = add[k] = 0; 55 if(L == R) return ; 56 build(lson); build(rson); 57 } 58 59 void pushDown(int k) { 60 ma[k<<1] += add[k]; add[k<<1] += add[k]; 61 ma[k<<1|1] += add[k]; add[k<<1|1] += add[k]; 62 add[k] = 0; 63 } 64 65 void update(int k, int L, int R, int l, int r, int val) { 66 if(R < l || L > r) return ; 67 if(l <= L && R <= r) { ma[k] += val; add[k] += val; return ; } 68 pushDown(k); 69 update(lson, l, r, val); 70 update(rson, l, r, val); 71 ma[k] = max(ma[k<<1], ma[k<<1|1]); 72 } 73 74 LL query(int k, int L, int R, int l, int r) { 75 if(R < l || L > r) return 0; 76 if(l <= L && R <= r) return ma[k]; 77 pushDown(k); 78 return max(query(lson, l, r), query(rson, l, r)); 79 } 80 81 }segTree; 82 83 int main() 84 { 85 //FIN; 86 while(~scanf("%d", &T)) while(T--) 87 { 88 scanf("%d %d %d %d %d", &N, &M, &P, &Q, &K); 89 rep (i, 0, K - 1) scanf("%d %d", &p[i].y, &p[i].x); 90 sort(p, p + K); 91 92 segTree.build(1, 1, M); 93 LL ans = 0, fr = 0, re = 0; 94 rep (i, P, N) { 95 while(fr < K && p[fr].y <= i) { 96 int st = OK(fr) ? p[fr-1].x + Q : p[fr].x; 97 int ed = min(p[fr].x + Q - 1, M); 98 segTree.update(1, 1, M, st, ed, 1); 99 fr ++; 100 } 101 while(i - p[re].y >= P) { 102 int st = OK(re) ? p[re-1].x + Q : p[re].x; 103 int ed = min(p[re].x + Q - 1, M); 104 segTree.update(1, 1, M, st, ed, -1); 105 re ++; 106 } 107 ans += segTree.query(1, 1, M, 1, M); 108 } 109 printf("%.2lf\n", (double)ans / (N - P + 1)); 110 } 111 return 0; 112 }

?

轉載于:https://www.cnblogs.com/gj-Acit/p/4493091.html

總結

以上是生活随笔為你收集整理的ZOJ 3597 Hit the Target! （线段树扫描线 -- 矩形所能覆盖的最多的点数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。