NOIP多校模拟20
2021/11/2 6:39:54
本文主要是介绍NOIP多校模拟20,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
T1:
询问期望,但是显然的计数题,根据期望的线性性,可以想到转化
问题转化为求每一位的平均值的期望,考虑共有(n * m)!种情况,于是
只需要统计每种情况前i位的和除以总情况即可
打表可以发现为sigma * (n * m - 1)!于是线性处理逆元即可
T2:
最优策略问题考虑策略是什么,对于这类区间随机取值模型,每次
取值的期望可以抽象为均值
考虑问题的性质,对于当前点的决策由之后点的结果决定,于是考
虑倒推,设f[i]表示i点及之后点的期望结果,转移时判断i - 1点区间均值
比较并加权转移即可
T3:
考虑首先比较明显的思路是笛卡尔树求出最大值控制的区间,问题
转化为子区间成绩的和
貌似是一种套路,然而并不会,利用多项式计数——考虑求出当前
点左右两侧乘机前缀和,相乘即可,原理显然,于是Dfs过程中传递结
构体(存储处理当前点信息所需要的信息),多项式递推即可
T4:
套路题,首先u^2可以根据实际意义容斥为sigma (d^2 | i)u(d)
于是直接代入+和式变换即可,事件复杂度O(tsqrt(n))仍然无法通过,
发现可以直接三次数论分块,再转换枚举顺序,预处理u * i^2即可
这篇关于NOIP多校模拟20的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)