题解：CF235D Graph Game

好题啊。基本把期望线性性玩明白了。

利用期望线性性，首先可以拆贡献。要计算“某个点在点分治过程中被遍历的期望次数”。所有点分别计算后求和就是答案。

然后可以手玩这个分治过程，假设要计算的点为

i

，从

i

的视角观察，把它定为“根”。然后就会发现，按照分治过程，等概率在

i

所在的联通块内选一个点，然后把它删掉，重复直至

i

被删掉，这个过程是和原点分治是一样的。所以一个点的贡献可以转化为进行上述操作的期望步数。

要解决如上问题，依然可以拆贡献。要计算“

x

点在操作中被删掉次数的期望（也就是被删的概率）”

以下图情况（

x

到

i

间经过基环）解决该问题：

首先我们构造一个“操作序列”，是一个

1 \sim n

的排列。按顺序在原基环树上删点，要是不合法操作就直接忽略。容易发现操作序列中合法点的部分与实际删点的方案一一对应，并合法点部分出现的概率等于实际删点方案的概率。

具体来说，在第

j

次（共

cnt

次）删点时，记除自己外，被删掉（与

i

断开）的点数为

del_j

。我们可以在当前操作序列最靠左的空位上填写点的编号，把填上后面剩余的空位选择

del_j

个用这些被断开的点任意排列后补齐。这样同一个删点方案所对应的排列出现的概率即为

\dfrac{\prod_{s=1}^{cnt}A_{n-s-\sum_{t=1}^{s-1}del_t}^{del_s}}{n!} = \dfrac{(n-1) \times (n-2) \times ... \times (n-del_1) \times (n-del_1-2) \times ... \times (n-del_1-del_2-1) \times ...}{n!}

消完后即得到实际操作的概率。

欸？好像有道题也是这么个证法。

回到图上，

D

部分是不在环上的点 + 进入和走出环上的点，在删点过程中，他们中一个被删了，

x

不能被删，所以在操作序列上他们必须在

x

点的后面，

x

才能合法地被删除。同理，

a1

和

a2

部分是

x

到

i

环上可能的两条路径，则需要至少一个部分在操作序列上完全在点

x

的后面。经过简单的计算+容斥可得最终的答案为

\frac1{D+a1} + \frac1{D+a2} - \frac1{D+a1+a2}

。

然后其他情况比这个简单，也是这么推的。

然后这道题就做完了。

时间复杂度

O(n^2)

CPP

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> vec[3002];
int du[3002];
queue<int> q;
bool incir[3002];
int cirtot;
void forcir(){
	for(int i=1;i<=n;i++) incir[i] = 1;
	cirtot = n;
	for(int i=1;i<=n;i++) if(du[i] == 1) q.push(i);
	while(!q.empty()){
		int u = q.front();
        q.pop();
		incir[u] = 0;
		cirtot--;
		for(int i=0;i<vec[u].size();i++){
			int v = vec[u][i];
			du[v]--;
			if(du[v] == 1){
				q.push(v);
			}
		}
	}
}

int dep[3002], a[3002];
bool vis[3002];
double solve(int pos,int fa){
    //cout << pos <<endl;
	double ret = 0;
	if(!incir[pos]) dep[pos] = dep[fa] + 1, a[pos] = a[fa];
	else dep[pos] = dep[fa], a[pos] = a[fa] + 1;
    double S = dep[pos]+min(a[pos],2);
    if(a[pos] > 2 && cirtot - a[pos] > 0) ret += 1.0 / (S + a[pos]-2) + 1.0 / (S + cirtot-a[pos]) - 1.0 / (S + cirtot-2);
    else ret += 1.0 / S;
	for(int i=0;i<vec[pos].size();i++){
		int v = vec[pos][i];
		if(vis[v]) continue;
		vis[v] = 1, ret += solve(v,pos);
	}
	return ret;
}

int main(){
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int u, v;
		scanf("%d%d",&u,&v);
		u++, v++;
		vec[u].push_back(v);
		vec[v].push_back(u);
		du[u]++, du[v]++;
	}
	forcir();
    //for(int i=1;i<=n;i++) cout << incir[i] << ' ';
    //cout << endl;
	
	double Ans = 0;
	for(int i=1;i<=n;i++){
        //cout << i << endl;
        for(int j=1;j<=n;j++) vis[j] = 0;
		vis[i] = 1, Ans += solve(i,0);
	}
	
	printf("%.10f",Ans);
	
	return 0;
}

题解：CF235D Graph Game

文章操作

相关推荐

评论

题解：CF235D Graph Game