总结

今天要结束了哈哈。今天早上模拟，本来是信心赛的，结果由于大家的“出色表现”，标题不叫信心赛了哈哈。今天考的还行，不是很难。简单说一下，也要下课了，noip rp++！

题解

先简单评价一下本次考试。T1 std 是 \(O(N)\) 的，带一个 \(\log\) 的常数小也能过，还是很棒的！注：前三题都打了快读，足以可见数据的毒瘤。link。

T1

标程是开两个单调队列，一个单增，一个单减就行，双指针就行。如果带一个 \(\log\) 的话差不多只能二分能过，用一些容器可能就要超时了。[[单调队列]]

T2

很容易发现只要两个数满足一定的比例关系就行。我们考虑化简后的比例关系的规律。从 \(1:1\) 开始倒着枚举一下就可以很容易找到规律，和2的幂有关，然后暴力枚举和和比例，然后求出来就可以。很容易发现这样是 \(O(N\log N)\) 的，然后就变成了区间里面包含多少区间的问题。二维偏序。离线下来枚举右端点树状树组维护即可。[[树状数组]]

T3

题目说的是简单图，简单路径。显然 \(k<n\bigwedge k\le m\)。然后会发现 \(k\le 5\)。当 \(k < 5\) 时很简单，等于的时候就相当于假期计划的简单版，分类讨论打一下就可以。但是根据 DZhearMins 大佬的代码来看，当 \(k > 3\) 的时候暴力 dfs 即可。

T4

很神奇的题目，太好玩啦！反悔贪心的典题。可以发现最后问题转化成分开，前面选 0，后面选 1，容易发现先初始化为所有 1 的个数，然后往后移动，0的贡献为正，1为负，就变成最大前缀和。然后可以发现最后 \(k\) 次操作就是 \(k\) 段不相交的段和一个前缀的最大和。可以做题目：link。[[线段树]] [[反悔贪心]]