题解 CF97C 【Winning Strategy】

2019-04-16 19:07:42


一道很神仙的图论题。

首先转化一下题意(来自 $\mathrm{\color{black}{I}\color{red}{tst}}$ 的 $\mathrm{blog}$ ):

给出 $n$ 与一个范围在 $[0,1]$ 内的递增序列 $P_0\sim P_n$ ,试构造一个无穷序列 $\{a_i\}$ 满足 $0\leq a_i\leq n$ ,使得对于任意 $k>0$ 满足 $a_k \leq \sum\limits_{i=1}^{k-1}(n - 2a_i)$ 且极限 $\large\lim\limits_{m \rightarrow +\infty} \frac{\sum\limits_{i=1}^mp_{a_i}}{m}$ 达到最大,求出这个最大值。

显然我们不能直接构造 $a$ 。那么考虑构造一个 $a$ 的平均值最大的循环节。

假设当前在考虑 $a_k$ 。设 $Q=\sum\limits_{i=1}^{k-1}(n-2a_i)$ 。那么对于 $a_k$ ,它会造成 $p_{a_k}$ 的贡献,并使得 $Q$ 增大 $n-2a_k$ 。

考虑一个等价的问题:有一个空箱子,第 $i$ 次拿出 $a_i$ 个物品并放进 $n-a_i$ 个物品,求 $\large\lim\limits_{m\to+\infty}\frac{\sum\limits_{i=1}^mp_{a_i}}{m}$ 的最大值。

显然选择的 $a$ 只和 $Q$ 有关,于是将 $Q$ 的值作为点,决策的转换作为边,建出一个图。那么图中平均边权最大的环就是要找的循环节。

然后,实际上有用的点只有 $0\sim 2n$ 。

至于怎么找这个环?二分+ $\mathrm{SPFA}$ 即可。

具体实现及细节见代码