【题解】牛客国庆集训派对Day4
1.深度学习
最优的B显然等于n
2.异或求和
3.异或计数
考虑比较两个数的大小，肯定是在二进制下从高往低，找到第一个不同的位然后比较
枚举i表示b中所有数，二进制下高于i的那些二进制位的都与k对应位的二进制位相同
那么k的第i位肯定为1
b里一些数的第i位为1，且至少有一个数第i位为0
首先第i位为1的数必须有偶数个，这样才能满足第i位异或值为0
之后就是0...i-1的异或值要求为0，假设bx满足第i位为0，那么bx的0...i-1位可以随便选都不会违背bx小于等于k的条件
4.最小生成树
考虑作为一个生成树，每个点肯定往其他点连了边，那么我们让他们都连a最小的点即可
所以答案是
5.乒乓球
6.导数卷积
7.区间权值
考虑对于每个ax去算一下对于所有包含它的区间，w之和
则原式等于：
8.树链博弈
结论为：树上每个深度都有偶数个黑点的话后手必胜，否则先手必胜
首先，所有点多都是白点显然满足每层都是偶数个黑点，这个是题目规定的必败态
然后，如果是先手必胜的状态，那么肯定能通过一次操作达到先手必败的状态
且先手必败状态走一步只能达到先手必胜的状态
所以结论正确
另一种思路：用SG函数做的话，可以发现深度为i的点8g函数为2的i次幂
时间复杂度：O（n）
9.连通块计数
10.寻找复读机
按照题目意思模拟即可
每次记一下哪些人不可能是复读机，即第一个发言的人和上一条不一样的人
注意一句话都不说的人有可能是复读机
查看3道真题和解析
