CF2040E Control of Randomness
Tag：树、期望、DFS
题目描述
给定一个具有 \(n\) 个结点的树， 现在在结点 \(v\) 有一个人， 有 \(p\) 个硬币。 在第 \(i\) 步时：
若 \(i\) 为奇数，则向 \(1\) 号节点移动一步。
若 \(i\) 为偶数，可以有一下选择： 1. 花费一个硬币，向 \(1\) 号节点移动一步。 2. 不花费硬币，在当前结点的相邻节点中随机挑选一个移动一步。
一共 \(q\) 次询问，每次给定 \(v,p\)，求最优情况下走到 \(1\) 号结点的期望步数。
数据说明：
\(2 \leq n \leq 2 \times 10^3, 1 \leq q \leq 2 \times 10^3\)
\(\sum n,\sum q \leq 2 \times 10^3\)
分析
注意： 在下文描述中我们将 \(1\) 号节点当做根节点，所以将奇数步移动的本质看做是向父亲节点移动。
分析步数为奇数偶数时的操作，发现分开讨论并不方便， 我们尝试每 \(2\) 步看做一个整体进行讨论。
如果我们把每 \(2\) 步看做一个整体， 那么这个移动的本质就是，先向父亲节点移动一次， 之后在当前结点的父亲节点的相邻节点中随机选择一个结点进行移动。
因为题目要求的期望是到达父亲节点的期望步数， 所以我们把在偶数步中使用硬币和不使用硬币分成两种情况进行讨论。
首先考虑在偶数步中不消耗硬币，因为奇数步一定会向父亲节点移动一次， 所以我们真正关心的是在偶数步中不消耗硬币的情况下能否再次向父亲节点移动一次， 这个与我们在当前结点经过奇数步的移动之后所抵达的结点有关系。 我们将当前结点的父亲节点的度数（相邻节点个数）记作 \(x\)， 那么在偶数步中，能再次向父亲节点移动的概率为 \(\frac{1}{x}\)， 偶数步再次向父亲节点移动的期望则为 \(x\)。
那么我们再考虑使用硬币的情况，在这种情况下我们可以使用一个硬币直接向父亲节点再做出一次移动， 因此再次向父亲节点移动的期望为 \(1\)。
值得注意的是，上述的讨论我们都将一个奇数步和一个偶数步看做一个整体进行讨论， 因此我们最后求的期望是要 \(\times 2\) 的。
那么解题思路就很明显了， 我们先处理出所有节点的父亲是谁， 之后记录出从当前结点抵达 \(1\) 号节点路上的所有结点的度数， 因为我们可以消耗硬币向父亲节点移动， 我们贪心地选择前 \(p\) 个期望最大的结点，在这些结点使用硬币移动， 之后将所有数字求和乘以二就是答案。
有一个值得注意的小细节，若当前结点的父亲是 \(1\) 号节点时，我们直接把答案加一就可以了， 因为这一步可以直接通过一个奇数步抵达 \(1\) 号节点
代码实现
void NeverSayNever() {
int n,q; cin >> n >> q;
vector<vector<int>> adj(n+1);
vector<int> fa(n+1);
for (int i = 1; i < n; ++i) {
int u,v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
auto find_fa = [&](auto&& self,int cur,int f)->void{
fa[cur] = f;
for(auto& nxt : adj[cur]){
if(nxt == f) continue;
self(self,nxt,cur);
}
};
find_fa(find_fa,1,0);
vector<int> vec;
int ans = 0;
auto dfs = [&](auto&& self, int cur)->void{
if(fa[cur] == 1){
ans++;
return;
}
if(cur == 1) return;
vec.push_back(adj[fa[cur]].size());
self(self,fa[fa[cur]]);
};
while(q--){
int v,p; cin >> v >> p;
vec.clear();
ans = 0;
dfs(dfs, v);
std::sort(vec.begin(), vec.end(),[&](int x,int y){
return x > y;
});
for (int i = 0; i < p; ++i) {
if(vec.size() > i) {
vec[i] = 1;
}
}
ans += std::accumulate(vec.begin(), vec.end(),0LL) * 2 % MOD;
cout << ans % MOD << endl;
}
}
日志
本页面创建于 2025/1/21 10:01