铁流-2题解&赛后总结

BigRooster · 2024-12-08 11:05:53 · 算法·理论

T1

就是一个带权的LIS问题，二分处理时记得乘一个权值，还有就是乘的是 len 不是 j。

T2

NOIP2024 T1

分块贪心处理，暴力+贪心可过80。

T3

首先考虑暴力。

预处理每个数左边比它大的数和右边比它大的数，然后先找右边，再对右边找左边，再对左边找右边即可。注意到从右边找左边可以用二分优化，但优化后无法处理最后一步，于是用前缀和处理。若右边比 a_i 大的数存于 r_i 中，则 qzh_{i,j} 表示对于所有 k \leq i，r_i 中下标大于 j 的数有多少个，那么在枚举第二步的时候二分找到所有可作为第二大数的下标区间，并使用前缀和找到其右边大于它且下标大于第三大数下标的个数，相加即可。

T4

不想说了。

T5

乘法原理+分讨秒了。