多校NOIP21

本文主要是介绍多校NOIP21，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

T1：

　　惯性思路，想按位考虑，打表找规律或者分析每一位的贡献

　　正解是比较明显的容斥，考场上一种思路长时间无法做出应

及时更换思路

　　首先不考虑3的倍数的限制，那么问题转化为n个数or值为t的

方案数，按位容斥即可，枚举至少有i为为0

　　考虑如何加上3的倍数这一限制，发现二进制下若该位为奇数

位则模3为2，偶数位模3为1，证明简单的数学归纳即可，那么考虑

在钦定i为or为0时，我们需要使得所有的x为3的倍数，容易想到由

1与2构成3，那么我们需要具体考虑奇数位与偶数位的贡献

　　单纯钦定i位为0并不能计算，于是用范德蒙恒等式拆分组合数

再背包求出模3为0的方案数即可

T2：

　　期望的好题，考察了期望计算的两种方法，然而考场看错题以

为求树总长的期望，然而要求路径的期望

　　考虑问题可以转化为树总长*2-树直径长的期望，第一部分采用

期望的线性分解，转化为每一条边在树上的概率（E = P * G）每条

边贡献为一，直接树形DP乘以组合系数即可

　　考虑如何求树的直径，数据规模性不大，考虑枚举钦定两点为

树的直径，问题转化为判断存在多少情况，即期望=总情况权值和/

总情况数，发现另一点能加入该树，当且仅当该点到两端点距离小于

直径，或者等于且字典序大于树的直径的字典序，钦定字典序关系

是为了避免重复计算，最终该点对当直径的方案数即为C(cnt,k - 2)

T3：

　　矩阵行列式+仙人掌上DP 咕

T4：

　　计数DP黑白棋

这篇关于多校NOIP21的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！