A. Ahahahahahahahaha
通过作者半个小时的观察:全零和全一必定有一个是符合要求的答案,因为0的个数和1的个数至少有一个大于等于(frac{n}{2})。
B. Big Vova
贪心。
将剩余可用的数字用一个集合装起来,然后从小到大枚举下标(i),每次枚举可用的数字,保存使前缀GCD最大的那个数字,这个数字就是(b_i)。
C. Chocolate Bunny
通过观察可得:一次? i j
和一次? j i
可以确定(p_i)和(p_j)中的较小值及其下标。
证明:假设(p_i > p_j),那么(p_i \% p_j < p_j),(p_j \% p_i = p_j),所以两个返回值中较大的就是(p_i)和(p_j)中较小的那一个,即(p_j),并且可以知道较小值的下标为(j),同时较大值的下标也确定了为(i)。反之同理。
然后就可以记录较大值的下标(p),初始值为(1),然后从下标为(2)的位置开始遍历数组,每次用两个操作确定一个位置上的值,更新较大值的下表。
这样,用(2(n-1))次操作可以确定(1)至(n-1)的位置,且此时较大值的下标就是(n)的下标。
D. Discrete Centrifugal Jumps
单调栈优化DP。
现在有一个单调栈(up),栈中元素单调上升,然后有一个序列(h),遍历这个序列,不断尝试将当前元素加入单调栈。
现在要新加进来一个元素:
- 若元素的值大于栈顶对应元素,则直接加入。
- 反之,就将栈顶出栈,重复直到元素的值大于栈顶对应元素。
可以发现,将栈顶出栈后,若栈顶元素大于当前枚举到的元素,则新的栈顶元素到当前枚举到的元素之间的所有元素都大于两者,即新的栈顶对应元素到当前枚举到的元素的跳跃是一个满足条件3的跳跃。
同理可以维护一个栈中元素单调下降的单调栈(down)。
然后(dp_i)就只可能从(dp_{i-1})转移的来,或者是从(up)中的元素转移得来,或者是从(down)中的元素转移得来。