GJOI 5.27 题解-海口c网

GJOI 5.27 题解

article/2025/8/22 5:51:40

1.洛谷 P8981 距离

参考了这篇题解，我的比较口胡。

题意

给以一颗含有 $n$ 个节点的树，定义树上任意两点的 $u, v$ 之间的距离 $d_{u,v}$ 为两点之间点的数量。

如果树上两点 $u, v$ 满足，对于树上的任意节点 $x$ ，都满足 $d(u,x)\le d(u,v)$ ,并且满足 $d(x,v)\le d(u,v)$ ，那么我们称无序对 $(u, v)$ 为好点对。

树上每个节点 $i$ 都有一个点权 $v_i$ ， $v_i$ 的值为两点之间的最短路径经过 $i$ 的好点对的数量。求 $\displaystyle\sum_{i=1}^n {v_i}^k \bmod998244353$ 。

$1\le n\le 5000000$ ， $k\in\{1,2\}$ 。

思路

容易想到，好点对只能是直径的两端点，因为在树上直径是能出现的最长长度了。题目转化为每个点被直径覆盖的次数。

有一个性质，就是若树上所有边边权均为正，则树的所有直径中点重合。那么我们考虑将直径中点 $M i d$ 提到根去，因为所有直径都会过 $M i d$ 这个点。

我们计算每个节点 $i$ 最多可以向下延伸多少个节点 $mdis_i$ ，以及这种长度的数量 $num_i$ 。中点可能有两个？分类讨论。先考虑计算，除 $M i d$ 外所有节点的覆盖次数，我们统计最长路和次长路的总条数 $c n t 1, c n t 2$ ，对于 $M i d$ 的儿子们：

当直径为奇数个点时，中点只有一个。此时中点的孩子的 $m d i s$ 应该都是一样的；
当直径为偶数个点时，此时中点的孩子中，会有且仅有一个孩子的 $m d i s$ 比其他孩子大 $1$ 。这时经过中点的直径数量就应该是这个特殊孩子的 $n u m$ 与其他孩子的 $n u m$ 的乘积。

遍历下面的其他节点处理完 $M i d$ 和儿子就能遍历其他的节点了。

注意勤取模。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e6+9,mod=998244353;
ll n,k;
ll idx,head[N];
struct edge
{ll to,next;
}e[N<<1];
void addedge(ll u,ll v)
{idx++;e[idx].to=v;e[idx].next=head[u];head[u]=idx;
}
ll dis[N],d1,d2,D;
void dfs1(ll u,ll fa)
{if(dis[u]>dis[d1])d1=u;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dis[v]=dis[u]+1;dfs1(v,u);}
}
ll fat[N];
void dfs2(ll u,ll fa)
{fat[u]=fa;if(dis[u]>dis[d2]){d2=u;D=dis[u];}for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dis[v]=dis[u]+1;dfs2(v,u);}
}
ll mdis[N],num[N];
//以中点为根，节点i向下能走最长距离及其数量 
ll V[N];
void dp(ll u,ll fa)
{mdis[u]=1,num[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dp(v,u);if(mdis[u]<mdis[v]+1){mdis[u]=mdis[v]+1;num[u]=num[v]; }else if(mdis[u]==mdis[v]+1)num[u]+=num[v];}
}
ll ans;
void dfs3(ll u,ll fa,ll w)
{if(k==1)ans=(ans+w*num[u]%mod)%mod;else ans=(ans+w*num[u]%mod*w%mod*num[u]%mod)%mod;for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa||mdis[u]!=mdis[v]+1)continue;//并非长链 dfs3(v,u,w);}
}
int main()
{scanf("%lld%lld",&n,&k);if(n==1){puts("0");return 0;}if(n==2){puts("2");return 0;}for(int i=1;i<n;i++){ll u,v;scanf("%lld%lld",&u,&v);addedge(u,v);addedge(v,u);}dfs1(1,0);dis[d1]=0;dfs2(d1,0);ll Mid=d2;for(int i=1;i<=(D+1)/2;i++)Mid=fat[Mid];dp(Mid,0);ll cnt1=0,cnt2=0;for(int i=head[Mid];i;i=e[i].next){ll v=e[i].to;if(mdis[v]==D/2)cnt1+=num[v];else if(mdis[v]>D/2)cnt2+=num[v];}
//	cout<<cnt1<<" "<<cnt2<<endl;
//	分类讨论Midll VMid=0;if(D&1){for(int i=head[Mid];i;i=e[i].next){ll v=e[i].to;if(mdis[v]>D/2)V[v]=cnt1;else if(mdis[v]==D/2)V[v]=cnt2;}VMid=cnt1*cnt2%mod;}else //中点有两个 {for(int i=head[Mid];i;i=e[i].next){ll v=e[i].to;if(mdis[v]==D/2)V[v]=cnt1-num[v];}ll tem=cnt1;for(int i=head[Mid];i;i=e[i].next){ll v=e[i].to;if(mdis[v]==D/2){tem-=num[v];VMid=(VMid+tem*num[v]%mod)%mod; }}}//计算Mid外其他节点for(int i=head[Mid];i;i=e[i].next){ll v=e[i].to;if(mdis[v]>=D/2)dfs3(v,Mid,V[v]);}if(k==1)ans=(ans+VMid)%mod;else ans=(ans+VMid*VMid%mod)%mod;printf("%lld",ans);return 0;
}

2.SMOJ 任务兼容

题意

你有一个由 $n$ 个任务组成的列表，每个任务有一个对应的难度值。你需要将这些任务划分为若干个组，每组至少包含两个任务。划分需要满足以下条件：

每组任务必须是连续的。第一组任务必须从第一个任务开始，最后一组任务必须以最后一个任务结束。
相邻的组之间必须连续，即第 i 组的最后一个任务的下一个任务必须是第 i+1 组的第一个任务。
每组内的每个任务必须至少有一个其他任务与它“兼容”。两个任务兼容的条件是它们的难度值的最大公约数不为 $1$ 。

你的目标是找到满足条件的最大组数。如果无法满足条件，则输出 $- 1$ 。

思路

感觉对了，但只有 $\text{89pts}$ 捏。

考虑 $\Theta(n^2)$ 做法，设一维状态： $f_i$ 表示最后一组以 $i$ 结尾的最大组数，我们要枚举一个 $j$ 使 $j\sim i$ 成为一组，然后 $f_i=\max\{f_{j-1}\}+1$ 。

我们考虑怎么 $\Theta(1)$ 判定 $j\sim i$ 可以成为一组。

我们 $\Theta(n^2)$ 算出每个数左右最近的非互质数的位置，记作 $pre_i,nxt_i$ 。对于左端点 $j$ ，如果 $nxt_j<i$ ，那么需要有 $pre_j$ 出现。其实这是改变了新组的最右左端点。考虑更新这个东西，记作 $mi$ ，更新后如果 $j\le mi$ ，那么 $j\sim i$ 可以成为新的一组。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2003,inf=0x3f3f3f3f;
ll n,k,a[N];
ll pre[N],nxt[N];
ll f[N];
int main()
{scanf("%lld",&n);if(n==1){puts("-1");return 0;}for(int i=1;i<=n;i++)scanf("%lld",&a[i]),f[i]=-inf;for(int i=1;i<=n;i++){pre[i]=-inf;nxt[i]=inf;for(int j=i-1;j>=0;j--){if(__gcd(a[i],a[j])>1){pre[i]=j;break;}}for(int j=i+1;j<=n;j++){if(__gcd(a[i],a[j])>1){nxt[i]=j;break;}}}
//	for(int i=1;i<=n;i++)
//	cout<<i<<" "<<pre[i]<<" "<<nxt[i]<<endl; for(int i=1;i<=n;i++){ll mi=inf;for(int j=i;j>=1;j--){if(nxt[j]>i)mi=min(mi,pre[j]);if(i!=1&&mi>=j)f[i]=max(f[i],f[j-1]+1)/*,cout<<"f["<<i<<"] <= f["<<j-1<<"]+1="<<f[j-1]+1<<endl*/; }//	cout<<f[i]<<" ";}
//	for(int i=1;i<=n;i++)
//	cout<<f[i]<<" ";if(f[n]==-inf)puts("-1");else printf("%lld",f[n]);return 0;
}

3.CF1515E Phoenix and Computers

题意

在这里插入图片描述
$3\le n\le 400$ ， $M\in[10^8,10^9]$ 。

思路

一道好玩的计数题。

我们观察左右电脑打开后，这些电脑的打开方式：

一段电脑 $1\sim A_1-1$ 被手动打开， $A_1$ 被自动打开；
$A_1+1\sim A_2-1$ 被手动打开， $A_2$ 被自动打开；
……；
$A_{m-1}+1\sim A_m-1$ 被手动打开， $A_m$ 被自动打开；
$A_m+1\sim n$ 被手动打开（ $A_m+1\le n$ ）。

简要地说，就是一段被手动打开，接着一个被自动打开的，再接一段手动打开的。

我们设连续 $k$ 个全都手动打开的方案数为 $g_k$ ， $f_{i,j}$ 表示前 $i$ 台电脑手动打开了 $j$ 台的方案数，我们考虑枚举一段有 $k$ 台手动打开的电脑，最前面有一台自动打开的，那么将从 $f_{i-k-1,j-k}$ 转移过来。

在所有连续打开的 $j$ 台中，选择将要手动打开的 $k$ 台，即 $\dbinom{j}{k}$ ；然后开 $k$ 台方案数为 $g_k$ ，那么有转移方程：
$f_{i,j}\leftarrow f_{i-k-1,j-k}\times\binom{j}{k}\times g_k$

答案就是 $\displaystyle\sum_{i=1}^n f_{n,i}$ 。

我们现在再来考虑 $g_k$ 怎么算。我们枚举中间开了哪一台，然后向两边扩展；从 $x$ 开始开，对于 $x$ 右边的电脑，它们的相对开机顺序必须是 $x + 1, x + 2, ..., n$ 对于 $x$ 左边的电脑，它们的相对开机顺序必须是 $x - 1, x - 2, ..., 1$ 。两边的开机顺序是可以穿插（合并）在一起的。即：
$g_k=\sum_{i=1}^k \binom{k-1}{k-i}$

记得勤取模。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=405,inf=0x3f3f3f3f;
ll n,mod;
ll f[N][N],g[N];
ll C[N][N];
void init()
{for(int i=0;i<N;i++)C[i][0]=C[i][i]=1;for(int i=1;i<N;i++)for(int j=1;j<i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
int main()
{scanf("%lld%lld",&n,&mod);init();for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)g[i]=(g[i]+C[i-1][i-j])%mod;for(int i=1;i<=n;i++)//前i台电脑 {f[i][i]=g[i];for(int j=1;j<i;j++)//手动开j台  for(int k=1;k<j;k++)//一段k台被手动打开 f[i][j]=(f[i][j]+f[i-k-1][j-k]*g[k]%mod*C[j][k]%mod)%mod;}ll ans=0;for(int i=1;i<=n;i++)ans=(ans+f[n][i])%mod;printf("%lld",ans);return 0;
}