题意是说有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
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 = i &= i ++)
26 template&class T& T CMP_MIN(T a, T b) { return a & }
27 template&class T& T CMP_MAX(T a, T b) { return a & }
28 template&class T& T MAX(T a, T b) { return a & b ? a : }
29 template&class T& T MIN(T a, T b) { return a & b ? a : }
30 template&class T& T GCD(T a, T b) { return b ? GCD(b, a%b) : }
31 template&class T& T LCM(T a, T b) { return a / GCD(a,b) *
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 = ;
40 #define OK(i) (i & 0 && p[i - 1].y == p[i].y && p[i].x &= p[i - 1].x + Q - 1)
42 int T, N, M, P, Q, K;
43 struct Point {
bool operator & (const Point &A) const {
return y == A.y ? x & A.x : y & A.y;
48 }p[MAXM];
50 struct SegTree {
LL ma[MAXN&&2], add[MAXN&&2];
void build(int k, int L, int R) {
ma[k] = add[k] = 0;
if(L == R)
build(lson); build(rson);
void pushDown(int k) {
ma[k&&1] += add[k];
add[k&&1] += add[k];
ma[k&&1|1] += add[k]; add[k&&1|1] += add[k];
add[k] = 0;
void update(int k, int L, int R, int l, int r, int val) {
if(R & l || L & r) return ;
if(l &= L && R &= r) { ma[k] += add[k] += return ; }
pushDown(k);
update(lson, l, r, val);
update(rson, l, r, val);
ma[k] = max(ma[k&&1], ma[k&&1|1]);
LL query(int k, int L, int R, int l, int r) {
if(R & l || L & r) return 0;
if(l &= L && R &= r) return ma[k];
pushDown(k);
return max(query(lson, l, r), query(rson, l, r));
83 int main()
while(~scanf("%d", &T)) while(T--)
scanf("%d %d %d %d %d", &N, &M, &P, &Q, &K);
rep (i, 0, K - 1) scanf("%d %d", &p[i].y, &p[i].x);
sort(p, p + K);
segTree.build(1, 1, M);
LL ans = 0, fr = 0, re = 0;
rep (i, P, N) {
while(fr & K && p[fr].y &= i) {
int st = OK(fr) ? p[fr-1].x + Q : p[fr].x;
int ed = min(p[fr].x + Q - 1, M);
segTree.update(1, 1, M, st, ed, 1);
while(i - p[re].y &= P) {
int st = OK(re) ? p[re-1].x + Q : p[re].x;
int ed = min(p[re].x + Q - 1, M);
segTree.update(1, 1, M, st, ed, -1);
ans += segTree.query(1, 1, M, 1, M);
printf("%.2lf\n", (double)ans / (N - P + 1));
阅读(...) 评论()