省选模拟赛（IV）

本文主要是介绍省选模拟赛（IV），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

冲刺省选4月2日第四十三场

\(\color{white}{彼黍离离，彼稷之苗。行迈靡靡,中心摇摇。——《诗经·黍离》}\)

\(\color{white}{名之以：故都}\)

\(t2\) 上来直接转化出错沉溺在一维 \(dp\) 中 \(2h+\)，关键是还能过样例……
\(t3\) 在想高斯消元

B. 树点购买

设 \(f[u][0/1]\) 表示子树内有没有一个叶节点还未被覆盖的最优方案，\(g\) 表示方案数
那么

对于方案数，取到最值的转移都可以加进方案
对于合法转移，维护 \(op[u][0/1]\) 表示这个点能不能是最优 \(0/1\) 转移，同样进行转移，进行了 \(f[u][0]+a[u]\) 转移的是答案

C. 舰队游戏

设 \(f[u][i]\) 表示节点 \(u\) 血量为 \(i\) 时到终点的期望
那么 \(f[u][i]=min(f[1][h]+h-i,\frac{\sum f[v][i-d_v]}{deg}+1)\)
可以发现转移成环，那么二分 \(f[1][h]\) 的值看 \(dp\) 出的值是不是更小即可

这篇关于省选模拟赛（IV）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！