题很有趣。感觉Ag<Au
Ag
Cowlendar
首先如果只有小于等于3个不同a_i则无所谓,如果有多于3个则满足条件的数一定是差着L的倍数的数。
如果直接便利所有数会超时,可以优化遍历的数的数量,根号分治即可。不过不是很严格。
直觉上满足条件的数不会很多,这个来源是假设所有数的模数相等,则对于不满足的可以直接求出,则复杂度为拆分数。本题复杂度至多也是常数倍拆分数,则优化掉枚举ai个数这一点即可。
仔细分析发现我们可以用几个数的差值减少可能答案,因为只有最多四种余数的情况,所以抽屉原理枚举4个不同数两两差值即可。
Potion Farming
最小遍历次数为叶子数,然后贪心的去拿药水。
即从叶子设路线往上,能取(有路线没取过且遇到了药水)就取。
Cowmpetency
偏序关系,没有限制填最小的,有限制就填稍大的。
但是注意到hi得是第一个,也就是要保证多个偏序关系。
其实可以将区间限制的最后一个可填0的数看成代表元,类似前缀和维护即可。
Au
Walking in Manhattan
暴力是O(QN)的,排序后模拟即可。
正解则因为转弯和奇偶性相关的让我们可以直接二分查找。
Cowmpetency
和Ag那道同一个背景,$max_{ai<k<hi}(c_k)≤max_{k≤ai}(c_k)<c_{hi}$
值域明示会成为复杂度,做DP为O(nc^2),前缀和后为O(nc)
正解应该和区间相关,这样就有一些自由元,对区间排序后,可以DP
Nap Sort
二分。