【题解】牛客网NOIP赛前集训营-提高组（第七场）
A中国式家长2
题目大意
模拟一个挖脑洞游戏，判断行动过程是否合法，如果合法输出最终游戏结果
模拟
直接按题意模拟即可
在格子挖取后把周围的格子标记为开启，把当前格子标记为已挖取
注意一下行动力和悟性的计算方式
细心一点就可以满分了
在格子挖取后把周围的格子标记为开启，把当前格子标记为已挖取
注意一下行动力和悟性的计算方式
细心一点就可以满分了
B随机生成树
题目大意
有N个点从1到N编号，每个点有一个颜色
生成一棵树，每个点的父亲编号都是它的约数，
求树上最多有多少个同色联通块
生成一棵树，每个点的父亲编号都是它的约数，
求树上最多有多少个同色联通块
题意转换
考虑题目中联通块的定义：联通块中任意两点间都有一条同色的路径
因此如果一条边的两端点颜色不同，那么这条边是不能经过的
因此我们可以考虑断开两端颜色不同的边，联通块数等于剩下的森林中树的数目
一开始有一个联通块，每断掉一条边会增加一个联通块
因此联通块数 = 1 + （颜色和父亲不同的点数）
因此只需考虑每个点是否可以和父亲颜色不同即可
解法
因此如果一条边的两端点颜色不同，那么这条边是不能经过的
因此我们可以考虑断开两端颜色不同的边，联通块数等于剩下的森林中树的数目
一开始有一个联通块，每断掉一条边会增加一个联通块
因此联通块数 = 1 + （颜色和父亲不同的点数）
因此只需考虑每个点是否可以和父亲颜色不同即可
解法
依次枚举每个数的约数
可以直接枚举到根号，复杂度nsqrt(n)，但常数很小，可以通过
正解是对于每个数枚举它的倍数，这样复杂度为
N + N / 2 + N / 3 + N / 4 + … + N / N
（调和级数）
复杂度为O(NlogN)
C洞穴
可以直接枚举到根号，复杂度nsqrt(n)，但常数很小，可以通过
正解是对于每个数枚举它的倍数，这样复杂度为
N + N / 2 + N / 3 + N / 4 + … + N / N
（调和级数）
复杂度为O(NlogN)
C洞穴
题目大意
一个N点M边的有向图，给Q个询问
每个询问给定l, a, b，问是否存在一条以a开始以b结束，长度为l的路径
每个询问给定l, a, b，问是否存在一条以a开始以b结束，长度为l的路径
简单转移
f[a][len][b]代表是否存在一条从a到b，长度为len的路径
可以枚举一个中间点c进行转移（f[a][len – 1][c] && f[c][1][b]）
倍增
可以枚举一个中间点c进行转移（f[a][len – 1][c] && f[c][1][b]）
倍增
考虑到每条路径都可以拆分成若干条长度为2的次幂的路径
因此可以预处理f[a][i][b]代表是否存在一条从a开始，到b
结束，长度为2^i的路径
因为f值只可能为0/1，因此最后一维可以用bitset压缩
bitset<N>可以存储N位二进制数, & | 的复杂度均为N / 64
(如果使用pascal可以手写压位，每个integer可以存储32个
二进制位)
因此可以预处理f[a][i][b]代表是否存在一条从a开始，到b
结束，长度为2^i的路径
因为f值只可能为0/1，因此最后一维可以用bitset压缩
bitset<N>可以存储N位二进制数, & | 的复杂度均为N / 64
(如果使用pascal可以手写压位，每个integer可以存储32个
二进制位)
转移
处理询问
把l二进制表示之后依次枚举二进制中的每一个1
记录走过这么多步之后可以走到哪些点
假设当前可以走到a, b, c, d点
那么走过2^i步之后可以走到的点可以用
f[a][i] | f[b][i] | f[c][i] | f[d][i]求得
记录走过这么多步之后可以走到哪些点
假设当前可以走到a, b, c, d点
那么走过2^i步之后可以走到的点可以用
f[a][i] | f[b][i] | f[c][i] | f[d][i]求得
std
