<span>省选模拟88 题解</span>
A. 或许
容易发现 $u,v$ 联通仅当 $u \oplus v$ 能被集合 $S$ 通过 $\oplus$ 运算表出。
所以只需要维护线性基内元素个数。然后暴力的做法就是直接线段树分治。
然后有一个能进行删除的离线操作是，不断尝试用被删除最晚的替换线性基中的元素。
B. 这就是
对于完全图的情况，可以想到按照权值从小到大考虑每个点。
然后对于更加的一般的情况，只要预处理出每个点集是否是独立集，然后每次枚举一个点集表示集合内取值相同。
点集的权值就是集合内点的权值的最小值，然后用和上面类似的方法 dp 一下即可。
问题是如何恰好做到点集权值单调不降，然后对于每个方案还只统计一次，其实每次只要钦定转移未转移集合的最小值所在集合。
C. 人生吧
还是那个做法，对于求乘积的问题，可以把这个 $\gcd$ 质因数分解，然后考虑每一个 $p^k$ 造成的贡献。
然后根据部分分的提示，随便推一推式子弄个莫队上去就能做到 $O(n^{1.5} * log)$。
然后考虑根号分治，每个数 $> a_i^{0.5}$ 的质因子个数不超过 $1$ 个。
所以对于小的部分直接预处理前缀和，大的部分暴力莫队即可。
查看15道真题和解析
CVTE公司福利 269人发布
投递旷视等公司10个岗位 >