2023新年之前的最后一杯茶
01.16 CF 1691D
所有的子数组满足$max(a) \geq sum(a)$, 输出YES, 否则输出NO;
- $O(N)$复杂度
看到子数组的max => 单调栈, 每个元素作为max的范围可以求出来
=> 在这个范围内, 找到子数组的最大和(可以用前缀和+维护区间最值的数据结构完成)
=> 优化: 子数组最大和的检查, 可以放在单调栈弹出的时候检查(检查中间一段的和是否大于0(为什么? 因为单调栈维护最大值 所有小于的值必然会在达到边界直接出栈, 我们要找的负数必然会先出栈, 所以直接在这个时候检查即可))
01.17 CF 1409E
两条长度为$k$的线段, 覆盖最多的端点, 问可以最多覆盖多少点?
- 类似的题目：m条线段，LC 2209
01.18 ABC 222F
换根dp
- 求每个节点出发到其他节点的最大expense
- 端点带权重, 所以不仅需要考虑路径的最大值, 也要考虑只有一个端点(邻居节点+当前边), 端点为当前节点+最长路径等情况
01.19 CF 1721D
b数组可以任意排列
- $(a[1]^b[1]) & (a[2]^b[2]) & …& (a[n] ^b[n])$的最大值
从高到低排列bit位, 尽可能取1
- 问题：高位保证1的时候, 低位怎么搜索?
- 搜索+保持状态 | 使用数学&奇妙的掩码
01.20 CF 1598D
策略：
- 正难则反：直接数符合要求的数对很麻烦，因此要想到总数-不满足要求的数量
从n点取3点，横坐标互不相同/纵坐标互不相同
- 注意题目的重要信息：任何两个坐标不可能完全相同；
- 因此如果3个点的x坐标都一样，y坐标不可能相同；
- 那么不符合条件的数对只有两个x坐标相同且两个y坐标相同的情况