前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 4921 Map

HDU 4921 Map

作者头像
全栈程序员站长
发布2022-07-13 17:39:21
1420
发布2022-07-13 17:39:21
举报
文章被收录于专栏:全栈程序员必看

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

题意:

给n个节点 他们形成了最多10条链 每条最多1000的长度 每一个节点有个val 你能够选择任何位置截断链 断点前的全部节点被你获得 通过题中计算公式得出你的val 问 通过随机截断 获得val的期望是多少

思路:

期望=全部方案val的和/方案数

这里明显有分层的现象 并且每层最多10个元素 因此想到状压 那么我们仅仅要逐层统计 每层计算一下能对“全部方案val的和”产生多少贡献就可以 方案数能够直接算出来 计算方法例如以下

对于方案数 它就等于 (amt[1]+1)*(amt[2]+1)*… amt[i]为每条链上的节点总数 这个式子就表示对于每条链有amt+1种截断方式 即 一開始就截断+在每一个元素后面截断

对于val的和 我们通过每层的状态来计算(刚才也说了要状态压缩)

假设状压中该位置为1表示选中该元素 那么序列一定是这种111111XXXXXX 即1前面一定都是1 因此相应的方案有amt-层数+1 种

假设该位置为0 那么序列一定是这种 XXXXXXX000000 即0后面一定都是0 那么方案就有 层数 种

知道了那一层所形成的方案数 那么仅仅须要计算一下该层的节点val和与方案数乘一下就能够了

代码:

代码语言:javascript
复制
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 10010

int next[N], vis[N], val[N], amt[10], qu[10];
double x, y;
int t, n, m, tot;

int main() {
	int i, u, v, floor, have, num;
	double ways, res;
	//freopen("1001.in", "r", stdin);
	//freopen("1001.out", "w", stdout);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		memset(next, 0, sizeof(next));
		memset(vis, 0, sizeof(vis));
		memset(amt, 0, sizeof(amt));
		tot = 0;
		x = 1;
		y = 0;
		for (i = 1; i <= n; i++)
			scanf("%d", &val[i]);
		for (i = 1; i <= m; i++) {
			scanf("%d%d", &u, &v);
			u++;
			v++;
			next[u] = v;
			vis[v] = 1;
		}
		for (i = 1; i <= n; i++)
			if (!vis[i]) {
				qu[tot] = i;
				for (u = i; u; u = next[u])
					amt[tot]++;
				x *= amt[tot] + 1;
				tot++;
			}
		for (floor = 1;; floor++) {
			num = 0;
			for (i = 0; i < tot; i++)
				if (qu[i])
					num++;
			if (!num)
				break;
			for (u = 1; u < (1 << tot); u++) {
				have = 0;
				ways = 1;
				res = 0;
				for (i = 0; i < tot; i++) {
					if (u & (1 << i)) {
						if (!qu[i])
							break;
						res += val[qu[i]];
						have++;
						ways *= amt[i] - floor + 1;
					} else
						ways *= min(floor, amt[i] + 1);
				}
				if (i == tot) {
					y += res * ways;
					if (have > 1)
						y += res * have * ways / num;
				}
			}
			for (i = 0; i < tot; i++)
				qu[i] = next[qu[i]];
		}
		//printf("%.3f %.3f  ", y, x);
		printf("%.3f\n", y / (x - 1));
	}
	return 0;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/118188.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021年12月,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档