maven package golang tsql kubernetes dynamic hyperlink pip ios7 routing bootstrap后台管理 jquery通过class获取元素 matlab读取dat文件 mysql重新初始化 查看oracle连接数 android常用布局 git登陆命令 less比较级 Navicat mysql时间戳转时间 python界面 python算法 python变量定义 python如何调用函数 python获取字典的值 python设置环境变量 java时间 java中的多态 java判断文件是否存在 java获取文件 linux磁盘管理 删除数组中的某个元素 dep dnf刷什么图赚钱 gg修改器下载 骰子动态图 华为动态照片 黑客攻防技术宝典 批处理for appsync补丁
当前位置: 首页 > 学习教程  > 编程语言

2020杭电多校第7场1010 Jogging

2020/8/11 18:43:25 文章标签:

题目链接:这里

题意:

​ 题目乍一看有点复杂,二维平面上的点(x, y),如果gcd(x, y) > 1则说明这个点good,good的点意思是可到达的(初始点是good的)。对任意一个good的点,假设它相邻一圈8个点中有zz个点是good的,那么从这点出发,下一步到这z个点以及停留的概率是一样的。即停留起始点的概率是1z+1\frac{1}{z+1},到其他z个good点中任意一点的概率也是1z+1\frac{1}{z + 1}。求经过 t 步后仍在原点的概率,用分数表示,t足够大。

分析:

​ t 足够大的意思是,如果在给出的初始点中,如果存在无限个good点连通,那么在走数量足够大的次数后,回到起始点的概率是0。因为存在无数多个点是可以停留的,t 足够大后分母就是无穷大,分子1是原点,那么这个答案就是0。而已试着将例子作一下图,比较容易发现,存在无穷多个good点连通的充要条件是,能够连通的点中,存在(x,y)满足 x = y。因此判断是否存在无穷连通的点时,只需要判断是否存在点能够走到(k,k)这样类型的点。相反,如果不到这样的点,必定存在有限个连通的good点。

​ 这是一个图的模型,用dfs进行搜索就可以,我用了map<pair<long long, long long>, bool>进行点的记录,已搜索过的点不能再重复搜索,不然就死循环,用map<long long, int>进行压缩后数组进行记录或者结构体不知道行不行,感觉可以,没试过。。。。。

​ 剩下要做的就是在有限连通的点中,如何计算足够多的步数后回到起始点的概率。
​ 这里我写的时候只是用第三个例子推测了一下,第三个例子连通的点有三个,分别作为起始点时,第一次移动停留的概率分别为12\frac{1}{2}12\frac{1}{2}13\frac{1}{3},题目给出的起始点第一步停留的概率是12\frac{1}{2},足够多的步数回到自身的概率是27\frac{2}{7},直接猜了一个规律:答案的分子是自身第一步停留的概率的分母,答案的分母是所有可到的点作为起始点时第一步停留的自身的概率的分母和。
​ 文字有点拗口,换个方式:设每一个可连通的点作为起始点时停留自身的概率是1xi\frac{1}{x_i},i 从1到 n ,要求的起始点为第k个,那么答案就是xki=1nxi\frac{x_k}{\sum_{i=1}^{n}{x_i}}

​ 最后得到的分数如果可约,那就要约成最简分数。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
typedef long long LL;
int dir[8][2] = {-1, 1, 0, 1, 1, 1, -1, 0, 1, 0, -1, -1, 0, -1, 1, -1};
int flag, d, u;
//flag为1表示有穷连通,为0表示无穷连通;d为xi求和,u为xk
map<pair<LL, LL>, int> m;//记录点是否good
pair<LL, LL> p;

void dfs(LL x, LL y){
	if(x == y){
		flag = 0;
		return;
	}
	int dd = 1;
	for(int i = 0; i < 8; i++){
			LL xx = x + dir[i][0], yy = y + dir[i][1];
			if(__gcd(xx, yy) > 1) {
				dd++;
				p.first = xx, p.second = yy;
				if(m.count(p)) continue;
				m[p] = 1;
				dfs(xx, yy);
				if(flag == 0) return;
			}
			
		}
	//cout << "x:" << x << "  y:" << y << "   dd:" << dd << endl;
	d += dd;
	
}

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		LL x, y;
		scanf("%lld%lld", &x, &y);
		if(x == y + 2 || y == x + 2){
			printf("0/1\n");
			continue;
		}
		u = 1;
		d = 1;
		flag = 1;
		m.clear();
		p.first = x, p.second = y;
		m[p] = 1;
		//dfs(x, y);
		for(int i = 0; i < 8; i++){
				LL xx = x + dir[i][0], yy = y + dir[i][1];
				if(__gcd(xx, yy) > 1){
					d++;
					u++;
					p.first = xx, p.second = yy;
					m[p] = 1;
				}
			}

	//cout << "      x:" << x << "  y:" << y << "   d:" << d << endl;
		for(int i = 0; i < 8; i++){
				LL xx = x + dir[i][0], yy = y + dir[i][1];
				if(__gcd(xx, yy) > 1){
					dfs(xx, yy);
				}
			}
		if(flag){
			int kk = __gcd(u, d);
			u /= kk;
			d /= kk;
			printf("%d/%d\n", u, d);
		}
		else
			printf("0/1\n");

	}
	return 0;
}

PS:菜鸡一个,如果存在错误或者可提升的地方可尽情指出!


本文链接: http://www.dtmao.cc/news_show_100001.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?