POI18~20部分题(tu)解(cao)

bzoj2035:[2009国家集训队]数据读取问题 意识流题解

Recursion posted @ 2015年2月25日 20:37 in 题解 with tags BFS 图论 并查集 bzoj , 739 阅读

之所以写这题题解是因为它有种POI鬼畜图论题的感觉...

 

题意

题目能一遍看懂的举下手...

先不管题目是干啥的你TM扯一堆平行宇宙,薛定谔的猫是在干啥啊...

翻译:

有一棵带点权的树,对每条从根到叶子节点的链,进行以下操作:

1.花费1的代价进入下一个节点。

2.若当前节点的值为[tex]a_i[/tex],花费[tex]d[/tex]的代价向前走[tex]{a_i}+d[/tex]或[tex]{a_i}-d[/tex]的节点,必须保证后面有这么多节点且不能后退。

3.若还有节点,重复1,否则结束。

最小化代价。

题解

既然是要球每条链,那么先来分析一条链的情况。

首先在结尾添加一个[tex]n+1[/tex]号节点(其实加不加无所谓)

然后[tex]O({n^2})[/tex]的动态规划很好想。

然后把i提取出来发现可以用线段树优化到[tex]O(n \log n)[/tex]。

当然其实有线性做法。我们假设直接走[tex]a_i[/tex]个单位然后再调整。

于是构造有向图,i向[tex]i+{a_i}+1[/tex]连权值为1的边,同时向[tex]i-1[/tex]和[tex]i+1[/tex]页连一条权值为1的边。

然后我们发现直接半斧神bfs搞出最短路就行了...

直接把前面bfs的做法搬过来会发现不行是因为连的边数可能达到平方级别。所以要考虑优化。

我们球出树的bfs序,容易发现每个节点连出去的节点一定是连续的一段。

于是可以并查集维护,bfs时每次找一个未访问过的节点就行了。

时间复杂度[tex]O(n \alpha(n))[/tex]

 

非常搞笑的是清澄上面时限开的是1s,就连标程都跑不过去,居然有人能AC我也是醉了...

 

 

AP 10th Gk Model Pap 说:
2022年9月11日 18:49

General Knowlorge is most important subject to all Class 10 students studying in English Medium, AP 10th Gk Model Paper Telugu Medium & Urdu Medium of the State Board. So every student who is studying in the state Government & Private Schools can download the AP 10th GK Model Paper 2023 Pdf with answer solutions designed and suggested by subject experts. General Knowlorge is most important subject to all Class 10 students studying in English Medium.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter