题解
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;
}