首页 > 代码库 > bzoj2244 [SDOI2011]拦截导弹
bzoj2244 [SDOI2011]拦截导弹
我是萌萌的传送门
这题其实没那么难，只是我做法麻烦所以调起来相当费事儿……这人没救了
第一问显然是裸的三维偏序，分治随便搞搞就行了。考虑第二问，答案其实就是包括它的子序列数除以总方案数，那么定义$g[i]$为以i结尾的子序列数量，$h[i]$为以i开头的子序列数量，包括它的子序列数就是$g[i]h[i]$了。
而$g[i],h[i]$的转移方程分别是：
\begin{align}g[i]=\sum_{j<i,a_j<a_i,f[j]=f[i]-1}g[j]\end{align}
\begin{align}g[i]=1(f[i]=1)\end{align}
\begin{align}h[i]=\sum_{i<j,a_i<a_j,f[i]=f[j]-1}h[j]\end{align}
\begin{align}h[i]=1(f[i]=\max_{j=1}^n{f[j]})\end{align}
(注：这里的$<$都是指满足题中的偏序关系)
不难看出这还是三维偏序的形式，再跑两遍分治即可。
三遍分治都是手打的，没有用复制粘贴，写了好久……超过200行的分治，真是醉了……
1 /************************************************************** 2 Problem: 2244 3 User: hzoier 4 Language: C++ 5 Result: Accepted 6 Time:4636 ms 7 Memory:6368 kb 8 ****************************************************************/ 9 #include<cstdio> 10 #include<cstring> 11 #include<algorithm> 12 #include<vector> 13 using namespace std; 14 const int maxn=50010; 15 struct A{ 16 int x,y,id; 17 bool ins; 18 bool operator<(const A &a)const{ 19 if(x!=a.x)return x<a.x; 20 return ins&&!a.ins; 21 } 22 }a[maxn],aa[maxn],b[maxn]; 23 bool cmp(const A &a,const A &b){ 24 if(a.x!=b.x)return a.x>b.x; 25 return a.ins&&!b.ins; 26 } 27 void CDQ1(int,int); 28 void CDQ2(int,int); 29 void CDQ3(int,int); 30 void add1(int,int); 31 void add2(int,long double); 32 int query1(int); 33 long double query2(int); 34 void clear1(int); 35 void clear2(int); 36 vector<int>vec[maxn]; 37 long double c2[maxn]={0},g[maxn]={0},h[maxn]={0},tmp=0.0; 38 int n,t[maxn],f[maxn],c1[maxn],ans; 39 int main(){ 40 scanf("%d",&n); 41 for(int i=1;i<=n;i++){ 42 scanf("%d%d",&a[i].x,&a[i].y); 43 t[i]=a[i].y; 44 a[i].id=i; 45 f[i]=1; 46 } 47 sort(t+1,t+n+1); 48 for(int i=1;i<=n;i++)a[i].y=lower_bound(t+1,t+n+1,a[i].y)-t; 49 copy(a+1,a+n+1,aa+1); 50 CDQ1(1,n); 51 for(int i=1;i<=n;i++){ 52 ans=max(ans,f[i]); 53 vec[f[i]].push_back(i); 54 } 55 printf("%d\n",ans); 56 for(int i=0;i<(int)vec[1].size();i++)g[vec[1][i]]=1.0; 57 for(int k=2;k<=ans;k++){ 58 int i=0,j=0,cnt=0; 59 while(i<(int)vec[k-1].size()&&j<(int)vec[k].size()){ 60 if(vec[k-1][i]<vec[k][j]){ 61 b[++cnt]=aa[vec[k-1][i]]; 62 b[cnt].ins=true; 63 i++; 64 } 65 else{ 66 b[++cnt]=aa[vec[k][j]]; 67 b[cnt].ins=false; 68 j++; 69 } 70 } 71 while(i<(int)vec[k-1].size()){ 72 b[++cnt]=aa[vec[k-1][i]]; 73 b[cnt].ins=true; 74 i++; 75 } 76 while(j<(int)vec[k].size()){ 77 b[++cnt]=aa[vec[k][j]]; 78 b[cnt].ins=false; 79 j++; 80 } 81 CDQ2(1,cnt); 82 } 83 for(int i=0;i<(int)vec[ans].size();i++){ 84 tmp+=g[vec[ans][i]]; 85 h[vec[ans][i]]=1.0; 86 } 87 for(int k=ans-1;k;k--){ 88 int i=0,j=0,cnt=0; 89 while(i<(int)vec[k+1].size()&&j<(int)vec[k].size()){ 90 if(vec[k+1][i]<vec[k][j]){ 91 b[++cnt]=aa[vec[k+1][i]]; 92 b[cnt].ins=true; 93 i++; 94 } 95 else{ 96 b[++cnt]=aa[vec[k][j]]; 97 b[cnt].ins=false; 98 j++; 99 } 100 } 101 while(i<(int)vec[k+1].size()){ 102 b[++cnt]=aa[vec[k+1][i]]; 103 b[cnt].ins=true; 104 i++; 105 } 106 while(j<(int)vec[k].size()){ 107 b[++cnt]=aa[vec[k][j]]; 108 b[cnt].ins=false; 109 j++; 110 } 111 CDQ3(1,cnt); 112 } 113 for(int i=1;i<=n;i++)printf("%.10lf ",(double)(g[i]*h[i]/tmp)); 114 return 0; 115 } 116 void CDQ1(int l,int r){ 117 if(l>=r)return; 118 int mid=(l+r)>>1; 119 CDQ1(l,mid); 120 copy(aa+l,aa+r+1,a+l); 121 sort(a+l,a+mid+1,cmp); 122 sort(a+mid+1,a+r+1,cmp); 123 int i=l,j=mid+1; 124 while(i<=mid&&j<=r){ 125 if(a[i].x>=a[j].x){ 126 add1(n-a[i].y+1,f[a[i].id]); 127 i++; 128 } 129 else{ 130 f[a[j].id]=max(f[a[j].id],query1(n-a[j].y+1)+1); 131 j++; 132 } 133 } 134 while(j<=r){ 135 f[a[j].id]=max(f[a[j].id],query1(n-a[j].y+1)+1); 136 j++; 137 } 138 for(i=l;i<=mid;i++)clear1(n-a[i].y+1); 139 CDQ1(mid+1,r); 140 } 141 void CDQ2(int l,int r){ 142 if(l>=r)return; 143 int mid=(l+r)>>1; 144 CDQ2(l,mid); 145 copy(b+l,b+r+1,a+l); 146 sort(a+l,a+mid+1,cmp); 147 sort(a+mid+1,a+r+1,cmp); 148 int i=l,j=mid+1; 149 while(i<=mid&&j<=r){ 150 if(a[i].x>a[j].x||(a[i].x==a[j].x&&a[i].ins)){ 151 if(a[i].ins)add2(n-a[i].y+1,g[a[i].id]); 152 i++; 153 } 154 else{ 155 if(!a[j].ins)g[a[j].id]+=query2(n-a[j].y+1); 156 j++; 157 } 158 } 159 while(i<=mid){ 160 if(a[i].ins)add2(n-a[i].y+1,g[a[i].id]); 161 i++; 162 } 163 while(j<=r){ 164 if(!a[j].ins)g[a[j].id]+=query2(n-a[j].y+1); 165 j++; 166 } 167 for(i=l;i<=mid;i++)if(a[i].ins)clear2(n-a[i].y+1); 168 CDQ2(mid+1,r); 169 } 170 void CDQ3(int l,int r){ 171 if(l>=r)return; 172 int mid=(l+r)>>1; 173 CDQ3(mid+1,r); 174 copy(b+l,b+r+1,a+l); 175 sort(a+l,a+mid+1); 176 sort(a+mid+1,a+r+1); 177 int i=mid+1,j=l; 178 while(i<=r&&j<=mid){ 179 if(a[i].x<a[j].x||(a[i].x==a[j].x&&a[i].ins)){ 180 if(a[i].ins)add2(a[i].y,h[a[i].id]); 181 i++; 182 } 183 else{ 184 if(!a[j].ins)h[a[j].id]+=query2(a[j].y); 185 j++; 186 } 187 } 188 while(i<=r){ 189 if(a[i].ins)add2(a[i].y,h[a[i].id]); 190 i++; 191 } 192 while(j<=mid){ 193 if(!a[j].ins)h[a[j].id]+=query2(a[j].y); 194 j++; 195 } 196 for(int i=mid+1;i<=r;i++)if(a[i].ins)clear2(a[i].y); 197 CDQ3(l,mid); 198 } 199 void add1(int x,int d){ 200 while(x<=n){ 201 c1[x]=max(c1[x],d); 202 x+=x&-x; 203 } 204 } 205 void add2(int x,long double d){ 206 while(x<=n){ 207 c2[x]+=d; 208 x+=x&-x; 209 } 210 } 211 int query1(int x){ 212 int ans=0; 213 while(x){ 214 ans=max(ans,c1[x]); 215 x&=x-1; 216 } 217 return ans; 218 } 219 long double query2(int x){ 220 long double ans=0.0; 221 while(x){ 222 ans+=c2[x]; 223 x&=x-1; 224 } 225 return ans; 226 } 227 void clear1(int x){ 228 while(x<=n){ 229 c1[x]=0; 230 x+=x&-x; 231 } 232 } 233 void clear2(int x){ 234 while(x<=n){ 235 c2[x]=0.0; 236 x+=x&-x; 237 } 238 }
有一些做法可以一边分治一边求出$g$，然后再跑一遍分治就能求出$h$，可以减少代码量？听说lrd写的就是这个？表示还没理解清楚……
bzoj2244 [SDOI2011]拦截导弹
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。