正文

[JZOJ5233] 【GDOI模拟8.5】概率博弈

IP云
IP云V管理员/3 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

flowchart 箭头图标 勿删

题目

题目大意

给你一棵树，这棵树上的所有 叶子 节点的权值是 随机的排列 。

两个人博弈，从根开始，轮流往下走。

先手希望权值最大，后手希望权值最小。

问 期望 的最终结果。

思考历程

这场比赛实在是太丧心病狂了！两个期望题，有没有人性啊！

还是那种特别变态的期望……

想了好久，没有想出来……

于是打暴力：

枚举所有的排列，然后用DP计算答案。

如果喜欢，DP可以加上alpha-beta剪枝……当然我没加，因为在这题里面没有什么意义。

分数还给的挺大方的，30分。

正解

首先推个式子：

E(x)=∑xP(x=ans)=∑P(x≤ans)E(x)\\=\sum xP(x=ans) \\=\sum P(x \leq ans)E(x)=∑xP(x=ans)=∑P(x≤ans)

后面这个是什么鬼？

我们将第二个式子拆开，对于xxx，它贡献了xxx个P(ans=x)P(ans=x)P(ans=x)。

看看第三个式子，对于x′≤xx'\leq xx′≤x，它就可以加上xxx的贡献。这样的x′x'x′有xxx个，所以这是成立的。

接下来就是一个很巧妙的转化：

我们设结果为xxx，将大于xxx的记作111，将小于等于xxx的记作000。

这样就大大地简化了题目，因为我们只需要关心它的结果是否为111，而不需要关心结果是否恰好为xxx。

然后就是树形DP：设fi,j,0/1f_{i,j,0/1}fi,j,0/1​表示点iii为根的子树中，叶子节点的权值为000的个数是jjj，点iii的值为000或111（从下面转移上来的值）的方案数。

方程就不用说了吧……自己推。

这就是一个树上背包问题。

至于最终的答案，枚举xxx，它的贡献就是f1,x,1Cmx\frac{f_{1,x,1}}{C_m^x}Cmx​f1,x,1​​。（mmm为叶子节点的个数）

由于题目良心地让我们输出ans∗m!ans*m!ans∗m!，所以说，输出的就是f1,x,1∗x!∗(m−x)!f_{1,x,1}*x!*(m-x)!f1,x,1​∗x!∗(m−x)!

然而这个算法看上去是O(n3)O(n^3)O(n3)的，我在很长时间内也这么认为。

YMQ：我吸一口臭氧，也能过！

但时间复杂度实际上是O(n2)O(n^2)O(n2)。

为什么？

从最简单的开始考虑：如果这棵树是一棵二叉树，对于一个非叶子节点，当大小分布比较均匀时：

对于根节点，合并子树的时间是(n2)2=n24\left(\frac{n}{2}\right)^2=\frac{n^2}{4}(2n​)2=4n2​。

对于下一层，时间是2(n4)2=n282\left(\frac{n}{4}\right)^2=\frac{n^2}{8}2(4n​)2=8n2​。

再下一层，时间是4(n8)2=n2164\left(\frac{n}{8}\right)^2=\frac{n^2}{16}4(8n​)2=16n2​。

后面的就不枚举了。

把它们全部加起来，时间就趋近于n22\frac{n^2}{2}2n2​。

当大小分布不均匀时，我们考虑最极端的情况，时间复杂度还是O(n2)O(n^2)O(n2)。

至于不均匀而又不极端的情况……感性理解，不信邪的可以打一个DP来求最坏的情况。

考虑一下多叉树，发现其实际上是类似的，时间复杂度是O(n2)O(n^2)O(n2)。

最终我还是不会证明……

代码 
using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 5000

#define mo 1000000007

int n;

struct EDGE{

	int to;

	EDGE *las;

} e[N*2+1];

int ne;

EDGE *last[N+1];

inline void link(int u,int v){

	e[++ne]={v,last[u]};

	last[u]=e+ne;

}

long long jc[N+1];

int tot[N+1];

long long f[N+1][N+1][2];

void dfs(int x,int fa,bool flag){

	if (last[x]->las==NULL && last[x]->to==fa){//叶子节点的情况

		tot[x]=1;

		f[x][0][1]=f[x][1][0]=1;

		return;

	}

	EDGE *ei=last[x];//另外处理第一个儿子，这样就不用考虑初始化

	if (ei->to==fa)

		ei=ei->las;

	dfs(ei->to,x,!flag);

	memcpy(f[x],f[ei->to],sizeof f[ei->to]);

	tot[x]=tot[ei->to];

	ei=ei->las;

	if (flag==0){

		for (;ei;ei=ei->las)

			if (ei->to!=fa){

				dfs(ei->to,x,1);

				for (int j=tot[x]+tot[ei->to];j>=0;--j){

					//k=0

					f[x][j][1]=(f[x][j][0]*f[ei->to][0][1]%mo+f[x][j][1]*f[ei->to][0][0]%mo+f[x][j][1]*f[ei->to][0][1]%mo)%mo;

					f[x][j][0]=f[x][j][0]*f[ei->to][0][0]%mo;

					for (int k=1;k<=tot[ei->to] && k<=j;++k){

						(f[x][j][1]+=(f[x][j-k][0]*f[ei->to][k][1]%mo+f[x][j-k][1]*f[ei->to][k][0]%mo+f[x][j-k][1]*f[ei->to][k][1]%mo))%=mo;

						(f[x][j][0]+=f[x][j-k][0]*f[ei->to][k][0])%=mo;

					}

				}

				tot[x]+=tot[ei->to];

			}

	}

	else{

		for (;ei;ei=ei->las)

			if (ei->to!=fa){

				dfs(ei->to,x,0);

				for (int j=tot[x]+tot[ei->to];j>=0;--j){

					//k=0

					f[x][j][0]=(f[x][j][0]*f[ei->to][0][0]%mo+f[x][j][0]*f[ei->to][0][1]%mo+f[x][j][1]*f[ei->to][0][0]%mo)%mo;

					f[x][j][1]=f[x][j][1]*f[ei->to][0][1]%mo;

					for (int k=1;k<=tot[ei->to] && k<=j;++k){

						(f[x][j][0]+=(f[x][j-k][0]*f[ei->to][k][0]%mo+f[x][j-k][0]*f[ei->to][k][1]%mo+f[x][j-k][1]*f[ei->to][k][0]%mo))%=mo;

						(f[x][j][1]+=f[x][j-k][1]*f[ei->to][k][1])%=mo;

					}

				}

				tot[x]+=tot[ei->to];

			}

	}

}

int main(){

	freopen("game.in","r",stdin);

	freopen("game.out","w",stdout);

	scanf("%d",&n);

	jc[0]=1;

	for (int i=1;i<=n;++i)

		jc[i]=jc[i-1]*i%mo;

	for (int i=1;i<n;++i){

		int u,v;

		scanf("%d%d",&u,&v);

		link(u,v),link(v,u);

	}

	dfs(1,0,0);

	long long ans=0;

	for (int i=0;i<=tot[1];++i)

		ans=(ans+f[1][i][1]*jc[i]%mo*jc[tot[1]-i]%mo)%mo;

	printf("%lld\n",ans);

	return 0;

}

总结

这道题有一个·很奇妙的思想，就在于∑xP(x=ans)=∑P(x≤ans)\sum xP(x=ans)=\sum P(x \leq ans)∑xP(x=ans)=∑P(x≤ans)。

。

通过这个东西，可以大大地简化题目。

当条件为“等于”的时候，我们可以试着转化成“大于”“小于”。

然后就是树上背包的时间复杂度……

相关阅读

目录[+]