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

之所以写这题题解是因为它有种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我也是醉了...