【题解】牛客练习赛96
T1
按照
排序后比较相邻点能否到达
T2
考虑每一条边的贡献
显然对于同一层的边的贡献是相同的
一条边产生的贡献即两边点的个数相乘
计算一颗n层k叉树的点数可以暴力计算每一层
T3
有一个显然的性质：固定左端点之后随着右端点右移，最大值减最小值是单调递增的
所以可以利用单调栈维护一个滑动窗口)
或者枚举左端点二分右端点后用
计算)
T4
首先询问可以拆成-Q(1%2Cx-1))
注意到只有质因子为2时log2x才是和质因子个数相同的
在质因子为其他数时这两个差下降会很快
所以这题可以直接搜索不是2的质因子
T5
动态规划，从小到大枚举每一个数怎么放，
,代表当前枚举到
，
代表每个数和当前最大值的差，以及有没有使用过
转移有一些细节
T6
首先考虑没有一次交换
那么这个本质就是每个点的覆盖范围是在一个区间（左边第一个比它大的-右边第一个比它大的）
其实这个本质就是每个点的覆盖范围是在一个区间（左边第一个比它大的-右边第一个比它大的）
所以只需要在b数组中所有的这个元素都只出现在这个区间内且奇偶性与当前点相同
这个可以单调栈做到
因为有一次交换,所以肯定是至少有一个数不符合限制
那么考虑那个数，要让那个数符合限制，有两种情况
1.把那个数与另一个数交换
2.把限制那个数的数与另一个数交换（就是左边第一个比它大的和右边第一个比它大的）
总时间复杂度)
T2
考虑每一条边的贡献
显然对于同一层的边的贡献是相同的
一条边产生的贡献即两边点的个数相乘
计算一颗n层k叉树的点数可以暴力计算每一层
T3
有一个显然的性质：固定左端点之后随着右端点右移，最大值减最小值是单调递增的
所以可以利用单调栈维护一个滑动窗口
或者枚举左端点二分右端点后用
T4
首先询问可以拆成
注意到只有质因子为2时log2x才是和质因子个数相同的
在质因子为其他数时这两个差下降会很快
所以这题可以直接搜索不是2的质因子
T5
动态规划，从小到大枚举每一个数怎么放，
转移有一些细节
T6
首先考虑没有一次交换
那么这个本质就是每个点的覆盖范围是在一个区间（左边第一个比它大的-右边第一个比它大的）
其实这个本质就是每个点的覆盖范围是在一个区间（左边第一个比它大的-右边第一个比它大的）
所以只需要在b数组中所有的这个元素都只出现在这个区间内且奇偶性与当前点相同
这个可以单调栈做到
因为有一次交换,所以肯定是至少有一个数不符合限制
那么考虑那个数，要让那个数符合限制，有两种情况
1.把那个数与另一个数交换
2.把限制那个数的数与另一个数交换（就是左边第一个比它大的和右边第一个比它大的）
总时间复杂度
交通银行工作强度 39人发布
查看5道真题和解析