HDU多校7 - 6853 Jogging(bfs+结论)

题目链接：点击查看

题目大意：在二维平面中有一个点 ( x , y ) ，规定 “ 好点 ” 的定义是，gcd( x , y ) > 1 ，现在从点 ( x , y ) 开始，每一次都能等概率的选择：

去周围八个方向中的“好点”

停留在原地不动

现在问在走无穷多次步数后，能够从点 ( x , y ) 出发再回到点 ( x , y ) 的概率是多少

题目分析：比赛时稍微打了个表，感觉是暴力bfs出所有点然后计算答案，主要是答案不会计算，就放掉了，因为 1e12 以内的相邻两个素数之差最大也不过几百，对应到二维平面中最多也就只有几万个点，所以可以暴力bfs出所有点

关于答案的计算，是一个结论，题解说的是“图上随机游走”算法，但我找不到相关博客去学习，无奈只能背过结论以防以后再遇到了

结论就是在建出无向图后，答案就是 “起点的度数 + 1 ” 除以 “总度数 + n”

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;const int b[8][2]={0,1,0,-1,1,0,-1,0,1,1,-1,-1,-1,1,1,-1};set<pair<LL,LL>>vis;void bfs(LL x,LL y) {int ans1=0,ans2=0;queue<pair<LL,LL>>q;q.emplace(x,y);vis.emplace(x,y);while(q.size()){tie(x,y)=q.front();q.pop();if(x==y)//如果遍历到对角线的话，答案为0/1 {ans1=0,ans2=1;break;}ans2++;//统计有多少个点:ans2中的+n for(int i=0;i<8;i++){LL xx=x+b[i][0];LL yy=y+b[i][1];if(__gcd(xx,yy)==1)continue;ans2++;//记录度数if(vis.count(make_pair(xx,yy)))continue;vis.emplace(xx,yy);q.emplace(xx,yy); }if(!ans1)//记录(起点度数+1)的答案 ans1=ans2;}int gcd=__gcd(ans1,ans2);ans1/=gcd,ans2/=gcd;printf("%d/%d\n",ans1,ans2); }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){LL x,y;scanf("%lld%lld",&x,&y);bfs(x,y);}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU多校7 - 6853 Jogging(bfs+结论)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。