cdq分治优化dp的题目, 不是很了解当时省选这个题目的得分情况。

不过感觉对于日益简单SD一轮, 这个题目放在现在算是难度适中。

比较好写的一个题目。

传送门

题目大意

求最长三维偏序, 并求对于一个位置, 所在最长偏序的方案数。

解题报告

三维偏序, 可以cdq分治 + 树状数组做。

最长三维偏序比较容易解决, 统计一个位置所在的最长三维偏序的方案数, 需要记录正反两个方向的最大值和方案数, 如果最大值的和等于答案, 则方案数为两侧方案数的乘积, 否则为0。

代码

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
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
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 double ff;
const int N=50010;
const int inf=1000000000;
struct point {
int a,b,id; point(int a=0,int b=0,int id=0)
:a(a),b(b),id(id) {}
} p[N];
int vc[N],vas;
int n,m,f[2][N]; ff g[2][N];
inline bool cmp(point x,point y) {return x.a==y.a?x.id<y.id:x.a<y.a;}
inline void in(int &x) {
char ch=getchar(); int f=1;
for (;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for (x=0;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
x*=f;
}
int v[N],vv[N],mx[N]; ff hs[N];
inline void insert(int a,ff b,int x) {
for (;x<=n;x+=x&-x) if (mx[x]==a) hs[x]+=b;
else if (mx[x]<a) mx[x]=a,hs[x]=b;
}
inline void erase(int x) {
for (;x<=n;x+=x&-x) hs[x]=mx[x]=0;
}
inline void query(int &a,ff &b,int x) {
a=b=0; for (;x;x-=x&-x) if (mx[x]==a) b+=hs[x];
else if (mx[x]>a) a=mx[x], b=hs[x];
}
inline void cdq(int l,int r,int t) {
if (l==1&&r==n) rep(i,l,r) v[i]=i;
if (l==r) { int x=p[v[l]].id;
if (f[t][x]==1) g[t][x]+=1;
else if (!f[t][x]) f[t][x]=1, g[t][x]=1;
return;
}
int _l,_r,md; md=(l+r)>>1,_l=l-1, _r=md;
rep(i,l,r) { int x=v[i];
if (p[x].id<=md) vv[++_l]=x; else vv[++_r]=x;
}
rep(i,l,r) v[i]=vv[i];
cdq(l,md,t), _l=l;
rep(i,md+1,r) { int x=v[i],_mx; ff _hs;
while (_l<=md&&p[v[_l]].a<=p[x].a)
insert(f[t][p[v[_l]].id],g[t][p[v[_l]].id],p[v[_l]].b),++_l;
query(_mx,_hs,p[x].b) ;
int d=p[x].id;
if (_mx+1==f[t][d]) g[t][d]+=_hs;
else if(_mx+1>f[t][d]) f[t][d]=_mx+1,g[t][d]=_hs;
}
rep(i,l,md) erase(p[v[i]].b);
cdq(md+1,r,t);
_l=l,_r=md+1; int x=l-1;
while (_l<=md||_r<=r) {
if ((_l<=md)&&(_r>r||p[v[_l]].a<p[v[_r]].a))
vv[++x]=v[_l++];
else vv[++x]=v[_r++];
}
rep(i,l,r) v[i]=vv[i];
}
int main() {
in(n); rep(i,1,n) {
in(p[i].a),in(p[i].b),p[i].id=i;
vc[vas++]=p[i].b;
}
sort(vc,vc+vas), vas=unique(vc,vc+vas)-vc;
rep(i,1,n) p[i].b=lower_bound(vc,vc+vas,p[i].b)-vc+1;
rep(i,1,n/2) swap(p[i].a,p[n-i+1].a),swap(p[i].b,p[n-i+1].b);
sort(p+1,p+1+n,cmp),cdq(1,n,0);
rep(i,1,n) p[i].b=vas-p[i].b+1,p[i].a=inf-p[i].a+1,p[i].id=n-p[i].id+1;
sort(p+1,p+1+n,cmp),cdq(1,n,1);
int as=0; ff total=0;
rep(i,1,n) if (f[0][i]+f[1][n-i+1]-1==as) total+=g[0][i]*g[1][n-i+1];
else if (f[0][i]+f[1][n-i+1]-1>as) as=f[0][i]+f[1][n-i+1]-1,total=g[0][i]*g[1][n-i+1];
printf("%d\n",as); total/=as;
vep(i,n,1) if (f[0][i]+f[1][n-i+1]-1==as)
printf("%lf ", g[0][i]*g[1][n-i+1]/total);
else printf("0 ");
puts(""); return 0;
}

留言