跟着A队大爷XYM做的一个题,想到算法都不敢写系列?

用KD-tree维护些bitset相关的信息, 然后竟然卡得如此巧妙不炸内存?

感觉KD-tree越来越像暴力+剪枝了。

传送门

题目大意

炮台分为\(k\)个阵营, 每个阵营的炮台会攻击一定范围内所有其他阵营的炮台, 随机\(m\)轮, 每轮选择一个炮台攻击, 问期望剩下的完整的阵营数。

解题报告

\[ \text{ans} = \sum_{i=1}^{k} P(i) \]

\(P(i)\) 表示\(i\)阵营不被攻击的概率; \[ P(i) = (1-\frac{x}{n})^m \] 其中, \(x\)表示能够攻击到任意一个炮塔的炮塔个数。

那只要求出\(x\)就好了, 实际上就是能够攻击到阵营中的某个炮塔的集合的并集。

利用KD-tree+bitset得到每个炮塔能被哪些炮塔攻击到, 然后对于一个阵营, 直接\(\text{or}\)起来, 再除去阵营内部的炮塔就可以了。

时间复杂度是\(O(n^2 \sqrt{n} /W )\)的。

空间复杂度是\(O(n^2/8)\)的。

反正就是各种虚, 但是好像数据非常弱?

代码

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
80
81
82
83
84
85
86
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
typedef pair<int,int> pii;
typedef long long ll;
typedef double ff;
const int N=35010;
const int inf=0x7fffffff;
inline void cmax(int &x,int a) { x=a>x?a:x; }
inline void cmin(int &x,int a) { x=a<x?a:x; }
inline int abs(int x) { return x>=0?x:-x; }
inline int sqr(int x) {return x*x;}
inline int max(int a,int b) {return a>b?a:b;}
ff res;
int n,m,K,i,j,k,root,_d,_x,_y,_r,_a,cnt[N],od[N];
int g[N],v[N],nxt[N],ed;
bitset<N>ok,b[N];
struct P {int x,y,r,a,p;} a[N];
struct node {int d[2],l,r,mx[2],mn[2],p;} t[N];
inline bool cmp(const node &a,const node &b) {return a.d[_d]<b.d[_d];}
inline void add(int x,int y) { v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void up(int x) {
add(t[x].p,x);
if(t[x].l){
cmax(t[x].mx[0],t[t[x].l].mx[0]);
cmin(t[x].mn[0],t[t[x].l].mn[0]);
cmax(t[x].mx[1],t[t[x].l].mx[1]);
cmin(t[x].mn[1],t[t[x].l].mn[1]);
}
if(t[x].r){
cmax(t[x].mx[0],t[t[x].r].mx[0]);
cmin(t[x].mn[0],t[t[x].r].mn[0]);
cmax(t[x].mx[1],t[t[x].r].mx[1]);
cmin(t[x].mn[1],t[t[x].r].mn[1]);
}
}
int build(int l,int r,int D) {
int md=(l+r)>>1;
_d=D,nth_element(t+l+1,t+md+1,t+r+1,cmp);
t[md].mx[0]=t[md].mn[0]=t[md].d[0];
t[md].mx[1]=t[md].mn[1]=t[md].d[1];
if(l!=md) t[md].l=build(l,md-1,!D);
if(r!=md) t[md].r=build(md+1,r,!D);
return up(md),md;
}
void modify(node &x, int xx){
if(sqr(max(max(_x-x.mx[0],x.mn[0]-_x),0))+sqr(max(max(_y-x.mx[1],x.mn[1]-_y),0))>_r
&& max(x.mn[0]-_x,0)+max(_x-x.mx[0],0)+max(x.mn[1]-_y,0)+max(_y-x.mx[1],0)>_a) return;
if(max(sqr(_x-x.mn[0]),sqr(_x-x.mx[0]))+max(sqr(_y-x.mn[1]),sqr(_y-x.mx[1]))<=_r
|| max(abs(_x-x.mx[0]),abs(x.mn[0]-_x))+max(abs(_y-x.mx[1]),abs(x.mn[1]-_y))<=_a) { b[xx][i]=1; return;}
//if(sqr(x.d[0]-_x)+sqr(x.d[1]-_y)<=_r||abs(x.d[0]-_x)+abs(x.d[1]-_y)<=_a) ADD(x.p,i);
if(x.l) modify(t[x.l],x.l);
if(x.r) modify(t[x.r],x.r);
}
void dfs(node &x,int _x,int y){ b[_x]|=b[y];
if(x.l) dfs(t[x.l],x.l,_x); if(x.r) dfs(t[x.r],x.r,_x);
}
int main() {
scanf("%d%d%d",&n,&m,&K);
for(i=1;i<=n;i++){
scanf("%d%d%d%d%d",&a[i].x,&a[i].y,&a[i].r,&a[i].a,&a[i].p);
t[i].d[0]=a[i].x,t[i].d[1]=a[i].y,t[i].p=a[i].p;
cnt[a[i].p]++;
}
root=build(1,n,1);
for(i=1;i<=n;i++) _x=a[i].x,_y=a[i].y,_r=sqr(a[i].r),_a=a[i].a,modify(t[root],root);
dfs(t[root],root,0);
for(i=1;i<=K;i++){
ok.reset(); for(j=g[i];j;j=nxt[j]) ok|=b[v[j]];
res+=pow(1.0*(n-ok.count()+cnt[i])/n,m);
}
return printf("%.6lf\n",res),0;
}

留言