牛客练习赛 129 官方题解（简略）
A 三位出题人
如果我们画一张 的表，会发现题目要求等价于，在这张表每个位置填
或
，需要满足每列都不全是
且都不全是
，每列相互独立，于是答案为
。
B 数数
对 ~
之内的数进行筛质数（埃式筛或线性筛），对于所有质数
找出小于
的
的个数
，答案为
。
C 和天下
枚举 的前缀二进制
，按位与不严格小于其运算的两个数，可以将所有
的数全部用并查集合并。
D 搬家
我们可以发现，如果一个收纳箱从第 个物品开始装入物品，一定会有一个固定的结束点
，这与前面的物品无关，于是我们可以考虑用倍增优化上述过程，复杂度
。
E Alice and Bod
由于询问一个字符串是否对称，可以使用 维护，对于第二种操作，可以将字符串放到线段树上，但是由于有将一个字符由
变为
即带模意义下的加法，此时区间覆盖的懒标记不容易使用，但由于字符集合大小只有
，可以直接存下这
种在对应懒标记下的状态，由此解决区间覆盖。时间复杂度
F 网络通路
记 表示
为根节点
集合节点构成的树的最小权值，为了避免重复计算，我们钦定一棵树只有根节点可以往外连边，可以容易想到枚举
的子集和一条边进行转移，复杂度
。
考虑优化上述过程，一条边的贡献仅取决于它两侧的点数，于是我们可以在每轮转移前，预处理每条边对于每种集合的贡献，这样在转移时仅需考虑枚举根节点即可，复杂度 。