3
9
2016
0

[BZOJ3245] 最快路线

很久以前写的题目了……

SPFA

显然的算法啊

?
bzoj 3245
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
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
   
int fa[155][155],n,m,d,h[155],en=0,f[155][155];
double D[155][155];
   
struct Edge{
int b,v,l,next;
}e[30005];
   
struct Queue{
int speed,i,j;
};
   
void shuchu(int u,int v,int f){
if(u==v && v==0){printf("0 ");return;}
shuchu(fa[u][v],u,0);
if(f==0)printf("%d ",v);
else printf("%d\n",v);
}
   
void add(int as,int bs,int vs,int ls){
e[++en].b=bs;
e[en].v=vs;
e[en].l=ls;
e[en].next=h[as];
h[as]=en;
}
   
void spfa(){
queue<Queue> Q;
Queue pos;
pos.i=0;
pos.j=0;
pos.speed=70;
Q.push(pos);
int u,v;
D[0][0]=0;
f[0][0]=1;
while(!Q.empty()){
    Queue uu;
    uu=Q.front();
    u=uu.j;
    Q.pop();
    f[uu.i][u]=0;
    for(int i=h[uu.j];i;i=e[i].next){
        v=e[i].b;
        int speed=e[i].v;
        if(e[i].v<=0)speed=uu.speed;
        if(D[u][v]>D[uu.i][u]+(double)e[i].l/(double)speed){
            D[u][v]=D[uu.i][u]+(double)e[i].l/(double)speed;
            fa[u][v]=uu.i;
            if(!f[u][v]){
                f[u][v]=1;
                pos.i=u;
                pos.j=v;
                pos.speed=speed;
                Q.push(pos);
            }
        }
    }
}
}
   
int main(){
freopen("3245.in","r",stdin);
freopen("3245.out","w",stdout);
scanf("%d %d %d",&n,&m,&d);
memset(D,0x7f,sizeof(D));
for(int i=0;i<m;i++){
    int as,bs,vs,ls;
    scanf("%d %d %d %d",&as,&bs,&vs,&ls);
    add(as,bs,vs,ls);
}
spfa();
double mind=99999999999999.0;
int ans;
for(int i=0;i<n;i++){
    if(mind>D[i][d]){
        ans=i;
        mind=D[i][d];
    }
}
shuchu(ans,d,1);
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
8
2016
0

[BZOJ2178] 圆的面积并

直接辛普森积分，我是照着nixy的模版写的。

?
bzoj 2178
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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
  
int n;
const double eps=1e-9;
  
struct Circle{
double x,y,r;
friend bool operator<(Circle a,Circle b){
    return a.r<b.r;
}
}cir[1005];
  
struct Line{
double l,r;
Line(double kl=0,double kr=0){l=kl;r=kr;}
}line[1005];
  
double Dist(Circle a,Circle b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
  
bool cmp(Line a,Line b){
return a.l<b.l;
}
  
double F(double x){
int lx=0;
for(int i=1;i<=n;i++){
    double ex=(x-cir[i].x)*(x-cir[i].x);
    if(ex>cir[i].r)continue;
    ex=sqrt(cir[i].r-ex);
    line[++lx]=Line(cir[i].y-ex,cir[i].y+ex);
}
if(lx==0)return 0;
sort(line+1,line+lx+1,cmp);
double L=line[1].l,R=line[1].r,res=0;
for(int i=2;i<=lx;i++){
    if(line[i].l<=R){R=max(line[i].r,R);}
    else {res+=R-L;L=line[i].l;R=line[i].r;}
}
return res+R-L;
}
  
double Simpson(double l,double r,double Fl,double Fmid,double Fr){
return (Fl+Fr+4*Fmid)*(r-l)/6;
}
  
double Self_Adjust(double l,double r,double Fl,double Fmid,double Fr){
double mid=l/2+r/2;
double F1=F(l/2+mid/2),F2=F(mid/2+r/2);
if(r-l<2){
    double S1=Simpson(l,mid,Fl,F1,Fmid),S2=Simpson(mid,r,Fmid,F2,Fr),Se=Simpson(l,r,Fl,Fmid,Fr);
    if(fabs(Se-S1-S2)<eps)return S1+S2;
    else return Self_Adjust(l,mid,Fl,F1,Fmid)+Self_Adjust(mid,r,Fmid,F2,Fr);
}
else return Self_Adjust(l,mid,Fl,F1,Fmid)+Self_Adjust(mid,r,Fmid,F2,Fr);
}
  
int main(){
freopen("2178.in","r",stdin);
freopen("2178.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%lf %lf %lf",&cir[i].x,&cir[i].y,&cir[i].r);
    cir[i].r*=cir[i].r;
}
printf("%.3lf\n",Self_Adjust(-2000,2000,F(-2000),F(0),F(2000)));
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
8
2016
0

[BZOJ1901] Zju2112 Dynamic Rankings

这是我第一次写树状数组套可持久化数据结构，写了好长时间……

首先你需要AC POJ2104

然后把一个个递增的版本用树状数组维护就好了

为什么呢？因为你维护的是权值线段树，需要得到的值其实是作差得来的。

那么我们用类似树状数组的作差方法就可以了。

?
bzoj 1901
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
95
96
97
98
99
100
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
 
int siz,n,m,a[10005],tab[500005],tb,root[10005],A[10005],B[10005],An,Bn;
 
struct SegTree{
int nl,nr,sum;
}tree[2000005];
 
struct Ask{
int opt,l,r,k;
}ask[10005];
 
int lowbit(int x){return x&(-x);}
 
int Div(int x){
int l=1,r=tb;
while(l<=r){
    int mid=l+r>>1;
    if(tab[mid]<x)l=mid+1;
    else r=mid-1;
}
return l;
}
 
void AddTree(int lastrt,int l,int r,int &rt,int pos,int val){
if(rt==0)rt=++siz;
tree[rt].sum=tree[lastrt].sum+val;
tree[rt].nl=tree[lastrt].nl;
tree[rt].nr=tree[lastrt].nr;
if(l==r)return;
int mid=l+r>>1;
if(pos<=mid)AddTree(tree[lastrt].nl,l,mid,tree[rt].nl,pos,val);
else AddTree(tree[lastrt].nr,mid+1,r,tree[rt].nr,pos,val);
}
 
int Sum(int l,int r,int k){
if(l==r)return l;
int sumL=0,sumR=0,mid=l+r>>1;
for(int i=1;i<=An;i++)sumL+=tree[tree[A[i]].nl].sum;
for(int i=1;i<=Bn;i++)sumR+=tree[tree[B[i]].nl].sum;
if(sumR-sumL>=k){
    for(int i=1;i<=An;i++)A[i]=tree[A[i]].nl;
    for(int i=1;i<=Bn;i++)B[i]=tree[B[i]].nl;
    return Sum(l,mid,k);
}
else {
    for(int i=1;i<=An;i++)A[i]=tree[A[i]].nr;
    for(int i=1;i<=Bn;i++)B[i]=tree[B[i]].nr;
    return Sum(mid+1,r,k-sumR+sumL);
}
}
 
int main(){
freopen("1901.in","r",stdin);
freopen("1901.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    tab[++tb]=a[i];
}
for(int i=1;i<=m;i++){
    char s[5];
    scanf("%s",s);
    if(s[0]=='C'){
        scanf("%d %d",&ask[i].l,&ask[i].k);
        ask[i].opt=1;
        tab[++tb]=ask[i].k;
    }
    if(s[0]=='Q'){
        scanf("%d %d %d",&ask[i].l,&ask[i].r,&ask[i].k);
        ask[i].opt=2;
        ask[i].l--;
    }
}
sort(tab+1,tab+tb+1);
tb=unique(tab+1,tab+tb+1)-tab-1;
for(int i=1;i<=n;i++){
    int x=Div(a[i]);
    for(int j=i;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,1);
}
for(int i=1;i<=m;i++){
    if(ask[i].opt==1){
        int x=Div(a[ask[i].l]);
        for(int j=ask[i].l;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,-1);
        a[ask[i].l]=ask[i].k;
        x=Div(ask[i].k);
        for(int j=ask[i].l;j<=n;j+=lowbit(j))AddTree(root[j],1,tb,root[j],x,1);
    }
    else {
        An=Bn=0;
        for(int j=ask[i].l;j;j-=lowbit(j))A[++An]=root[j];
        for(int j=ask[i].r;j;j-=lowbit(j))B[++Bn]=root[j];
        printf("%d\n",tab[Sum(1,tb,ask[i].k)]);
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
7
2016
0

[BZOJ1503] [NOI2004]郁闷的出纳员

好多水题的题解忘了传……

直接Treap

?
bzoj 1503
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
95
96
97
98
99
#include<cstdio>
#include<cstdlib>
  
int n,mn,tag=0,root,leave=0,cnt;
char s[2];
  
struct Treap{
    int l,r,v,rnd,siz,w;
}tree[100005];
  
void Pre(){
tree[0].l=0;
tree[0].r=0;
root=0;
cnt=0;
srand(123465);
}
  
void Pushup(int rt){
tree[rt].siz=tree[tree[rt].l].siz+tree[tree[rt].r].siz+tree[rt].w;
}
  
void Lr(int &p){
int q=tree[p].r;
tree[p].r=tree[q].l;
tree[q].l=p;
tree[q].siz=tree[p].siz;
Pushup(p);
p=q;
}
  
void Rr(int &p){
int q=tree[p].l;
tree[p].l=tree[q].r;
tree[q].r=p;
tree[q].siz=tree[p].siz;
Pushup(p);
p=q;
}
  
void Ins(int &rt,int x){
if(!rt){
    rt=++cnt;
    tree[rt].l=0;
    tree[rt].r=0;
    tree[rt].v=x;
    tree[rt].siz=1;
    tree[rt].w=1;
    tree[rt].rnd=rand()<<15+rand();
    return;
}
tree[rt].siz++;
if(tree[rt].v>x){
    Ins(tree[rt].l,x);
    if(tree[tree[rt].l].rnd<tree[rt].rnd)Rr(rt);
    return;
}
else {
    Ins(tree[rt].r,x);
    if(tree[tree[rt].r].rnd<tree[rt].rnd)Lr(rt);
}
}
  
int Del(int &rt){
if(rt==0)return 0;
if(tree[rt].v+tag<0){
    int temp=tree[tree[rt].l].siz+1;
    rt=tree[rt].r;
    return temp+Del(rt);
}
int temp=Del(tree[rt].l);
tree[rt].siz-=temp;
return temp;
}
  
int Find(int rt,int x){
if(rt==0)return 0;
if(x<=tree[tree[rt].l].siz)return Find(tree[rt].l,x);
else {
    if(x>tree[tree[rt].l].siz+1)return Find(tree[rt].r,x-tree[tree[rt].l].siz-1);
    return tree[rt].v+tag;
}
}
  
int main(){
freopen("1503.in","r",stdin);
freopen("1503.out","w",stdout);
scanf("%d %d",&n,&mn);
for(int i=1;i<=n;i++){
    int Ts;
    scanf("%s %d",s,&Ts);
    if(s[0]=='I'){if(Ts>=mn){Ins(root,Ts-tag-mn);}}
    if(s[0]=='A'){tag+=Ts;}
    if(s[0]=='S'){tag-=Ts;leave+=Del(root);}
    if(s[0]=='F'){if(Ts>tree[root].siz)puts("-1");else printf("%d\n",Find(root,tree[root].siz-Ts+1)+mn);}
}
printf("%d\n",leave);
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
7
2016
0

[BZOJ4196] [Noi2015]软件包管理器

树链剖分直接上

?
bzoj 4196
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
  
int dep[100005],top[100005],id[100005],pre[100005],n,q,en,h[100005],fa[100005],son[100005],siz[100005],sn;
  
struct Edge{
int b,next;
}e[100005];
  
void AddEdge(int sa,int sb){
if(sa==sb)return;
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
  
struct SegTree{
int tag,sum,l,r,rem;
}tree[400005];
  
void Pushdown(int rt){
if(tree[rt].rem){
    tree[rt*2].tag=0;
    tree[rt*2+1].tag=0;
    tree[rt*2].sum=0;
    tree[rt*2+1].sum=0;
    tree[rt].tag=0;
    tree[rt*2].rem=1;
    tree[rt*2+1].rem=1;
    tree[rt].rem=0;
}
if(tree[rt].tag){
    tree[rt*2].tag=1;
    tree[rt*2+1].tag=1;
    tree[rt*2].rem=0;
    tree[rt*2+1].rem=0;
    tree[rt*2].sum=tree[rt*2].r-tree[rt*2].l+1;
    tree[rt*2+1].sum=tree[rt*2+1].r-tree[rt*2+1].l+1;
    tree[rt].tag=0;
}
}
  
void Pushup(int rt){
tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
}
  
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){
    tree[rt].rem=tree[rt].tag=tree[rt].sum=0;
    return;
}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
tree[rt].rem=tree[rt].tag=tree[rt].sum=0;
}
  
void Add(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    tree[rt].tag=1;
    tree[rt].rem=0;
    tree[rt].sum=tree[rt].r-tree[rt].l+1;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Add(rt*2,l,r);
if(r>mid)Add(rt*2+1,l,r);
Pushup(rt);
}
  
void Del(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    tree[rt].rem=1;
    tree[rt].tag=0;
    tree[rt].sum=0;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Del(rt*2,l,r);
if(r>mid)Del(rt*2+1,l,r);
Pushup(rt);
}
  
int Sum(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    return tree[rt].sum;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Sum(rt*2,l,r);
if(r>mid)ans+=Sum(rt*2+1,l,r);
Pushup(rt);
return ans;
}
  
void dfs1(int u,int fat){
fa[u]=fat;
son[u]=0;
dep[u]=dep[fat]+1;
siz[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
  
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++sn;
pre[sn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==son[u] || v==fa[u])continue;
    dfs2(v,v);
}
}
  
int AddLine(int u){
int ans=0,f=top[u];
while(f!=1){
    ans+=id[u]-id[f]+1-Sum(1,id[f],id[u]);
    Add(1,id[f],id[u]);
    u=fa[f];
    f=top[u];
}
ans+=id[u]-id[1]+1-Sum(1,id[1],id[u]);
Add(1,id[1],id[u]);
return ans;
}
  
int DelSome(int u){
int ans=Sum(1,id[u],id[u]+siz[u]-1);
Del(1,id[u],id[u]+siz[u]-1);
return ans;
}
  
int main(){
freopen("4196.in","r",stdin);
freopen("4196.out","w",stdout);
scanf("%d",&n);
for(int i=2;i<=n;i++){
    int tp;
    scanf("%d",&tp);
    AddEdge(tp+1,i);
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
    char s[10];
    int u;
    scanf("%s %d",s,&u);
    if(s[0]=='i')printf("%d\n",AddLine(u+1));
    else printf("%d\n",DelSome(u+1));
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
7
2016
0

[BZOJ4195] [Noi2015]程序自动分析

水并查集

?
bzoj 4195
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int t,n,f[1000005],g[1000005],index=0,ind;
 
struct Node{
int a,b,o;
}node[1000005];
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){if(x>y)f[x]=y;else f[y]=x;}
 
int main(){
freopen("4195.in","r",stdin);
freopen("4195.out","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ind=0;
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&node[i].a,&node[i].b,&node[i].o);
    g[++ind]=node[i].a;
    g[++ind]=node[i].b;
}
sort(g+1,g+ind+1);
ind=unique(g+1,g+ind+1)-g-1;
for(int i=1;i<=n;i++){
    node[i].a=lower_bound(g+1,g+ind+1,node[i].a)-g;
    node[i].b=lower_bound(g+1,g+ind+1,node[i].b)-g;
}
for(int i=1;i<=ind;i++)f[i]=i;
for(int i=1;i<=n;i++){
    if(node[i].o==1){Union(Find(node[i].a),Find(node[i].b));}
}
int flag=0;
for(int i=1;i<=n;i++){
    if(node[i].o==0 && Find(node[i].a)==Find(node[i].b)){puts("NO");flag=1;break;}
}
if(!flag)puts("YES");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
7
2016
0

[BZOJ3928&4048] [Cerc2014] Outer space invaders

区间DP

离散化后考虑一段区间(l,r)（这里指的是出现时间的区间）

那么这段区间的R的最小值至少为这一段区间最高的线段（感觉讲的很抽象啊……最高的线段高度等于这个外星人离你的距离）

然后输出(0,tb)表示在[1,tb-1]能取到的最小代价，所以中间那个tb要++，因为我用的是开区间

?
bzoj 3928&4048
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,table[10005],tb,f[1005][1005],T;
 
struct Plane{
int a,b,d;
}p[305];
 
int main(){
freopen("3928_4048.in","r",stdin);
freopen("3928_4048.out","w",stdout);
scanf("%d",&T);
while(T--){
    tb=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&p[i].a,&p[i].b,&p[i].d);
        table[++tb]=p[i].a;
        table[++tb]=p[i].b;
    }
    sort(table+1,table+tb+1);
    tb=unique(table+1,table+tb+1)-table-1;
    for(int i=1;i<=n;i++){
        p[i].a=lower_bound(table+1,table+tb+1,p[i].a)-table;
        p[i].b=lower_bound(table+1,table+tb+1,p[i].b)-table;
    }
    tb++;
    for(int len=0;len<=tb;len++){
        for(int i=0;i<=tb-len;i++){
            int j=i+len,H=-1;
            for(int k=1;k<=n;k++){
                if(i<p[k].a && p[k].b<j && (H==-1 || p[H].d<p[k].d))H=k;
            }
            if(H==-1)f[i][j]=0;
            else {
                f[i][j]=2100000000;
                for(int k=p[H].a;k<=p[H].b;k++){
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]+p[H].d);
                }
            }
        }
    }
    printf("%d\n",f[0][tb]);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
5
2016
0

[BZOJ1857] [Scoi2010]传送带

三分点在AB和CD上面的位置

然后搞一搞就行了

?
bzoj 1857
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
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
 
struct Point{
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y){}
friend Point operator+(Point a,Point b){return Point(a.x+b.x,a.y+b.y);}
friend Point operator-(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}
friend Point operator*(Point a,double k){return Point(a.x*k,a.y*k);}
double mold(){return sqrt(x*x+y*y);}
}A,B,C,D;
 
double V0,Vab,Vcd;
const double eps=1e-6;
 
double Calc(Point X,Point Y){
return (Y-X).mold()/V0+(Y-D).mold()/Vcd;
}
 
double sanfen2(Point x){
double l=0,r=1,res=(x-A).mold()/Vab;
while(r-l>eps){
    double mid1=l+(r-l)/3.0,mid2=r-(r-l)/3.0;
    double p1=Calc(x,C+(D-C)*mid1),p2=Calc(x,C+(D-C)*mid2);
    if(p1<p2)r=mid2;
    else l=mid1;
}
return res+Calc(x,C+(D-C)*l);
}
 
double sanfen1(){
double l=0,r=1;
while(r-l>eps){
    double mid1=l+(r-l)/3.0,mid2=r-(r-l)/3.0;
    double p1=sanfen2(A+(B-A)*mid1),p2=sanfen2(A+(B-A)*mid2);
    if(p1<p2)r=mid2;
    else l=mid1;
}
return sanfen2(A+(B-A)*l);
}
 
int main(){
freopen("1857.in","r",stdin);
freopen("1857.out","w",stdout);
scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y);
scanf("%lf %lf %lf",&Vab,&Vcd,&V0);
printf("%.2lf\n",sanfen1());
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
5
2016
0

[BZOJ1076] [SCOI2008]奖励关

状态压缩DP

根据期望的线性性，我们知道可以分开考虑每个物品在每一时刻出现的期望

然后把这些期望加起来再除以物品种类数（因为要求平均期望，而每种物品出现的概率都是1/k）

那么DP方程就是

f[i][j]+=max(f[i+1][j],f[i+1][j|bit[k]]+score[k]);(其中满足可以取k物品的条件)

f[i][j]+=f[i+1][j];(当前枚举到的k物品没办法取到所得到的上一次的平均得分期望)

最后f[i][j]/=k就可以了

为什么要从f[i+1][j]推导f[i][j]?因为如果顺推的话有可能会枚举到无效的状态，而且最后没办法输出f[n][j]

所以只需要倒推就可以解决问题啦

?
bzoj 1076
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int k,n,bit[25],ist[25],score[25];
double f[105][1<<15];
 
int main(){
freopen("1076.in","r",stdin);
freopen("1076.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=20;i++)bit[i]=1<<(i-1);
for(int i=1;i<=k;i++){
    scanf("%d",&score[i]);
    int tp;
    for(int j=0;scanf("%d",&tp),tp;j++){
        ist[i]|=bit[tp];
    }
}
for(int i=n;i>=1;i--){
    for(int j=0;j<=bit[k+1]-1;j++){
        for(int l=1;l<=k;l++){
            if((j&ist[l])==ist[l]){
                f[i][j]+=max(f[i+1][j],f[i+1][j|bit[l]]+score[l]);
            }
            else f[i][j]+=f[i+1][j];
        }
        f[i][j]/=k;
    }
}
printf("%.6f\n",f[1][0]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
3
3
2016
0

[BZOJ1664] [Usaco2006 Open]County Fair Events 参加节日庆祝

排序直接做就行了

?
bzoj 1664
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,ans=0;
 
struct Event{
int s,t;
friend bool operator<(Event a,Event b){
return (a.t<b.t)||(a.t==b.t && a.s<b.s);
}
}e[10005];
 
int main(){
freopen("1664.in","r",stdin);
freopen("1664.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d %d",&e[i].s,&e[i].t);
    e[i].t+=e[i].s;
}
sort(e+1,e+n+1);
int last=0;
for(int i=1;i<=n;i++){
    if(e[i].s>=e[last].t){
        ans++;
        last=i;
    }
    else if(e[i].t<e[last].t){
        last=i;
    }
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com