P1059 · OFFICIAL SOLUTION

P1059 新水濯旧隍官方题解

Gioush OJ · P1059 新水濯旧隍

【题意分析】

当前宫室自身不足平均值时，剩余藏宝量不可能全部落在平均值更低的儿子辖域中。因此至少有一个儿子辖域仍达到目标平均值，沿它下降即可。

【部分分：测试点 111】

当 $n\leq 15$ 时，可以询问所有宫室的转域藏量。
按照深度从大到小处理。宫室 $u$ 自身剩余藏量等于其转域藏量减去所有儿子转域藏量之和。
这样能够还原全部藏量，再直接选择藏量最大的 $b$ 个宫室清洗。

【部分分：测试点 222】

当 $b=1$ 时，只需找到一间藏量不少于全体平均值的宫室。
从明光殿开始。若当前宫室自身藏量达到平均值就清洗它，否则至少有一个非空儿子转域的平均藏量不小于全局平均值。
向这个儿子继续下降，最终一定能够找到目标宫室。

【部分分：测试点 333】

特殊性质 A 保证王宫是一条链，每个宫室至多只有一个儿子。
询问当前宫室与其儿子的转域藏量，二者之差就是当前宫室自身藏量。
沿链下降即可寻找不低于当前平均值的宫室。每轮需要 $\mathcal O(h)$ 次询问。

【部分分：测试点 444】

设当前尚未清洗的宫室数为 $r$ ，剩余藏量和为 $V$ 。本轮寻找一间藏量至少为 $V/r$ 的宫室。
当前宫室的自身藏量可以由当前转域藏量减去两个儿子转域藏量得到。
若自身藏量不足 $V/r$ ，则至少有一个非空儿子转域的平均藏量不小于 $V/r$ ，向该儿子下降即可。

【正解】

清洗一间藏量至少为 $V/r$ 的宫室后，新的剩余藏量至多为

V-\frac Vr=V\frac{r-1}{r}.

连续进行 $b$ 轮后，剩余藏量至多为 $v(n-b)/n$ ，因此取得的藏量至少为 $bv/n$ 。
代入评分比例 $p=\min(1,ns/(bv))$ ，得到 $p=1$ ，所以这是一种对任意合法数据都能取得满分的通用策略。
每个宫室至多有两个儿子。沿一条根到叶路径下降时，每层至多询问两个儿子转域。
一轮的询问次数不超过 $2h+1$ ，全部 $b$ 轮不超过 $2bh+b$ 。根转域总量可以在开始时询问一次并持续维护。
题目给出的上限为 $2bh+20$ ，实现时复用已经得到的当前转域藏量即可满足限制。

【参考代码】

1#include "moat.h"2#include <vector>3using namespace std;4 5void Init(int c,int T){return;}6 7void Play(int c,int n,int b,vector<int> parent){8    vector<vector<int>> Son(n+1);9    vector<int> Size(n+1,1),Cleaned(n+1,0),Order;10    Order.push_back(1);11    for(int u=2;u<=n;u++) Son[parent[u]].push_back(u),Order.push_back(u);12    for(int i=n-1;i>0;i--) Size[parent[Order[i]]]+=Size[Order[i]];13    long long Total=Scout(1);14    for(int Round=0;Round<b;Round++){15        long long Current=Total;16        int Remain=n-Round,u=1;17        while(true){18            vector<long long> Sum(Son[u].size());19            long long ChildSum=0;20            for(int i=0;i<(int)Son[u].size();i++) Sum[i]=Scout(Son[u][i]),ChildSum+=Sum[i];21            long long Own=Current-ChildSum;22            if(Own*Remain>=Total) break;23            int Next=0,NextIndex=-1;24            for(int i=0;i<(int)Son[u].size();i++){25                int v=Son[u][i],Count=Size[v]-Cleaned[v];26                if(Count&&Sum[i]*Remain>=Total*Count){Next=v;NextIndex=i;break;}27            }28            u=Next;Current=Sum[NextIndex];29        }30        Total-=Clean(u);31        for(int v=u;v;v=parent[v]) Cleaned[v]++;32    }33}