根据难度排序。
个人总结向。
如果有什么讲的不清楚的欢迎留言私信交流~
A. 牛牛爱字符串（模拟）
题意： 提取字符串中的数字。
思路： 判断是否是数字，如果是就输出否则输出空格，重点在于字符串中含有空格，没注意看题wa了好久才发现要用getline。
B. 牛牛爱位运算（位运算）
题意： 给定数组，可用任意个元素相与，求得到的数最大。
思路： 相与只会越来越小，直接输出最大的元素就可以。
C. 牛牛爱博弈（思维）
题意： 问给出的石子总数n，每次可拿2^k个，每个人最优选择下谁会赢得比赛。
思路： 直接手推一下得到规律逢3 Alan必赢。
D. 牛妹爱数列（思维+模拟）
题意： 给定01数组，可以进行两种操作，把下标为x的数取非的运算操作和把1~x下标全部取非运算操作。
求全部变成0的最少操作数。
思路： 只有两种操作，就是当前位取非，还有当前以及之前所有位取非。
1.把0变成1 再全反转:
2.把1变成0 再全反转:
3.全0 和 全1反转:
4.不要忘记更新全1反转:
最后ans就是答案。
E. 牛妹游历城市（思维+位运算+最短路）
题意： 两个下标如果值按位与为1说明有边，边权为lowbit下按位与，求最少花费。
思路： 很明显的最短路，但是比赛的时候不会做。
结束后看了一些大佬的代码才恍然大悟，把32位二进制作为一些虚点来看待。
每个点皆与本身二进制位上为1的位连边，边权为 (1<<i) 。
然后就是最短路模板题了。
跑完记得 ，因为原本两个点之间只有一条边，但是你用一个虚拟的点作为中介导致连了两条同样花费的边。
F. 牛妹的苹果树（树链剖分）
题意： 给定一棵树，q次询问，给定区间求带权直径。
思路：
比赛的时候：
队友: 快做F，线段树维护直径
我: 感觉放在F没有那么简单
然后....队友就A了。
趁着这题赶紧学一波树链剖分，然后再来做这道题。
线段树每个节点维护当前区间的带权直径。
然后push_up的时候要记得和左儿子以及右儿子比较。
剩下的就是树链剖分的常规操作了。
京公网安备 11010502036488号