CodeForces

Luogu

分析

一道很神仙的图论题。

首先转化一下题意(来自 $\mathsf{\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}$ 即可。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

const int N=200+10;
const int M=N*N;

int n;
double p[N];
struct Edge { int v,nxt; double w; } e[M];
int head[N];

inline void addEdge(int u,int v,double w) {
    static int cnt=0;
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

double dis[N];
int inq[N],cnt[N];

inline int check(double mid) {
    memset(dis,0xdd,sizeof(dis)),memset(inq,0,sizeof(inq)),memset(cnt,0,sizeof(cnt));
    queue<int> Q; Q.push(1); dis[1]=0,inq[1]=1,cnt[1]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; double w=e[i].w-mid;
            if (dis[u]+w>dis[v]) {
                dis[v]=dis[u]+w,cnt[v]=cnt[u]+1;
                if (cnt[v]>n*2) return 1;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d",&n);
    for (re int i=0;i<=n;++i) scanf("%lf",&p[i]);
    for (re int i=0;i<=n*2;++i)
        for (re int j=0;j<=n*2;++j) {
            int dlt=i-j;
            if (dlt>=-n&&dlt<=n&&(dlt&1)==(n&1))
                addEdge(i,j,p[(n+i-j)/2]);
        }
    double L=0,R=1;
    while (R-L>1e-8) {
        double mid=(L+R)/2;
        if (check(mid)) L=mid;
        else R=mid;
    }
    printf("%.10lf\n",L);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 12 PM