[省选集训2022] 模拟赛1
中心城镇问题
题目描述
给出一个 \(n\) 个点的树，第 \(i\) 个点的权值是 \(a_i\)，现在要选择一些点建立据点，要求任意两个据点之间的距离必须大于 \(k\)，问选出据点的最大权值和是多少。
\(n\leq 10^6\)
解法
我发现我学不懂长链剖分的原因是指针基础为?零，而今天终于把我的心头大患解决了。
其实这题根本不需要任何题意转化，我们把两个据点的限制在 \(\tt lca\) 处考虑即可，那么可以直接掏出树形 \(dp\)，设 \(dp[u][i]\) 表示点 \(u\) 内最浅的据点离 \(u\) 的距离是 \(i\)，选出的最大权值和。转移考虑合并两棵子树，考虑最浅的点是再原来的子树中还是在新的子树中，我们枚举最浅点的距离 \(j(j\leq dep[v])\)，设 \(o=\max(j,k-j+1)\)，表示选取其他点的最小深度，这要求我们再求出 \(tmp[u][i]\) 表示 \(dp\) 数组的后缀最大值：
\[dp[u][j]\leftarrow \max(dp[v][j-1]+tmp[u][o],tmp[v][o-1]+dp[u][j]) \]然后简单讲一下长链剖分需要用到的指针知识：*p 作为一个指针可以用 p=a 操作来指向数组的第一个元素，然后直接用 p[x] 就相当于取 *(p+x)，所以我们的 \(dp\) 数组就设置成一个指针数组即可，再根据深度设置指针的初始位置。
实现细节：\(dep[u]\) 代表子树 \(u\) 的长链长度，那么 \(dp[u]\) 范围是 \([0,dep[u])\)，转移时要注意卡好范围。
#include
#include
using namespace std;
const int M = 1000005;
#define int long long
const int inf = 1e18;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,tot,f[M],a[M],son[M],dep[M],qwq[M<<1];
int *dp[M],*tmp[M];
struct edge {int v,next;}e[M<<1];
void upd(int &x,int y) {x=max(x,y);}
void pre(int u,int fa)
{
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
pre(v,u);
if(dep[v]>dep[son[u]]) son[u]=v;
}
dep[u]=dep[son[u]]+1;
}
void dfs(int u,int fa)
{
if(son[u])
{
dp[son[u]]=dp[u]+1;
tmp[son[u]]=tmp[u]+1;
dfs(son[u],u);
}
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa || v==son[u]) continue;
dp[v]=dp[u]+dep[u];
tmp[v]=tmp[u]+dep[u];
dfs(v,u);
for(int j=dep[v];j;j--)
{
int o=max(j,k-j+1),t=-inf;
//the min-dis lies in v
if(o1) upd(tmp[u][0],tmp[u][1]);
}
signed main()
{
freopen("central.in","r",stdin);
freopen("central.out","w",stdout);
n=read();k=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i 心理阴影
题目描述
给定一棵 \(n\) 个节点的有根树，现在有一个排列，满足若 \(u\) 是 \(v\) 的父节点则 \(u\) 在 \(v\) 之前，问这个排列逆序对的期望。
\(n\leq 4000\)
解法
有一个 \(O(n^5)\) 的算法可以拿到 \(50\) 分，就是你枚举两个点，然后用组合数加 \(dp\) 算贡献即可。
正解却是直接 \(dp\) 算贡献，考虑到逆序对是一个二元关系，那么我们同样也去设计二元关系的状态，设 \(dp[u][v]\) 表示把子树 \(u,v\) 合并之后 \(u,v\) 之间产生的期望逆序对数，转移考虑第一个位置是 \(u\) 还是 \(v\)：
\[f(u,v)=\frac{siz_u}{siz_u+siz_v}\cdot (\sum_{x\in son_u} f(x,v)+g(u,v))+\frac{siz_v}{siz_u+siz_v}\cdot(\sum_{x\in son_v} f(u,x)+g(v,u)) \]其中 \(g(u,v)\) 表示子树 \(v\) 中比 \(u\) 小的数的个数，\(siz_u\) 表示子树 \(u\) 的大小，前面的系数就是考虑有 \(\frac{siz_u}{siz_u+siz_v}\) 的概率 \(u\) 放在第一位，因为这相当于从 \(siz_u+siz_v\) 个数中选出 \(siz_u\) 个，选到红色的概率。然后计算 \(u\) 和 子树 \(v\) 的贡献，然后因为 \(u\) 的儿子是互相独立的，就可以递归到子问题了，后面那部分的解释类似。
总状态数 \(O(n^2)\)，转移均摊 \(O(1)\)，所以时间复杂度 \(O(n^2)\)
总结
我觉得关键是二元关系的处理吧，似乎这类题有这种特殊的方法，比如
#include
#include
#include
#include
using namespace std;
const int M = 4100;
const int MOD = 1e9+7;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,rt,tot,ans,f[M],fa[M];
int dp[M][M],inv[M],siz[M],g[M][M];
struct edge{int v,next;}e[M<<1];
void dfs(int u,int p)
{
siz[u]=1;fa[u]=p;
for(int i=u+1;i<=n;i++) g[i][u]++;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==p) continue;
dfs(v,u);siz[u]+=siz[v];
for(int j=1;j<=n;j++) g[j][u]+=g[j][v];
}
}
int get(int x,int y)
{
if(~dp[x][y]) return dp[x][y];
int res=(siz[x]*g[x][y]+siz[y]*g[y][x])%MOD;
for(int i=f[x];i;i=e[i].next) if(e[i].v^fa[x])
res=(res+siz[x]*get(e[i].v,y))%MOD;
for(int i=f[y];i;i=e[i].next) if(e[i].v^fa[y])
res=(res+siz[y]*get(x,e[i].v))%MOD;
res=res*inv[siz[x]+siz[y]]%MOD;
return dp[y][x]=dp[x][y]=res;
}
signed main()
{
freopen("nightmare.in","r",stdin);
freopen("nightmare.out","w",stdout);
n=read();rt=read();inv[0]=inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i