省选模拟赛(IV)
2022/4/3 0:03:46
本文主要是介绍省选模拟赛(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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?