差别

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

--- 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/08/19 11:11]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:缓冲区 [2021/10/04 17:00] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-===== K. Walking =====
+===== H. travel =====
 ==== 题意 ====
-给定一个 $n\times m$ 的网格和初始点 $(a,b)$，求从初始点出发移动 $t$ 步且始终不出界的情况下的所有走法。
+给定一棵点权树，从树上选三条不相交的路径，每条路径的权值定义为路径上的点权和，要求最大化三条路径权值和。
 ==== 题解 ====
-显然横轴坐标是独立的，可以分开考虑。
+设 $\text{dp}(u,0/1/2,i)$ 表示只考虑 $u$ 的子树，结点 $u$ 的状态为 $0/1/2$ 时，已经选中了 $i$ 条链此时的最大路径权值和。
-设 $f(s,n,a)$ 表示从一维坐标轴从 $a$ 点出发走 $s$ 步且始终处于 $[1,n]$ 范围内的情况下的所有走法。于是答案为
+我们需要维护一条正在生成的链，这条链不包含在已经选中的 $i$ 条链当中，如果 $u$ 状态为 $0$ 表示 $u$ 不在生成链中。
-$$
+如果 $u$ 状态为 $1$ 表示 $u$ 在生成链中且 $u$ 只有一个儿子在生成链中， $u$ 状态为 $2$ 表示 $u$ 在生成链中且 $u$ 有两个儿子在生成链中。
-\sum_{i=0}^t {t\choose i}f(i,n,a)f(t-i,m,b)
-$$
-接下来考虑如何计算 $f(s,n,a)(s\in [0,t])$，$f(s,m,b)$ 的计算方式类同。
-方案一：设 $\text{dp}(i,j)$ 表示走 $i$ 步最后位于 $j$ 点且始终为出界的方案数，不难得到一个 $O(nt)$ 的暴力解法。
-方案二：不难发现，有
+考虑状态转移，利用生成链的合并，不难有
 $$
-\begin{equation}\begin{split}
+\text{dp}(u,0,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,0,j)\\
-f(s,n,a)&=\sum_{i=1}^n \text{dp}(s,i) \\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,0,i)+\text{dp}(v,1,j)+a_u\\
-&=\text{dp}(s-1,1)+\sum_{i=2}^{n-1} (\text{dp}(s-1,i-1)+\text{dp}(s-1,i+1))+\text{dp}(s-1,n)\\
+\text{dp}(u,1,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,0,j)\\
-& =2f(s-1,n,a)-\text{dp}(s-1,1)-\text{dp}(s-1,n)
+\text{dp}(u,2,i+j)\gets \text{dp}(u,1,i)+\text{dp}(v,1,j)\\
-\end{split}\end{equation}
+\text{dp}(u,2,i+j)\gets \text{dp}(u,2,i)+\text{dp}(v,0,j)
 $$
-于是问题转化为计算 $\text{dp}(s,1),\text{dp}(s,n)$。
+注意上式的 $\gets$ 表示取最大值，另外为了防止选中复数条从 $v$ 生成的链，需要开一个临时数组存储中间量。
-对每个移动方案，定义非法序列，每当点进入 $(-\infty,0)$ 时非法序列末尾加上 $L$，每当点进入 $(n,+\infty)$ 时非法序列末尾加上 $R$。
+初始状态为 $\text{dp}(u,1,0)=a_u$，最后转移完要考虑将正在生成的链转化为已经选中的链，于是有
-对于 $\text{dp}(s,1)$，我们需要获得所有非法序列为空串的移动方案。设 $h(a,b,s)$ 表示从 $a$ 移动 $s$ 步到达 $b$ 的方案数。
-显然根据 $a,b,s$ 奇偶性以及预处理组合数可以 $O(1)$ 计算 $h(a,b,s)$。
-然后总移动方案为 $h(a,1,s)$。利用容斥，首先我们减去非法序列为 ''L+.*'' 和 ''R+.*'' (非法序列均用正则表达式表示)的移动方案。
-设 $l(x)=-x,r(x)=2(n+1)-x$。根据简单组合数学知识，不难发现 ''L+.*''  代表的方案为 $h(a,l(1),s)$，''R+.*''  代表的方案为 $h(a,r(1),s)$。
-接下来我们需要补上减去非法序列为 ''L+R+.*'' 和 ''R+L+.*'' 的移动方案，分别为 $h(a,r(l(1)),s),h(a,l(r(1)),s)$。依次类推，有
 $$
-\text{dp}(s,1)=h(a,1,s)-h(a,l(1),s)-h(a,r(1),s)+h(a,r(l(1)),s)+h(a,l(r(1)),s)-h(a,l(r(l(1))),s)-h(a,r(l(r(1))),s)+\cdots
+\text{dp}(u,0,i)\gets \max(\text{dp}(u,1,i-1),\text{dp}(u,2,i-1))
 $$
-由于 $r(l(x))=2(n+1)+x$，且当 $\text{abs}(a-x)\gt s$ 时一定有 $h(a,x,s)=0$，所以上述容斥最多迭代 $O(\frac sn)$ 次。
+最终答案为 $\text{dp}(1,0,3)$，时间复杂度 $O(nk^2)$，其中 $k$ 表示最多能选中的链的个数。
-于是方案二的总时间复杂度为 $O\left(\sum_{i=1}^t \frac in\right)\sim O\left(\frac {t^2}n\right)$。
+[[http://tokitsukaze.live/2018/07/24/2018niuke2.H/|参考资料]]
-考虑根号分治，当 $n\lt \sqrt t$ 时采用方案一，否则采用方案二。总时间复杂度 $O(t\sqrt t)$。
 <hidden 查看代码>
 <code cpp>
-const int MAXN=5e5+5,MAXM=800,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;
 }
-int frac[MAXN],invf[MAXN];
+void Max(LL &a,LL b){
-int C(int n,int m){
+	if(b>a)
-    return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
+	a=b;
 }
-void init(){
+void dfs(int u,int fa){
-	frac[0]=1;
+	dp[u][1][0]=a[u];
-    _for(i,1,MAXN)frac[i]=1LL*frac[i-1]*i%mod;
+	for(int i=head[u];i;i=edge[i].next){
-    invf[MAXN-1]=quick_pow(frac[MAXN-1],mod-2);
+		int v=edge[i].to;
-    for(int i=MAXN-1;i;i--)
+		if(v==fa)continue;
-    invf[i-1]=1LL*invf[i]*i%mod;
+		dfs(v,u);
-}
+		_for(i,0,3)_for(j,0,MAXK)
-int ans1[MAXN],ans2[MAXN];
+		tmp[i][j]=dp[u][i][j];
-int dp[2][MAXM];
+		_for(i,0,MAXK)_for(j,0,MAXK-i){
-void solve1(int s,int n,int a,int *ans){
+			Max(tmp[0][i+j],dp[u][0][i]+dp[v][0][j]);
-	int pos=0;
+			Max(tmp[1][i+j],dp[u][0][i]+dp[v][1][j]+a[u]);
-	mem(dp[pos],0);
+			Max(tmp[1][i+j],dp[u][1][i]+dp[v][0][j]);
-	dp[pos][a]=1;
+			Max(tmp[2][i+j],dp[u][1][i]+dp[v][1][j]);
-	ans[0]=1;
+			Max(tmp[2][i+j],dp[u][2][i]+dp[v][0][j]);
-	_rep(i,1,s){
-		pos=!pos;
-		mem(dp[pos],0);
-		_rep(j,1,n){
-			dp[pos][j]=(dp[!pos][j-1]+dp[!pos][j+1])%mod;
-			ans[i]=(ans[i]+dp[pos][j])%mod;
 		}
+		_for(i,0,3)_for(j,0,MAXK)
+		dp[u][i][j]=tmp[i][j];
 	}
-}
+	_for(i,1,MAXK)
-int cal(int s,int n,int a,int pos){
+	Max(dp[u][0][i],max(dp[u][1][i-1],dp[u][2][i-1]));
-	int pos1=pos,pos2=pos,ans=0,d=abs(pos-a);
-	if(d<=s&&(s-d)%2==0)
-	ans=C(s,(s+d)/2);
-	for(int j=1;;j++){
-		if(j&1){
-			pos1=-pos1;
-			pos2=2*(n+1)-pos2;
-		}
-		else{
-			pos1=2*(n+1)-pos1;
-			pos2=-pos2;
-		}
-		int d1=abs(pos1-a),d2=abs(pos2-a),det=0;
-		if(d1>s&&d2>s)break;
-		if(d1<=s&&(s-d1)%2==0)
-		det=(det+C(s,(s+d1)/2));
-		if(d2<=s&&(s-d2)%2==0)
-		det=(det+C(s,(s+d2)/2))%mod;
-		if(j&1)
-		ans=(ans+mod-det)%mod;
-		else
-		ans=(ans+det)%mod;
-	}
-	return ans;
-}
-void solve2(int s,int n,int a,int *ans){
-	ans[0]=1;
-	_rep(i,1,s)
-	ans[i]=(2LL*ans[i-1]+mod-cal(i-1,n,a,1)+mod-cal(i-1,n,a,n))%mod;
-}
-void solve(int s,int n,int a,int *ans){
-	if(1LL*n*n<s)
-	solve1(s,n,a,ans);
-	else
-	solve2(s,n,a,ans);
 }
 int main()
 {
-	init();
+	int n=read_int();
-	int t=read_int(),n=read_int(),m=read_int(),a=read_int(),b=read_int();
+	_rep(i,1,n)
-	solve(t,n,a,ans1);
+	a[i]=read_int();
-	solve(t,m,b,ans2);
+	_for(i,1,n){
-	int ans=0;
+		int u=read_int(),v=read_int();
-	_rep(i,0,t)
+		Insert(u,v);
-	ans=(ans+1LL*C(t,i)*ans1[i]%mod*ans2[t-i])%mod;
+		Insert(v,u);
-	enter(ans);
+	}
+	dfs(1,0);
+	enter(dp[1][0][3]);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具