uoj7 购票

发表于 | 更新于

Link

一道题，说明我斜率优化和CDQ分治都学的一知半解。所以会写的很详细。

Solution

30pts

f[i]=min{f[j]+dist(i,j)∗p[i]+q[i],dist(i,j)≤limt[i]}f[i]=min\{f[j]+dist(i,j)*p[i]+q[i],dist(i,j)\le limt[i]\} 用来对拍

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
namespace KISS
{
	void DP(int pos)
	{
		f[pos]=LLONG_MAX;
		int par=c[pos].fa;
		ll d=c[pos].s;
		while(par && d<=c[pos].lim)
		{
			if(chkmn(f[pos],f[par]+d*c[pos].k))
				pre[pos]=par;
			d+=c[par].s;
			par=c[par].fa;
		}
		if(pos!=1) f[pos]+=c[pos].b;
		else f[pos]=0;
		for(Edge *e=id[pos];e;e=e->pre)
			DP(e->to);
	}
	void Solve(){DP(1);}
}

40pts

考虑在序列上，无限制的情况。 f[i]=min{f[j]+dist(i,j)×p[i]+q[i]}=q[i]+min{f[j]+dist(i,j)×p[i]}f[i]=min\{f[j]+dist(i,j)\times p[i]+q[i]\}=q[i]+min\{f[j]+dist(i,j)\times p[i]\} 看起来很斜率优化。 设j<kj< k，kk优于jj当且仅当 f[j]+dist(i,j)×p[i]>f[k]+dist(i,k)×p[i]f[j]+dist(i,j)\times p[i]> f[k]+dist(i,k)\times p[i] 即 f[j]−len[j]×p[i]>f[k]−len[k]×p[i]f[j]-len[j]\times p[i]> f[k]-len[k]\times p[i] f[j]−f[k]>(len[j]−len[k])×p[i]f[j]-f[k]> (len[j]-len[k])\times p[i] 给定s>0s>0，所以len[]len[]递增，可以化为 f[j]−f[k]len[j]−len[k]<p[i]\dfrac {f[j]-f[k]}{len[j]-len[k]}< p[i] 维护一个下凸壳。 p[]p[]并不是递增的，所以不能用单调队列，需要用单调栈+二分。

Code

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
namespace NakedOptOnChain
{
	struct Node
	{
		ld slop;int id;
		Node(){}
		Node(ld slop,int id):slop(slop),id(id){}
		bool operator <(const Node &a)const{return fcmp(slop-a.slop)<0;}
		
	}Q[MAXN];int he,ta;
	void Solve()
	{
		//x坐标单调，k不单调，维护斜率下凸壳，二分查找
		static ll len[MAXN];
		for(int i=2;i<=n;++i) len[i]=len[i-1]+c[i].s;
		new(&Q[he=ta=1])Node(inf,1);
		#define transfer(j,i) (f[j]+(len[i]-len[j])*c[i].k+c[i].b) 
		#define slope(y,x) ((ld)(y)/(x))
		#define count(x,y) (y-x+1)
		for(int i=2;i<=n;++i)
		{
			int index=lower_bound(Q+he,Q+ta,Node((ld)c[i].k,0))-Q;
			int j=Q[index].id;
			f[i]=min(j!=0?transfer(j,i):LLONG_MAX,transfer(Q[ta].id,i));//j==0...
			while(count(he,ta)>=2 
			   && fcmp(Q[ta-1].slop-slope(f[i]-f[Q[ta].id],len[i]-len[Q[ta].id]))>=0) 
				ta--;
			Q[ta].slop=slope(f[i]-f[Q[ta].id],len[i]-len[Q[ta].id]);
			Q[++ta]=Node(inf,i);
		}
		#undef transfer
		#undef slope
		#undef count
	}
}

50pts

加上了路径限制。一开始的想法显然就是在单调栈中二分到第一个可以取到的位置，然后再二分查找最优位置，当时觉得应该不行，但也没想出反例。写出来之后WA，发现反例如下 所以这样是不行的。。 而CDQ分治恰好可以对区间的两半分别做一些操作而不影响答案，于是就CDQ分治 第一维，按照可以到最靠左的点排序；第二维，分治区间 在统计答案的时候，两个指针都从右向左走，维护满足距离限制的凸壳 回溯的时候按照标号的大小顺序归并

Code

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
namespace DCOnChain
{
	ll len[MAXN];
	struct Opt
	{
		int id;ll fr;
		bool operator <(const Opt &a) const{return fr<a.fr;}
	}p[MAXN],t[MAXN];
	bool CmpID(const Opt &a,const Opt &b){return a.id<b.id;}
	int Partition(int L,int R)
	{
		int Mid=(L+R)>>1,pl=L,pr=Mid+1;
		for(int i=L;i<=R;++i) t[p[i].id<=Mid?pl++:pr++]=p[i];
		copy(t+L,t+R+1,p+L);
		return Mid;
	}
	void Merge(int L,int Mid,int R)
	{
		merge(p+L,p+Mid+1,p+Mid+1,p+R+1,t+L,CmpID);
		copy(t+L,t+R+1,p+L);
	}
	struct Point
	{
		ll x,y;int id;
		Point(){}
		Point(int id):id(id)
		{
			x=len[id];
			y=f[id];
		}
		Point(ll x,ll y):x(x),y(y){}
		Point operator -(const Point &a)const{return Point(x-a.x,y-a.y);}
	}stack[MAXN];int top;
	ld Outer(Point a,Point b){return (ld)a.x*b.y-(ld)a.y*b.x;}//叉积爆ll没加强转ld..........
	ld Slope(Point a,Point b){return ((ld)a.y-b.y)/(a.x-b.x);}
	int BinarySearch(ll k)
	{
		if(!top) return 0;
		int L=1,R=top;
		while(L!=R)
		{
			int Mid=(L+R+1)>>1;
			if(Mid==1 || fcmp(Slope(stack[Mid],stack[Mid-1])-k)>=0) L=Mid;
			//stack[top]???....
			else R=Mid-1;
		}
		return stack[L].id;
	}
	ll transfer(int j,int i) {return (f[j]+(len[i]-len[j])*c[i].k+c[i].b);}
	void DC(int L,int R)
	{
		if(L==R) return;
		int Mid=Partition(L,R);
		DC(L,Mid);
		top=0;
		for(int pl=Mid,pr=R;pr>Mid;--pr)
		{
			int goal=p[pr].id;
			while(pl>=L && len[p[pl].id]>=p[pr].fr)
			{
				Point cur(p[pl].id);
				while(top>=2 && fcmp(Outer(stack[top]-stack[top-1],cur-stack[top]))>=0)//叉的顺序写反了 
					top--;
				stack[++top]=cur;
				pl--;
			}
			int best=BinarySearch(c[goal].k);
			if(best && chkmn(f[goal],transfer(best,goal))) pre[goal]=best;
		}
		DC(Mid+1,R);
		Merge(L,Mid,R);
	}
	void Solve()
	{
		for(int i=1;i<=n;++i)
		{
			len[i]=len[i-1]+c[i].s;	
			p[i].id=i;p[i].fr=len[i]-c[i].lim;
			f[i]=LLONG_MAX;
		}
		f[1]=0;
		sort(p+1,p+1+n);
		DC(1,n);
	}
}

100pts

这一步做法就非常妙了。 在树上要满足距离限制，也可以借鉴CDQ分治的思路，把用来更新的点和被更新的点隔离开，就可以分别进行一些操作 对树点分治，每层找重心，找到重心之后先把重心的父节点对应的子树DC，然后用从重心的父节点开始，沿着父指针一直走到当前层之外，用这条链上满足距离限制的点更新重心的答案，然后把重心也加进这条链。取出剩下的子树中的所有节点，再按照序列上的做法用那条链更新剩下的节点。

Code

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
namespace DCOnTree
{
	ll len[MAXN];
	bool ud[MAXN]={1};
	int sz[MAXN],dep[MAXN];
	struct Opt
	{
		int id;ll fr;
		Opt(){}Opt(int id,ll fr):id(id),fr(fr){}
		bool operator <(const Opt &a) const{return fr<a.fr;}
	}p[MAXN],t[MAXN];
	bool CmpID(const Opt &a,const Opt &b){return a.id<b.id;}

	struct Point
	{
		ll x,y;int id;
		Point(){}
		Point(int id):id(id){x=len[id];y=f[id];}
		Point(ll x,ll y):x(x),y(y){}
		Point operator -(const Point &a)const{return Point(x-a.x,y-a.y);}
	}stack[MAXN];int top;
	ld Outer(Point a,Point b){return (ld)a.x*b.y-(ld)a.y*b.x;}//叉积爆ll没加强转ld..........
	ld Slope(Point a,Point b){return ((ld)a.y-b.y)/(a.x-b.x);}
	void CalSize(int pos,int from)
	{
		sz[pos]=1;
		for(Edge *e=id[pos];e;e=e->pre)
		{
			int u=e->to;
			if(ud[u] || u==from) continue;
			CalSize(u,pos);
			sz[pos]+=sz[u];
		}
	}
	int DP(int pos,int from,int tol)
	{
		static int f[MAXN]={INT_MAX};
		int res=0,temp;f[pos]=0;
		for(Edge *e=id[pos];e;e=e->pre)
		{
			int u=e->to;
			if(ud[u] || u==from) continue;
			temp=DP(u,pos,tol);
			if(res==0 || f[res]>f[temp]) res=temp;
			chkmx(f[pos],sz[u]);
		}
		chkmx(f[pos],tol-sz[pos]-1);
		return f[res]<f[pos]?res:pos;
	}
	int Center(int rt)
	{
		CalSize(rt,0);
		return DP(rt,0,sz[rt]);
	}
	void Others(int pos,int from,Opt *p,int &pc)
	{
		if(!ud[pos]) p[++pc]=Opt(pos,len[pos]-c[pos].lim);
		for(Edge *e=id[pos];e;e=e->pre)
		{
			int u=e->to;
			if(ud[u] || u==from) continue;
			Others(u,pos,p,pc);
		}
	}
	int BinarySearch(ll k)
	{
		if(!top) return 0;
		int L=1,R=top;
		while(L!=R)
		{
			int Mid=(L+R+1)>>1;
			if(Mid==1 || fcmp(Slope(stack[Mid],stack[Mid-1])-k)>=0) L=Mid;
			//stack[top]???....
			else R=Mid-1;
		}
		return stack[L].id;
	}
	ll transfer(int j,int i) {return (f[j]+(len[i]-len[j])*c[i].k+c[i].b);}
	void DC(int pos)
	{
		if(!pos || ud[pos]) return;
		int gc=Center(pos);
		int above=gc;
		while(!ud[above]) above=c[above].fa; 
		ud[gc]=1;
		DC(c[gc].fa);//
		int pc=0,tc;//front..
		for(int cur=gc;cur!=above;cur=c[cur].fa)
		{
			p[++pc]=Opt(cur,len[cur]-c[cur].lim);
			if(cur!=gc && len[cur]>=p[1].fr && chkmn(f[gc],transfer(cur,gc))) pre[gc]=cur;
		}
		reverse(p+1,p+1+pc);

		Others(gc,0,t,tc=0);sort(t+1,t+1+tc);
		for(top=0;tc;tc--)
		{
			int goal=t[tc].id;
			while(pc && len[p[pc].id]>=t[tc].fr)
			{
				Point cur(p[pc--].id);
				while(top>=2 && fcmp(Outer(stack[top]-stack[top-1],cur-stack[top]))>=0)
				//if..........!!
					top--;
				stack[++top]=cur;
			}
			int best=BinarySearch(c[goal].k);
			if(best && chkmn(f[goal],transfer(best,goal))) pre[goal]=best;
		}
		for(Edge *e=id[gc];e;e=e->pre)
		{
			int u=e->to;
			if(!ud[u]) DC(u);
		}
	}
	void Prep()
	{
		memset(f,127,sizeof(f));f[1]=0;
		static int stack[MAXN],top;
		stack[top=1]=1;dep[1]=1;
		while(top)
		{
			int cur=stack[top--];
			for(Edge *e=id[cur];e;e=e->pre)
			{
				int u=e->to;
				if(dep[u]) continue;
				stack[++top]=u;
				dep[u]=dep[cur]+1;
				len[u]=len[cur]+c[u].s;
			}
		}
	}
	void Solve()
	{
		Prep();
		DC(1);
	}
}

Solution

这是第二次做到考算法新推广的题 第一次是用替罪羊思想维护动态点分治 做不出来甚至看不懂题解说明这种算法本身就学的不扎实 以后再碰到这种情况也应该像这样写出退化版问题的程序，可以加深对原算法和推广的算法的理解

Code

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
169
170
171
172
173
174
175
176
177
178
179
180
181
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define get64(x) scanf("%lld",&x)
#define put64(x) printf("%lld",x)
typedef long long ll;
typedef long double ld;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::lower_bound;
using std::min;
using std::copy;
using std::sort;
using std::merge;
using std::greater;
using std::reverse;

const int MAXN=2e5+11;
const ld eps=1e-5,inf=1e100;
inline int fcmp(ld x){return -eps<x && x<eps?0:(x<0?-1:1);}
struct City
{
	int fa;ll s,k,b,lim;
}c[MAXN];int n;
ll f[MAXN];
struct Edge
{
	Edge *pre;int to;
	Edge(Edge *pre,int to):pre(pre),to(to){}
	void *operator new(size_t);
}*Edge_Me=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*id[MAXN];
void *Edge::operator new(size_t){return Edge_Me++;}
void Adde(int x,int y){id[x]=new Edge(id[x],y),id[y]=new Edge(id[y],x);}

ll len[MAXN];
bool ud[MAXN]={1};
int sz[MAXN];
struct Opt
{
	int id;ll fr;
	Opt(){}Opt(int id,ll fr):id(id),fr(fr){}
	bool operator <(const Opt &a) const{return fr<a.fr;}
}p[MAXN],t[MAXN];
bool CmpID(const Opt &a,const Opt &b){return a.id<b.id;}

struct Point
{
	ll x,y;int id;
	Point(){}
	Point(int id):id(id){x=len[id];y=f[id];}
	Point(ll x,ll y):x(x),y(y){}
	Point operator -(const Point &a)const{return Point(x-a.x,y-a.y);}
}stack[MAXN];int top;
ld Outer(Point a,Point b){return (ld)a.x*b.y-(ld)a.y*b.x;}//叉积爆ll没加强转ld..........
ld Slope(Point a,Point b){return ((ld)a.y-b.y)/(a.x-b.x);}
void CalSize(int pos,int from)
{
	sz[pos]=1;
	for(Edge *e=id[pos];e;e=e->pre)
	{
		int u=e->to;
		if(ud[u] || u==from) continue;
		CalSize(u,pos);
		sz[pos]+=sz[u];
	}
}
int DP(int pos,int from,int tol)
{
	static int f[MAXN]={INT_MAX};
	int res=0,temp;f[pos]=0;
	for(Edge *e=id[pos];e;e=e->pre)
	{
		int u=e->to;
		if(ud[u] || u==from) continue;
		temp=DP(u,pos,tol);
		if(res==0 || f[res]>f[temp]) res=temp;
		chkmx(f[pos],sz[u]);
	}
	chkmx(f[pos],tol-sz[pos]-1);
	return f[res]<f[pos]?res:pos;
}
int Center(int rt)
{
	CalSize(rt,0);
	return DP(rt,0,sz[rt]);
}
void Others(int pos,int from,Opt *p,int &pc)
{
	if(!ud[pos]) p[++pc]=Opt(pos,len[pos]-c[pos].lim);
	for(Edge *e=id[pos];e;e=e->pre)
	{
		int u=e->to;
		if(ud[u] || u==from) continue;
		Others(u,pos,p,pc);
	}
}
int BinarySearch(ll k)
{
	if(!top) return 0;
	int L=1,R=top;
	while(L!=R)
	{
		int Mid=(L+R+1)>>1;
		if(Mid==1 || fcmp(Slope(stack[Mid],stack[Mid-1])-k)>=0) L=Mid;
		//stack[top]???....
		else R=Mid-1;
	}
	return stack[L].id;
}
ll transfer(int j,int i) {return (f[j]+(len[i]-len[j])*c[i].k+c[i].b);}
void DC(int pos)
{
	if(!pos || ud[pos]) return;
	int gc=Center(pos);
	int above=gc;
	while(!ud[above]) above=c[above].fa; 
	ud[gc]=1;
	DC(c[gc].fa);//
	int pc=0,tc;//front..
	for(int cur=gc;cur!=above;cur=c[cur].fa)
	{
		p[++pc]=Opt(cur,len[cur]-c[cur].lim);
		if(cur!=gc && len[cur]>=p[1].fr) chkmn(f[gc],transfer(cur,gc));
	}
	reverse(p+1,p+1+pc);

	Others(gc,0,t,tc=0);sort(t+1,t+1+tc);
	for(top=0;tc;tc--)
	{
		int goal=t[tc].id;
		while(pc && len[p[pc].id]>=t[tc].fr)
		{
			Point cur(p[pc--].id);
			while(top>=2 && fcmp(Outer(stack[top]-stack[top-1],cur-stack[top]))>=0)
				top--;
			stack[++top]=cur;
		}
		int best=BinarySearch(c[goal].k);
		if(best) chkmn(f[goal],transfer(best,goal));
	}
	for(Edge *e=id[gc];e;e=e->pre)
	{
		int u=e->to;
		if(!ud[u]) DC(u);
	}
}
void Prep()
{
	memset(f,127,sizeof(f));f[1]=0;
	static int stack[MAXN],top;
	stack[top=1]=1;
	while(top)
	{
		int cur=stack[top--];
		for(Edge *e=id[cur];e;e=e->pre)
		{
			int u=e->to;
			if(len[u] || u==1) continue;
			stack[++top]=u;
			len[u]=len[cur]+c[u].s;
		}
	}
}
int main()
{
	int t;get(n),get(t);
	for(int i=2;i<=n;++i)
	{
		get(c[i].fa);
		get64(c[i].s);
		get64(c[i].k),get64(c[i].b);
		get64(c[i].lim);
		Adde(c[i].fa,i);	
	}
	Prep();
	DC(1);
	for(int i=2;i<=n;++i)
		put64(f[i]),putchar('\n');
	return 0;
}