专栏文章

题解：P14260 期待（counting）

VVinstaG173かえで
P14260题解参与者 10已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@minrsgnx
此快照首次捕获于
2025/12/02 07:18
3 个月前
此快照最后确认于
2025/12/02 07:18
3 个月前
查看原文
tag：树形结构，计数。
以下为了表述方便，称期待的方案为合法。

暴力

直接枚举所有合法移动方案，复杂度 O(n3)O(n^3)，期望得分 15+?15+?。

特殊性质 B

祖传不按顺序讲特殊性质。
菊花图部分分。
事实上发现在菊花图上只有四种本质不同的情况，直接求出对应答案公式即可。
若 y≠sy\neq s，则有两种情况：
  1. y,sy,s 其一为根，如样例 1 的第一组数据，距离为 00 时要走一条经过该两点的路径，共 2(n−1)2(n-1) 种。距离为 11 时或者不动，或者经过 y,sy,s 之间的边和另一条边，或者在 y,sy,s 之间的边上两端点互换，共 1+2(n−2)+21+2(n-2)+2 种，最终答案为 4n−34n-3。
  2. y,sy,s 为两不同叶子，同样例第二组数据，答案为 55。
复杂度 O(n)O(n)，期望得分 2020。

特殊性质 C

链部分分。不妨设 ii 与 i+1i+1 连边，我们可以自然地定义从小到大和从大到小两种移动方向。
首先考虑合法移动方案的条件。样例非常良心地给我们提示了一种小 corner case：在一条边上两端点互换。容易发现只有这一种情况可以使得两棋子移动方向不同。以下不再赘述。
发现其余情况下只要两棋子移动方向相同则方案合法。再根据非常良心的样例解释容易发现除了 (y,s)(y,s) 不动外的所有方案都可以两两配对，每对恰互为调换移动方向后的结果。因此我们只考虑从小到大的情况。
如上我们将问题转化为：求区间组 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2] 的数量，使得 r1−l1+1=r2−l2+1r_1-l_1+1=r_2-l_2+1，且 l1≤y≤r1,l2≤s≤r2l_1\le y\le r_1,l_2\le s\le r_2。
直接枚举 l1,l2l_1,l_2 可以 O(1)O(1) 求出方案数，期望得分 1010。
考虑 l=min⁡{l1,l2},r=max⁡{r1,r2}l=\min\{l_1,l_2\},r=\max\{r_1,r_2\}，显然 l≤y,s≤rl\le y,s\le r。若 l1=l,r2=rl_1=l,r_2=r，则要求 r1≥y,l2≤sr_1\ge y,l_2\le s，有 min⁡{r−y+1,s−l+1}\min\{r-y+1,s-l+1\} 种可能。同理 l2=l,r1=rl_2=l,r_1=r 有 min⁡{r−s+1,y−l+1}\min\{r-s+1,y-l+1\} 种可能。其中有一种重复方案：l1=l2,r1=r2l_1=l_2,r_1=r_2。
不妨设 y≤sy\le s，由上可知 l=y−i,r=s+jl=y-i,r=s+j 时有 (s−y)+2min⁡{i,j}+1(s-y)+2\min\{i,j\}+1 种方案，即求 ∑i=0y−1∑j=0n−s((s−y)+2min⁡{i,j}+1)\sum_{i=0}^{y-1}\sum_{j=0}^{n-s}\left((s-y)+2\min\{i,j\}+1\right)，容易后缀和优化 O(n)O(n) 求出。期望得分 2020。

特殊性质 A

完全二叉树的大部分性质我不知道怎么用。这个部分分是正解的一部分。
容易证明合法移动方案中经过的所有点一定在同一条链上。只要确定这条链就可以沿用链部分分的解法。
考虑以 ss 为根时 yy 的子树中点作为 ll，以 yy 为根时 ss 的子树中点作为 rr，类似地只需求 ∑l∑r(dis(s,y)+2min⁡{dis(y,l)+dis(s,r)}+1)\sum_l\sum_r(dis(s,y)+2\min\{dis(y,l)+dis(s,r)\}+1)，因为 dis(y,l)dis(y,l) 和 dis(s,r)dis(s,r) 都是 O(log⁡n)O(\log n) 的，统计深度相同的点数后直接计算可以做到 O(log⁡2n)O(\log^2n)。

正解

同完全二叉树部分分直接算可以做到 O(n2)O(n^2)。同链部分分可以优化至 O(n)O(n)，期望得分 100100。
Code:
CPP
int n,y,s;
int d[100003];
vector<int>e[100003];

int c0[100003];
int c1[100003];
int dep[100003],dp0,dp1;
void dfs(int u,int fa){
	for(int i=0,v;i<d[u];++i){
		v=e[u][i];if(v==fa)continue;
		dep[v]=dep[u]+1;dp0=max(dp0,dep[v]);
		++c0[dep[v]];dfs(v,u);
	}
}

int dis;
void dfs1(int u,int fa){
	if(u==s){
		dis=dep[u];
		dep[u]=dp0=0;
		c0[0]=1;dfs(u,fa);
		return;
	}for(int i=0,v;i<d[u];++i){
		v=e[u][i];if(v==fa)continue;
		dep[v]=dep[u]+1;dfs1(v,u);
	}
}

ll ans;
inline void solve(){
	cin>>n>>y>>s;ans=0;
	for(int i=1;i<=n;++i){
		d[i]=0;e[i].clear();
	}for(int i=1,u,v;i<n;++i){
		cin>>u>>v;++d[u],++d[v];
		e[u].push_back(v);
		e[v].push_back(u);
	}dep[y]=0;dfs1(y,0);
	for(int i=0;i<=dp0;++i)
		c1[i]=c0[i],c0[i]=0;
	dp1=dp0;swap(y,s);
	dep[y]=0;dfs1(y,0);
	for(int i=max(dp0,dp1);i>=0;--i)
		ans+=((ll)c0[i]*c1[i+1]+(ll)c1[i]*c0[i+1]+(ll)c0[i]*c1[i])*(dis+i*2+1),\
		c0[i]+=c0[i+1],c1[i]+=c1[i+1];
	ans=ans*2-1;if(dis==1)ans+=2;
	for(int i=0;i<=n;++i)c0[i]=c1[i]=0;
	cout<<ans<<"\n";
}

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...