2025/10/23CSP集训

· · 个人记录

T1

严重的细节错误，在判断是否合法的地方错了。

最后没有判断栈是否为空，直接获得-100分。

T2

过了， log n^2，可以直接二分+线段树贪心模拟。

当然，老师的思路是结论：最少的覆盖数量是最长上升子序列。

因为你第一个子序列里随便选一个数，再下一个里也能找到一个比他大的数，不然他们就可以直接合并。

用线段树优化DP即可。

T3

这道题我们要转换角度，从区间问题转移到每个元素上，判断每个元素可以成为哪些区间的最小值。

如果他可以是长度为 len 的区间的最小值，那么它也可以成为 [1,len-1]区间的最小值。

那么 R_i 和 L_i 为每个数能参与选择最小值的区间的右端点和左端点。

明显的，这个可以用单调栈维护。

最后，我们倒叙枚举区间长度计算答案即可。

T4

这个栈可以直接用单点修改线段树解决。

为了解决超限的问题，因为值域是非负数，所以我们设-1为超界情况，那么最后我们在判断改一下就可以了。

如果都是-1，答案也是-1.

如果有一个0，那么答案就是0。

如果有一个-1，且另一个不是0，答案是-1.

如果乘积超界，答案为-1.

否则为积。

线段树维护即可。