P8411 「SvR-1」Problem Solution

y_kx_b · 2022-06-20 23:25:23 · 题解

本以为这题和几天前的 CCC 红题一样太简单不能交题解，后来发现这是月赛题。。。

题意

（首先题目与题目之间构成树的关系，因为 n 个点只有 n-1 条边（i 与 fa_i 之间建边））

定义一个节点的高兴程度为该节点到根的链上的点的点权的最小值，求所有点的高兴程度之和。

Sol.

这是一道树上乱搞题（确信）

常规做法（会被卡常）

先遍历一遍这个树（dfs 或 bfs 均可），对于搜到的每个节点 i 有：

（ans_i 表示节点 i 的高兴程度）

因为是搜索，所以对于搜到的每个节点 i，ans_{fa_i} 肯定被计算出来了。

最后统计，所有点的 ans 一加就行。（统计记得开 long long）

现在证明上面的递推方程是正确的：即对于上面计算出来的高兴程度值，总有一种做题方法与之契合。（上面计算出来的高兴程度值为最佳答案：易证。）

对于兄弟节点 i 和 j，不妨设 ans_i\leqslant ans_j，则先做 j 题再做 i 题，就可以各自达到 ans 值。

#define int uint
int a[N],fa[N],to[N<<1],ne[N<<1],head[N],idx=0,ans[N];
void add(int u,int v){
    ne[++idx]=head[u],to[idx]=v,head[u]=idx;
}
void dfs(int cur){
    for(int i=head[cur];i;i=ne[i])
        ans[to[i]]=min(ans[cur],a[to[i]]),dfs(to[i]);
}
void major(){
    int n=read();
    uint seed;scanf("%u",&seed);
    for (register int i = 1; i <= n; i++){
        a[i] = data::get_next(seed);
    }
    for (register int i = 2; i <= n; i++){
        fa[i] = data::get_next(seed) % (i - 1) + 1;
        add(fa[i],i);
    }
    dfs(1);
    long long sum=0;
    for(int i=1;i<=n;i++)
        sum+=ans[i];
    printf("%lld",sum);
}

考场 （指中考考场） 做法

和上面基本一样，但是 不用建树，所以时间会少很多

注意到

节点 i 的高兴程度只与节点 fa_i 的高兴程度有关，与兄弟节点无关

那么我们可以不按照树形搜，随便怎么都可以。 我这里是

#define int uint
int a[N],fa[N],ans[N];
void dfs(int cur){
//  if(ans[fa[cur]]==-1)
//      dfs(fa[cur]);
    ans[cur]=min(ans[fa[cur]],a[cur]);
}
void major(){
//  memset(ans,-1,sizeof ans);
    int n=read();
    uint seed;scanf("%u",&seed);
    for (register int i = 1; i <= n; i++){
        a[i] = data::get_next(seed);
    }
    for (register int i = 2; i <= n; i++){
        fa[i] = data::get_next(seed) % (i - 1) + 1;
    }
    ans[1]=a[1];
    long long ret=0;
    for(int i=2;i<=n;i++)
        dfs(i);
    for(int i=1;i<=n;i++)
        ret+=ans[i];
    printf("%lld",ret);
}

因为是顺着搜的，对于搜到的每个节点 i，ans_{fa_i} 肯定被计算出来了（因为 fa_i< i），所以注释部分可以去掉。

如果乱搜的话（当然会被卡），注释部分得加上（有可能搜到的节点的父节点 ans 未计算）

Thanks for reading!

Having fun coding!