差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/08/17 20:51]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-===== G. Game of Death =====
+===== H. travel =====
 ==== 题意 ====
-一个游戏，有 $n$ 名玩家。每个玩家等概率选择一名除自己以为的人进行射击，射击的命中率为 $p$。
+给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
-对每个 $k=1\sim n$ ，询问最后存活 $k$ 人的概率。
 ==== 题解 ====
-设 $f(k)$ 表示固定 $k$ 个人的集合，这 $k$ 个人全部死亡的概率。$g(k)$ 表示固定 $k$ 个人的集合，死亡的人是这个集合的子集的概率。
+设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。
-首先考虑计算 $g(k)$，事实上可以把所有人分成两种人，一种是在这个 $k$ 人集合中的人，记为 $A$ 类人。另一种记为 $B$ 类人。
+我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。
-于是只需要保证不杀死 $B$ 类人即可。于是对 $A$ 类人，这个概率为 $1-\frac {p(n-k)}{n-1}$。而对于 $B$ 类人，这个概率为 $1-\frac {p(n-1-k)}{n-1}$。
+如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
-于是有
+考虑状态转移，利用生成链的合并，不难有
 $$
-g(k)=\left(1-\frac {p(n-k)}{n-1}\right)^k\left(1-\frac {p(n-1-k)}{n-1}\right)^{n-k}
+\text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\
+\text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j)
 $$
-同时有 $g(k)=\sum_{i=0}^k {k\choose i}f(i)$，根据二项式反演，得
+注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。
+初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有
 $$
-f(k)=\sum_{i=0}^k (-1)^{k-i}{k\choose i}g(i)=k!\sum_{i=0}^k\frac{(-1)^{k-i}}{(k-i)!}\frac{g(i)}{i!}
+\text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1))
 $$
-卷积计算即可，最终 $k$ 人死亡的答案为 ${n\choose k}f(k)$。时间复杂度 $O(n\log n)$。
+最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。
+[[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]]
 <hidden 查看代码>
 <code cpp>
-const int MAXN=3e5+5,mod=998244353;
+const int MAXN=4e5+5,MAXK=4;
-int quick_pow(int n,int k){
+struct Edge{
-	int ans=1;
+	int to,next;
-	while(k){
+}edge[MAXN<<1];
-		if(k&1)ans=1LL*ans*n%mod;
+int a[MAXN],head[MAXN],edge_cnt;
-		n=1LL*n*n%mod;
+LL dp[MAXN][3][MAXK],tmp[3][MAXK];
-		k>>=1;
+void Insert(int u,int v){
-	}
+	edge[++edge_cnt]=Edge{v,head[u]};
-	return ans;
+	head[u]=edge_cnt;
+}
+void Max(LL &a,LL b){
+	if(b>a)
+	a=b;
 }
-namespace Poly{
+void dfs(int u,int fa){
-	const int G=3,Mod=998244353;
+	dp[u][1][0]=a[u];
-	int rev[MAXN<<2],Wn[30][2];
+	for(int i=head[u];i;i=edge[i].next){
-	void init(){
+		int v=edge[i].to;
-		int m=Mod-1,lg2=0;
+		if(v==fa)continue;
-		while(m%2==0)m>>=1,lg2++;
+		dfs(v,u);
-		Wn[lg2][1]=quick_pow(G,m);
+		_for(i,0,3)_for(j,0,MAXK)
-		Wn[lg2][0]=quick_pow(Wn[lg2][1],Mod-2);
+		tmp[i][j]=dp[u][i][j];
-		while(lg2){
+		_for(i,0,MAXK)_for(j,0,MAXK-i){
-			m<<=1,lg2--;
+			Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]);
-			Wn[lg2][0]=1LL*Wn[lg2+1][0]*Wn[lg2+1][0]%Mod;
+			Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]);
-			Wn[lg2][1]=1LL*Wn[lg2+1][1]*Wn[lg2+1][1]%Mod;
+			Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]);
+			Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]);
+			Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]);
 		}
+		_for(i,0,3)_for(j,0,MAXK)
+		dp[u][i][j]=tmp[i][j];
 	}
-	int build(int k){
+	_for(i,1,MAXK)
-		int n,pos=0;
+	Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1]));
-		while((1<<pos)<=k)pos++;
-		n=1<<pos;
-		_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
-		return n;
-	}
-	void NTT(int *f,int n,bool type){
-		_for(i,0,n)if(i<rev[i])
-		swap(f[i],f[rev[i]]);
-		int t1,t2;
-		for(int i=1,lg2=0;i<n;i<<=1,lg2++){
-			int w=Wn[lg2+1][type];
-			for(int j=0;j<n;j+=(i<<1)){
-				int cur=1;
-				_for(k,j,j+i){
-					t1=f[k],t2=1LL*cur*f[k+i]%Mod;
-					f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
-					cur=1LL*cur*w%Mod;
-				}
-			}
-		}
-		if(!type){
-			int div=quick_pow(n,Mod-2);
-			_for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
-		}
-	}
-	void mul(int *f,int _n,int *g,int _m){
-		int n=build(_n+_m-2);
-		_for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0;
-		NTT(f,n,1);NTT(g,n,1);
-		_for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod;
-		NTT(f,n,0);
-	}
-}
-int frac[MAXN],invf[MAXN];
-int C(int n,int m){
-	return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
 }
-int f[MAXN<<2],g[MAXN<<2];
 int main()
 {
-	Poly::init();
+	int n=read_int();
-	int n=read_int(),a=read_int(),b=read_int();
+	_rep(i,1,n)
-	int p=1LL*a*quick_pow(b,mod-2)%mod;
+	a[i]=read_int();
-	frac[0]=1;
+	_for(i,1,n){
-	_for(i,1,MAXN)frac[i]=1LL*frac[i-1]*i%mod;
+		int u=read_int(),v=read_int();
-	invf[MAXN-1]=quick_pow(frac[MAXN-1],mod-2);
+		Insert(u,v);
-	for(int i=MAXN-1;i;i--)
+		Insert(v,u);
-	invf[i-1]=1LL*invf[i]*i%mod;
-	int div=quick_pow(n-1,mod-2);
-	_rep(i,0,n){
-		LL t1=1-1LL*p*(n-i)%mod*div;
-		LL t2=1-1LL*p*(n-1-i)%mod*div;
-		g[i]=1LL*quick_pow(t1%mod,i)*quick_pow(t2%mod,n-i)%mod;
-		g[i]=1LL*g[i]*invf[i]%mod;
-		f[i]=(i&1)?-invf[i]:invf[i];
 	}
-	Poly::mul(f,n+1,g,n+1);
+	dfs(1,0);
-	_rep(i,0,n)
+	enter(dp[1][0][3]);
-	f[i]=1LL*f[i]*frac[i]%mod*C(n,i)%mod;
-	_rep(i,0,n)
-	enter(f[n-i]);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具