Java教程

NOIP多校模拟20

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!