A
只要把,这个序列倒序输出即可。不难得到这样的 sort 序列一样。
B
贪心。因为和是0所以怎么搞都行
C
构造,不难发现 于是直接验证是否是循环节即可。需要注意的是如果
的数量比
和
的差值还少的话,那么无法使得一个循环节里的数量一样。
D
首先,如果树的直径没有爱丽丝跳的长度的两倍长,那么显然爱丽丝获胜,否则,如果两者的开始距离比爱丽丝跳的短或者是鲍勃的速度没有比爱丽丝的两倍还多的话,就是爱丽丝获胜。
我们可以研究在一个链上的形式,这几乎是显然的,那么合理的扩展在树上是客星的。
E
一个巧妙的解法,令 这样子,他的操作变为了,去掉一个0,后边的数-1即可。
首先,我们可以研究 ,而
不固定的情况。
分析一下设 是之前最多的取得个数,那么如果
这里的
是指变化之后。那么,显然
,否则
根据变化,我们只要动态的维护
即可。
不妨离线,对询问的右端点排序。具体的做法是:
- 对于每个询问,右端点排序,迭代右端点从小至大,维护每个左端点的
- 对于每一次新加入的
,我们只要找到第一个
的位置
即可 。(为了便于实现代码,这里 若
则
- 这样子对于
的位置 +1, 而其他位置不变即可。为了降低常数,我们可以使用差分+树状数组来完成。
- 那么,每个查询的左端点的答案救记录完毕。
如果要使得这个算法在线的话,可以使用可持久化的数据结构。
就是一个可以完成一下内容的数据结构
- 可持久化的
- 区间加
- 单点查询
这个我不会证明复杂度了。