QOJ8008 MIPT Yolki-Palki Contest 1 F. Fortune Wheel

题解

1.题目

QOJ8008

2.思路

考虑贪心

首先，我们发现，肯定是先瞬移，再移动

因为如果在移动后瞬移那么移动就没有作用了，相当于重新开始了

那么我们可以把操作次数分为两部分：瞬移+移动

那我们将每个点到0最短需要走多少步 $dis$ bfs预处理出来

然后将 $dis$ 从小到大排序

为什么排序

因为我们还要枚举一个 $i$ ，表示所有距离大于 $dis_i$ 的数都先瞬移到距离小于等于 $dis_i$ 的数再移动到0。

排序后才能让距离最优

那么期望怎么算

先算瞬移的期望 ：

首先，列式子（j是移动步数（代价），后面的都是概率）：

$$
\sum_{j=1}^{\infty} j\left(\frac{n-i}{n}\right)^{j-1}\frac{i}{n}
$$

将 $\left(\frac{n-i}{n}\right)^{j-1}$ 视为常数，记为 $x$，则上式可以重写为：

$$
\frac{i}{n}\sum_{j=1}^{\infty} j x^{j-1}
$$

这是一个常见的等比数列求和，其和为：

$$
\frac{i}{n}\cdot \frac{1}{(1-x)^2}
$$

将 $x$ 恢复为 $\left(\frac{n-i}{n}\right)$，得到最终结果：

$$
\frac{i}{n}\cdot \frac{1}{\left(1-\frac{n-i}{n}\right)^2}

\frac{i}{n}\cdot \frac{1}{\left(\frac{i}{n}\right)^2}

\frac{n}{i}
$$

因此，经过推导求证，我们得到了结论：

$$
\sum_{j=1}^{\infty} j\left(\frac{n-i}{n}\right)^{j-1}\frac{i}{n}

\frac{n}{i}
$$

移动的期望也是同理 ：

列出式子：

$$
\sum_{j=1}^{\infty} (\sum_{k=1}^{i}{dis_k})\left(\frac{n-i}{n}\right)^{j-1}\frac{i}{n}
$$

因为还是等差数列的形式，同理给出式子：

$$
\frac{\sum_{j=1}^{i}{dis_j}}{i}
$$

加在一起即为当前的答案
最后所有 $i$ 算出的答案取个min就行了qoj

3.Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed n,x,k;long long a[200010],dis[200010];
vector<int>e[200010];
pair<int,int>ans;vector<pair<int,int>>sz;
main(){
    cin>>n>>x>>k;
    for(int i=1;i<=k;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        for(int j=1;j<=k;j++){

            e[(i+a[j])%n].push_back(i);
        }
        dis[i]=2e9;
    }

    queue<int>q;
    q.push(0);
    dis[0]=0;
    while(q.size()){
        int u=q.front();
        //cout<<u<<endl;
        q.pop();
        for(auto v:e[u]){
            if(dis[u]+1<dis[v]){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    int sum=0;
    for(int i=0;i<n;i++)sz.push_back({dis[i],i});
    sort(sz.begin(),sz.end());
    for(int i=0;i<n;i++){
        //cout<<dis[i]<<' ';
        sum+=sz[i].first;
        if(sz[i].first>n)break;
        int tag=0;
        if(x==sz[i].second)tag=1;
        if(tag==1){

            if(ans.second==0)ans={sz[i].first,1};
            else{
                if(ans.first*(1)>(sz[i].first)*ans.second){
                    ans={sz[i].first,1};
                }
            }
        }else{
            if(ans.second==0)ans={sum+n,i+1};
            else{
                if(ans.first*(i+1)>(sum+n)*ans.second){
                    ans={sum+n,i+1};
                }
            }
        }
        if(tag)break;
        //cout<<ans.first<<" "<<ans.second<<'\n';
    }
    int tmp=__gcd(ans.first,ans.second);
    ans.first/=tmp;
    ans.second/=tmp;
    cout<<(long long)ans.first<<" "<<(long long)ans.second;
    return 0;
}