NOIP2024模拟2
都不会,哈哈哈
我在此发表暴论,在 \(T4\) 放签到题的都是 SB。做不出来的更 SB。
-
T1:酸碱度中和
签到题。
排序,二分答案,记录一下这一组的最小的,最小的和最多的差大于二倍答案就新开一组。
-
T2:聪明的小明
状压。
50pts 是显然状压,考虑延续其思路。
压出状态发现只有最后一位是有用的,最后一位具体是什么也没用,只有位置有用。
于是用 \(0/1\) 表示前 \(m\) 个位置中这个位置是否是最后一个。
转移比较显然。
要预处理状态和前 \(m\) 位的值,个人感觉有点卡常(滚掉一维加上取模优化就可以在 150ms 左右了)
-
T3:线段树
区间 DP。
考虑从一个地方截断会有什么贡献,发现只会对过截断点且不完全包含此查询区间的线段有 \(1\) 的贡献。
容斥后就是一个二维偏序,因为 \(n\) 巨小,直接暴力二维前缀和即可。
最后记得加上每个线段最初的 \(1\) 贡献。
-
T4:公路
签到题。
显然贪心,考虑只有两种策略:加到恰好到下一个比他小的点,加满后走到可以走的最小的。
我不说谁看出贪心策略,以为是平衡树维护凸壳的斜率优化,只写了 80pts 部分分,还过了。