題意：
有b個(gè)炸彈，p個(gè)飛機(jī)，平行于x軸飛行，地面部署了m個(gè)導(dǎo)彈，只能垂直打。知道0時(shí)刻炸彈、飛機(jī)的坐標(biāo)，以及導(dǎo)彈的坐標(biāo)以及炸彈、導(dǎo)彈、飛機(jī)的速度，問不打到飛機(jī)的情況下最多能攔截多少導(dǎo)彈？
給力條件：炸彈被導(dǎo)彈擊中后，繼續(xù)飛行，而導(dǎo)彈立刻消失。飛行物高度均不同
有個(gè)注意點(diǎn)：注意C++中的短路問題，慎用兩個(gè)函數(shù)相或、與，可能因此一個(gè)函數(shù)得不到執(zhí)行，這個(gè)在線段樹里是很麻煩的。寧可多寫一步
解法：
上次比賽這題死都A不掉，今天重新做了下，1A。。
首先，看到這題肯定想到二分圖的匹配模型。這個(gè)不細(xì)說，說下之前的處理。
首先，按照飛行物高度排序，然后枚舉導(dǎo)彈i能否打到j(luò)個(gè)炸彈，計(jì)算該導(dǎo)彈打到每個(gè)飛行物的時(shí)間區(qū)間，看區(qū)間有沒有被完全覆蓋即可判斷。這里用到線段樹。然后就是可惡的精度問題，其實(shí)，這題完全能夠避免精度誤差，將所有坐標(biāo)預(yù)先乘以三種速度的最小公倍數(shù)，然后離散化再用線段樹來統(tǒng)計(jì)就沒問題了。區(qū)間處理還要注意一點(diǎn)就是處理成左閉右開區(qū)間，用[s*2,e*2-1)即可。
代碼：
1
# include <cstdio>
2# include <algorithm>
3# include <vector>
4# include <cstring>
5using namespace std;
6struct graph
7
{
8
int g[305],nxt[305*305],v[305*305],c,match[605];
9 bool used[305];
10 void clear()
11
{
12 memset(g,-1,sizeof(g));
13 memset(match,-1,sizeof(match));
14 c=0;
15
}
16 void insert(int s,int e)
17 {
18 v[c]=e;
19 nxt[c]=g[s];
20 g[s]=c++;
21 }
22 bool dfs(int pos)
23 {
24 if(used[pos]) return false;
25 used[pos]=true;
26 for(int p=g[pos];p!=-1;p=nxt[p])
27 if(match[v[p]]==-1||dfs(match[v[p]]))
28 {
29 match[v[p]]=pos;
30 return true;
31 }
32 return false;
33 }
34 int Match(int n)
35 {
36 int res=0;
37 for(int i=0;i<n;i++)
38 {
39 memset(used,false,sizeof(used));
40 res+=dfs(i);
41 }
42 return res;
43 }
44
}g;
45struct st_tree
46{
47 struct node
48 {
49 int s,e;
50 bool cover;
51 }st[10000];
52 int mid(int s,int e)
53 {
54 return (s+e)>>1;
55 }
56 void init(int s,int e,int pos=1)
57 {
58 st[pos].s=s;
59 st[pos].e=e;
60 st[pos].cover=false;
61 if(e!=s+1)
62 {
63 init(s,mid(s,e),pos<<1);
64 init(mid(s,e),e,(pos<<1)+1);
65 }
66 }
67 void clear()
68 {
69 init(0,2500);
70 }
71 bool insert(int s,int e,int pos=1)
72 {
73 if(st[pos].cover) return false;
74 if(st[pos].s==s&&st[pos].e==e)
75 {
76 st[pos].cover=true;
77 return true;
78 }
79 else if(e<=mid(st[pos].s,st[pos].e))
80 return insert(s,e,pos<<1);
81 else if(s>=mid(st[pos].s,st[pos].e))
82 return insert(s,e,(pos<<1)+1);
83 else
84 {
85 bool a1=insert(s,mid(st[pos].s,st[pos].e),pos<<1),a2=insert(mid(st[pos].s,st[pos].e),e,(pos<<1)+1);
86 return a1||a2;
87 }
88 }
89}refer;
90struct node
91{
92 long long x,y;
93 bool type;
94 bool operator<(const node &pos) const
95 {
96 return y<pos.y;
97 }
98};
99int b,p,m;
100node barr[1000];
101long long miss[400];
102int vb,vp,vm;
103long long s[1500],sc=0;
104int gcd(int a,int b)
105{
106 int t;
107 while(b) t=a%b,a=b,b=t;
108 return a;
109}
110int main()
111{
112 int test;
113 scanf("%d",&test);
114 for(int tt=1;tt<=test;tt++)
115 {
116 scanf("%d%d%d%d%d%d",&b,&p,&m,&vb,&vp,&vm);
117 long long lcd=(long long)vb*vp*vm/gcd(vb,gcd(vp,vm));
118 for(int i=0;i<b;i++)
119 {
120 barr[i].type=0;
121 scanf("%lld%lld",&barr[i].x,&barr[i].y);
122 barr[i].x*=lcd;
123 barr[i].y*=lcd;
124 }
125 for(int i=b;i<b+p;i++)
126 {
127 barr[i].type=1;
128 scanf("%lld%lld",&barr[i].x,&barr[i].y);
129 barr[i].x*=lcd;
130 barr[i].y*=lcd;
131 }
132 for(int i=0;i<m;i++)
133 {
134 scanf("%lld",miss+i);
135 miss[i]*=lcd;
136 }
137 sort(barr,barr+b+p);
138 g.clear();
139 for(int i=0;i<m;i++)
140 {
141 sc=0;
142 for(int j=0;j<b+p;j++)
143 {
144 long long ss=(miss[i]-barr[j].x)/(barr[j].type?vp:vb)-barr[j].y/vm,ee=(miss[i]-barr[j].x+lcd)/(barr[j].type?vp:vb)-barr[j].y/vm;
145 if(ee<0) continue;
146 if(ss<0) ss=0;
147 s[sc++]=ss;
148 s[sc++]=ee;
149 }
150 sort(s,s+sc);
151 sc=unique(s,s+sc)-s;
152 refer.clear();
153 for(int j=0;j<b+p;j++)
154 {
155 long long ss=(miss[i]-barr[j].x)/(barr[j].type?vp:vb)-barr[j].y/vm,ee=(miss[i]-barr[j].x+lcd)/(barr[j].type?vp:vb)-barr[j].y/vm;
156 if(ee<0) continue;
157 if(ss<0) ss=0;
158 ss=(lower_bound(s,s+sc,ss)-s)*2;
159 ee=(lower_bound(s,s+sc,ee)-s)*2+1;
160 if(barr[j].type) refer.insert(ss,ee);
161 else if(refer.insert(ss,ee)) g.insert(i,j);
162 }
163
164 }
165 printf("Mission #%d: %d bomber(s) exploded\n",tt,g.Match(m));
166 }
167 return 0;
168}
169