关键词:
【BZOJ3672】[Noi2014]购票
Description
Input
第 1 行包含2个非负整数 n,t,分别表示城市的个数和数据类型(其意义将在后面提到)。输入文件的第 2 到 n 行,每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v,分别表示城市 v 的父亲城市,它到父亲城市道路的长度,票价的两个参数和距离限制。请注意:输入不包含编号为 1 的SZ市,第 2 行到第 n 行分别描述的是城市 2 到城市 n。
Output
输出包含 n-1 行,每行包含一个整数。其中第 v 行表示从城市 v+1 出发,到达SZ市最少的购票费用。同样请注意:输出不包含编号为 1 的SZ市。
Sample Input
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10
Sample Output
150
70
149
300
150
HINT
对于所有测试数据,保证 0≤pv≤106,0≤qv≤1012,1≤fv<v;保证 0<sv≤lv≤2×1011,且任意城市到SZ市的总路程长度不超过 2×1011。
输入的 t 表示数据类型,0≤t<4,其中:
当 t=0 或 2 时,对输入的所有城市 v,都有 fv=v-1,即所有城市构成一个以SZ市为终点的链;
当 t=0 或 1 时,对输入的所有城市 v,都有 lv=2×1011,即没有移动的距离限制,每个城市都能到达它的所有祖先;
当 t=3 时,数据没有特殊性质。
n=2×10^5
题解:做这种题就怕突然灵光一现,然后自己yy了一发,到对拍1w组的时候才发现自己的做法完全GG,于是只好重写。。。
先分享一下做这道题的思路(前置技能:BZOJ1492货币兑换),如果着急和MM约会,可以直接看最后两段。
——————————————从此处开始略过——————————————
蒟蒻的独白:“不就是将cdq分治换成树分治嘛,有什么难的?这式子也太水了:用dep[i]表示根到i的距离,f[i]表示从i到根的最小购票费用,显然 $f[i]=min(f[j]+(dep[i]-dep[j])*p[i]+q[i]) \rightarrow f[j]=dep[j]*p[i]+f[i]-q[i]-dep[i]*p[i]$ 式子都推出来了,搞呗!当我们以x为分治中心时,可选的i就是x子树中的所有点,可选的j就是根到i路径上的所有点(当然要满足i,j的距离<=li啦~),然后我就先递归分治x的父亲的那部分(在有根树中好像这个不能叫子树吧?),然后将x到根路径上的所有的点都拎出来维护个凸包,枚举x子树中的所有点,然后每个点都在那个凸包上二分一下,就完事啦!WA。 “突然发现,我们在搞凸包的时候,会丢掉很多点,新加入一些深度更小的点,但是由于有距离限制,这些深度更小的点不能更新x子树中的一些点,于是,这就要求我们将x子树中的点也都拎出来,一起搞。 “思路来了,我们将x到根路径上的所有点都用数组A存起来,x子树中的点都用数组B存起来,并按照(dep-l)排好序,那么我们同时扫这两个数组,边维护凸包边二分更新答案,感觉很棒!WA。 “惊讶的发现!x居然是降序的!无可奈何,重新搞。WA。 “1w组对拍都过了?woc用叉积会爆long long!无可奈何,用double。AC。”
————————————————省略结束————————————————
总结一下全过程(翻译一下代码):
1.当我们以x为分治中心时,先从网上一直延伸直到第一个已经访问过的节点,然后将这个最高点记录下来(一会才用!),然后分治处理x的父亲那部分
2.处理完父亲后,我们将从x到那个最高点的路径上的点都拎出来扔到数组A中,再DFSx的子树中的点,放到B中,并按dep-l从大到小排序。
3.同时扫A和B,进行斜率优化
4.分治处理x的子树
本人的代码不可读性还是比较高的,WA的同学请注意:在我们拎出x子树中的点时,就算访问到之前被标记过(做过分治中心)的点时也要将它放入数组中更新,只是不继续延伸下去。
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include <algorithm> #define x(_) (dep[_]) #define y(_) (f[_]) using namespace std; const int maxn=200010; typedef long long ll; int n,m,cnt,maxx,tot,root; int fa[maxn],siz[maxn],to[maxn],next[maxn],head[maxn],A[maxn],st[maxn],vis[maxn],B[maxn]; ll val[maxn],dep[maxn],len[maxn],p[maxn],q[maxn],lim[maxn],f[maxn]; ll rd() { ll ret=0; char gc=getchar(); while(gc<'0'||gc>'9') gc=getchar(); while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret; } bool cmp(int a,int b) { return dep[a]-lim[a]>dep[b]-lim[b]; } void add(int a,int b) { to[cnt]=b,next[cnt]=head[a],head[a]=cnt++; } void getr(int x,int fa) { siz[x]=1; int i,mx=0; for(int i=head[x];i!=-1;i=next[i]) { if(vis[to[i]]||to[i]==fa) continue; getr(to[i],x),siz[x]+=siz[to[i]],mx=max(mx,siz[to[i]]); } if(maxx>max(mx,tot-siz[x])) maxx=max(mx,tot-siz[x]),root=x; } void getB(int x) { B[++B[0]]=x; if(vis[x]) return ; for(int i=head[x];i!=-1;i=next[i]) getB(to[i]); } double getk(int a,int b) { if(x(a)==x(b)) return 1e15*(y(a)>y(b)?1.0:-1.0); else return (double)(y(a)-y(b))/(x(a)-x(b)); } void calc(int x) { if(!m) return ; int mid,l=1,r=m; double k=p[x]; while(l<r) { mid=l+r>>1; if(getk(A[mid],A[mid+1])>k) l=mid+1; else r=mid; } f[x]=min(f[x],f[A[l]]+(dep[x]-dep[A[l]])*p[x]+q[x]); } void dfs(int x) { vis[x]=1; int i,j,top=x; while(top!=1&&!vis[fa[top]]) top=fa[top]; if(x!=top) maxx=1<<30,tot=siz[top]-siz[x],getr(top,0),dfs(root); if(top!=1) top=fa[top]; st[st[0]=1]=x; while(st[st[0]]!=top) st[st[0]+1]=fa[st[st[0]]],st[0]++; for(B[0]=0,i=head[x];i!=-1;i=next[i]) getB(to[i]); sort(B+1,B+B[0]+1,cmp); for(m=0,i=1,j=1;i<=st[0];i++) { for(;j<=B[0]&&dep[st[i]]<dep[B[j]]-lim[B[j]];j++) calc(B[j]); while(m>1&&getk(A[m-1],A[m])<=getk(A[m],st[i])) m--; A[++m]=st[i]; } for(;j<=B[0];j++) calc(B[j]); for(i=head[x];i!=-1;i=next[i]) if(!vis[to[i]]) maxx=1<<30,tot=siz[to[i]],getr(to[i],x),dfs(root); } int main() { n=rd(),rd(); int i; memset(head,-1,sizeof(head)); for(i=2;i<=n;i++) { fa[i]=rd(),len[i]=rd(),p[i]=rd(),q[i]=rd(),lim[i]=rd(); add(fa[i],i); dep[i]=dep[fa[i]]+len[i]; } memset(f,0x3f,sizeof(f)),f[1]=0; maxx=1<<30,tot=n,getr(1,0),dfs(root); for(i=2;i<=n;i++) printf("%lld\n",f[i]); return 0; }
bzoj3672:[noi2014]购票
斜率优化+树分治。点分治:找出当前子树的重心,分治根到重心这一段,更新根到重心这一段的值,将剩下的点按能到达的高度从低到高排序,更新。分治其他子树。#include<cstdio>#include<algorithm>#include<cstring>#defineLLl... 查看详情
bzoj3672[noi2014]购票斜率优化+cdq分治+树的点分治
题目描述 给出一棵以1为根的带边权有根树,对于每个根节点以外的点$v$,如果它与其某个祖先$a$的距离$d$不超过$l_v$,则可以花费$p_vd+q_v$的代价从$v$到$a$。问从每个点到1花费的最小代价(中途可以经停其它点)输入第1行包... 查看详情
●bzoj3672[noi2014]购票
题链:http://www.lydsy.com/JudgeOnline/problem.php?id=3672 题解:斜率优化DP,点分治(树上CDQ分治...) 这里有一个没有距离限制的简单版:BZOJ1767[Ceoi2009]harbingers定义$DP[i]$为从i出发到1号点的最小花费,$dis_i$为i到1号点的距离:转移:... 查看详情
bzoj3672noi2014购票
这题好神啊..好神啊...好神啊...首先列出N2的DP方程较易.从DP方程很容易看出来是斜率优化.如何进一步优化?考虑对当前点以上的链建立一个下凸包.维护凸包就可以,但不是很好写.观察到方程可以必然由它的祖先节点转移.很像Cash... 查看详情
bzoj3672[noi2014]购票
推一下式子发现就是普通的斜率优化,但是放到了树上,那么我们怎么做呢,树上有什么能保证复杂度的求路径的算法呢,点分治!但是这是有根树,我们对于首先处理点分治后的重心以及与根相连的那个块,之后我们将块中剩... 查看详情
bzoj3672uoj#7noi2014购票
http://www.lydsy.com/JudgeOnline/problem.php?id=3672http://uoj.ac/problem/7链上的情况可以用斜率优化dp。树上用斜率优化dp时,单调队列的复杂度是均摊$O(n)$的,所以放到树上做“可持久化单调队列”复杂度是$O(n^2)$的,所以不能树上斜率... 查看详情
bzoj3672购票点分治+dp
3672:[Noi2014]购票TimeLimit: 30Sec MemoryLimit: 512MBSubmit: 1177 Solved: 562[Submit][Status][Discuss]Description 今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国n个城市的OIer们都会从 查看详情
bzoj3672:[noi2014]购票(树形dp+斜率优化+可持久化凸包)
这题的加强版,多了一个$l_i$的限制,少了一个$p_i$的单调性,难了好多... 首先有方程$f(i)=min{f(j)+(dep_i-dep_j)*p_i+q_i}$ $frac{f(j)-f(k)}{dep_j-dep_k}<p_i$ 假如没有$l_i$的限制,实际上就是上面那题... 如果多了$l_i$的限... 查看详情
bzoj3672/luogu2305购票(运用点分治思想的树上cdq分治+斜率优化dp)(代码片段)
我们都做过一道题(?)货币兑换,是用cdq分治来解决不单调的斜率优化现在它放到了树上..总之先写下来dp方程,$f[i]=minf[j]+(dis[i]-dis[j])*p[i]+q[i],j是i的祖先,dis[i]-dis[j]<=l[i]$,其中dis[i]表示1号点到i号点的距离可以很明显的看出... 查看详情
bzoj3672:[noi2014]购票
Description今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国n个城市的OIer们都会从各地出发,到SZ市参加这次盛会。全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的n... 查看详情
bzoj3672/uoj7[noi2014]购票
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。 本文作者:ljh2000作者博客:http://www.cnblogs.com/ljh2000-jump/转载请注明出处,侵权必究,保留最终解释权! Description ... 查看详情
noi2014购票
传送门另一个传送门这题劲啊……其实这题题解应该都烂大街了,不过我还是想大概写一下……就当是留作以后复习用也好……$t=0$的斜率优化很好搞。到了$t=1$的情况时,每个点都有转移区间的限制,做法大致就有线段树维护... 查看详情
bzoj1492[noi2007]货币兑换cashcdq分治+斜率优化dp
1492:[NOI2007]货币兑换CashTimeLimit: 5Sec MemoryLimit: 64MBSubmit: 5541 Solved: 2228[Submit][Status][Discuss]Description小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券 查看详情
[bzoj1492][noi2007]货币兑换cash(斜率优化+cdq分治)
1492:[NOI2007]货币兑换CashTimeLimit:5Sec MemoryLimit:64MBSubmit:5838 Solved:2345[Submit][Status][Discuss]Description小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和B纪念券(以下简称B... 查看详情
bzoj3672uoj#6noi2014随机数生成器
暴力出奇迹原题:2≤N,M≤50000≤Q≤500000≤a≤3000≤b,c≤1080≤x0<d≤1081≤ui,vi≤N×M 恩首先容易看出来这个棋盘直接模拟搞出来就行了,不用反演矩阵乘之类的奇怪的东西然后又容易发现只需要遍历从1~n*m的数尽量答案里塞就... 查看详情
bzoj1492[noi2007]货币兑换cash斜率优化+cdq分治
【BZOJ10492】[NOI2007]货币兑换CashDescription小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和B纪念券(以下简称B券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个... 查看详情
[noi2014]购票---斜率优化+树形dp+数据结构(代码片段)
题目描述今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国n个城市的OIer们都会从各地出发,到SZ市参加这次盛会。全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的n... 查看详情
[bzoj1492][noi2007]货币兑换cash(cdq分治+斜率优化dp)
Description小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和B纪念券(以下简称B券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波... 查看详情