Codeforces 掉分日常(六):最小生成树与飞行棋

Codeforces 掉分日常之 1245D/E

昨晚继续掉分...... D 题乍一看没啥思路,E 题秒想了一个解,但细节上差了一点,写完过不了样例,找了半天不知道哪错了,于是自闭了。从分奴的角度看,应该上来先看看 D 和 E 可不可做,然后 E 卡住的时候(还剩一小时)赶紧改开 D 题,可能还有点机会。不过一力破十会,还是多练练下次把他们都秒了比较靠谱。

这篇博客记录一下 D 和 E 吧,都是不错的问题。

D - Shichikuji and Power Grid

题意:平面上有 N 个点(城市),现在要给他们通电。除位置 x_i,y_i 外,每个城市还有两个值:c_i 和 d_i。城市要通电有两种办法:建一个发电站,代价为c_i;或者与已通电的城市连一根线,代价为 (d_i+d_j)*dist(i, j),其中 dist 表示 i 与 j 间的曼哈顿距离。问最小的总代价。数据范围 N

乍一想,由于每两个城市间都可以连线,而且代价与这两个城市的距离、d 值都有关,因此每个城市的选择空间都非常多,似乎难以下手。(我这时候就开 E 题去了并掉在了 E 题的坑里)

一般来说这种时候就需要贪心一下。稍微模拟一下可以发现,最终的结果一定是若干棵树,每棵树上恰好有一个发电站。对于每棵树来说,建这棵树的边所需要的成本是固定的,因此发电站一定建在这棵树上 c 最小的那条边上。因此,即使我们暂时很难确定哪些点组成树,树上怎么连边,但可以确定 c 最小的那个点上一定建了一个发电站。

接下来有一种很巧妙的思路:将每个点的 c 值更新为原来 c 和与当前点的距离的较小值,也就是 c_j = min(c_j, (d_i+d_j)*dist(i, j)),然后问题就化为了规模较小的子问题,可以递归求解。输出答案的时候,需要看每个点用的 c 值到底是原来的,还是与某个点的距离的较小值更新后的,分别输出建站或连线。其实也不能说有多巧妙,思想上是与最小生成树的 Kruskal 算法类似的。

本题还有一种解法:直接建立一个 0 号虚节点,与每个点连边,权值是 c_i;然后每个点之间的边的权值就是他们连线的代价。不难发现问题的答案就是整张图从 0 节点开始的最小生成树,用 prim 算法就可以直接求解。这种方法看上去一句话搞定,实际上不好想到。

本质上,这题就是一个最小生成树,但数据上除了边的权值还多了一个点的权值,乍一看比较恐怖。都说图论的算法本质都是贪心,但只有对 Kruskal 和 Prim 的两种贪心的思路有一些感性的理解,才能在面对变体的问题时游刃有余。

参考代码:64341288

 

E - Hyakugoku and Ladders

题意:飞行棋,问到达终点的期望是掷多少次骰子。细节比较多,大概有两个难点:有一些可以往上跳的梯子,梯子可以向上爬或不想上爬,需要 optimally 地选择;最后几格的时候如果 roll 到超过长度的数字会原地不动。

概率和期望的 dp 一般挺简单的,这次却自闭了。赛后过了一天才想明白,因此现在简单理一下思路。

首先这个问题有两种可能的思路:倒着推或者正着推。正解是要倒着推,但一开始也看不出正着推走不通,所以我们都写写看:

正着推的思路是这么想的:首先一个 dp[] 数组表示跳到第 i 个格子的期望步数。但我们会发现从第二个格子开始,到倒数第二格,到达这个格子的概率都是不同的,而这个概率对后面的期望有影响。因此还需要一个 p[] 数组表示每个格子到达的概率。梯子很好解决,统计一下每个梯子的 to[] 即可。边界条件比较难想,由于最后几格会有原地不动的概率。

倒着推其实比较简单:直接 dp[] 表示每个格子到终点还有多少步。这样不用考虑每个点到达的概率,直接瞎搞一波即可。

无论正着推、倒着推,其实列出 dp 式子只是这个题目的第一步。题目的第二步是要判断每个梯子要不要走。根据样例 3 可以看出,某一个梯子是否需要使用是和别的梯子有关的,因为那个 1 的梯子从前面的信息上看是要走,但如果走这个梯子,就错过了后面的几个 6 的梯子,所以 optimally 的选择应该是不走。

我最终采用的方法类似退火,反复尝试每个梯子是否需要往上走,也就是跳 to[] 或不跳 to[] 对结果的最终影响。对于不需要往上走的梯子,有可能在别的梯子更新后又需要往上走,因此需要循环足够多次(按照最坏复杂度算应该要 次左右,实际上 100 次就 AC 了)。如果是倒着推的 dp 做法,则可以O(n^2)地一遍推出来,这里不再详述。

参考代码,写的比较挫:64069972