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