脚本宝典收集整理的这篇文章主要介绍了多校NOIP22，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

T1：

　　发现暴力枚举，由于阶乘与指数增长速度，因此可以枚举

阶乘项数，然而并不能够通过，发现在同一项存在大量冗余枚举

而a，b上下界显然为n开d次方，暴力在范围内Check即可

　　考场上时间复杂度严重算错，5min想到正解然而被pass，想

到分支log层处理分界点log个位置，以为复杂度是对的，然而实际

上在每一层均摊复杂度为O(n)，一定要算对时间复杂度

T2：

　　构造题，考虑首先当每组元素为偶数时一定可以首尾一一配对

考虑每组元素为奇数，同样，问题出在多出的一组，那么考虑将其

与最后两组配对，使得这三组和为定值

　　类比偶数情况，将这三组构造等差数列即可

T3：

　　正解咕

　　暴力显然主席树区间修改+二分版本值，由于之前并没有做过主

席树的题，这里记一下主席树的Case，首先版本之间一定要求区分

性，即修改的点不能继承，主席树实际上是继承不被修改的点，其

次由于是直接继承，因此区间/单点查询时，要类似标记永久化，将

沿途所有节点的sum统计起来

T4：

　　考虑期望计算的方法，由于不同情况计算不同（复杂），因此统

计所有情况贡献除以总情况数并不使用，考虑线性分解

　　这里是一种不太一样的香型分解，考虑发现断掉一条边的期望如

何转化，我们显然是尽量在一个图上topsort，那么发现其影响即为在

出点上减去一个定值，在其余出点上加上一个定值，那么可以差分统

计，这样做的意义为将断边的期望影响线性差分，再在原图上统计所

有情况即可（乘以概率使得最终图上即为所有情况期望影响）

脚本宝典总结

以上是脚本宝典为你收集整理的多校NOIP22全部内容，希望文章能够帮你解决多校NOIP22所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。