Difficulty: 1800 ～ 2200
题目链接
1106E
题意
给一个总时间 $n$，最多使用技能次数 $m$，$k$个节目，每个节目有$(s_i, t_i, d_i, w_i)$，表示每个可以看的时间段，看这个节目要到d秒后才能看别的节目，和看这个节目的收益w，每次有多个节目可以看的时候会选择w最大，其次选择d最大的，每次在时间x使用技能可以让你在x秒不能选择节目，x+1才可以，问时间n内的最小收益。
$(n\le10^5, m \le 200, k \le10^5)$
分析
- 定义dp[i][j]:前i秒使用j次技能最小收益。
- 问题难点在于：怎么对于一个i，找到w最大的节目，这个问题可以用一个优先队列维护一下。
1141F2
题意
给出n个数字，问最多有多少个不重叠的区间的和相同。
$(n\le 1500, a_i\le10^5)$
分析
直接枚举$n^2$个区间和，对于每种和找到最多不重叠区间和即可。
1101D
题意
给出一颗 $n$ 个节点的点权树，问最长的链满足链上的点权值的$gcd>1$的最长长度。
分析
- 树形dp
- $dp[i]:$ 表示以 $i$ 为终点的最大值。
- 答案只会出现 $dp_i$ 或者 一颗节点两个子树连接起来。
1045G
题意
x轴上给出n个点，和一个k，每个点有$(x_i, r_i，q_i)$，每个点可以到达$[x_i - r_i, x_i + r_i]$，问有多少对点满足可以互相到达且q值差值的绝对值不超过k。
$(n\le 10^5, k\le20)$
分析
- k最大只有20，显然要从k入手。
- 数据范围很大，需要动态开树。
- 对于每种值iq动态开一颗线段树，维护每个值下面有哪些位置有$a_i$，每次查询即对区间[iq - k, iq + k]查询合法的区间。
- 对于合法的区间，由于需要互相看到，对所有robot按照半径r从大到小排序，从大到小一边查询一边更新，因为r小的能找到r大的，那么r大的一定可以找到r小的。
Nowcoder30C
题意
分析
- 问题难点在于大招是一个区间且不同点的贡献还不变化的。
- 可以用线段树维护一下区间max，但区间修改的区间最大值并不是很好写，需要lazy标记。
- 实际上对于任意一个查询的区间，相邻点之间的差值的固定了，所以可以一开始随便赋值满足差值为A即可，这样不会影响最大值的位置。
- 所以单点修改，区间查询最大值位置即可。
1092D2
题意
给出n个连续的柱子的高度，每次只能用2✖️1的长方形放在柱子上面，问n个柱子是否可以变成同一高度且没有空隙。
分析
- 显然对于有矮的柱子，需要连续两个高度一样才行。
- 用栈维护一下这个过程。