Sorting with Twos
因为每次只能操作区间 \([1,2^{m}]\),所以 \([2^{m}+1,2^{m+1}]\) 内的所有数是同时进行操作的,它们需要满足非递减的性质,最后不要忘记结尾不能操作的数也需要满足条件。
1 | public static void solve() { |
Deja Vu
如果一个数能够被 \(2^{i}\) 整除,那么操作之后,它只能被所有小于等于 \(2^{i-1}\) 的二的幂整除。所以预处理所有修改,只保留满足递减顺序的修改,然后模拟即可。或者也可以直接修改,不用预处理,在修改之前判断一下是否比上次小就行。
1 | public static void solve() { |
Smilo and Monsters
比赛时我是排序 + 相向双指针模拟的,先干前面的怪物,如果计数和最后一个的怪物群数量相等,则使用终极攻击,比较麻烦的是双指针到达同一个位置时,需要特判一些情况。然后下面的解法,很简洁啊。似乎总是可以使用普通攻击干掉怪物总数的一半向上取整,并且使用终极攻击干掉总数的一半向下取整。然后排序数组并倒序遍历,使得一次终极攻击干掉尽可能多的怪物,这样就得到最少攻击次数。
1 | public static void solve() { |
Suspicious logarithms
\(f(x)\) 表示 \(x\) 的二进制表示中最高位的 \(1\) 所在的位数 \(y\),而 \(g(x)\) 表示满足 \(y^{z}<= x\) 条件的最大的 \(z\)。可以发现如果 \(y=2,x=10^{18}\),则 \(z=59\)。我们可以枚举所有 \(y\in[2,59]\),对于特定的 \(y\),枚举不同的 \(z\) 覆盖的区间范围。得到各个区间范围内所有数的 \(z\) 值,我们就可以在 \(O(\log{(r-l+1)})\) 的时间复杂度内执行查询。为了避免乘法溢出,在进行比较时需要使用除法。其他人代码有直接使用 \(\log\) 的,也比较简单啊,我还以为很麻烦,结果溢出没想到换除法。当然也可以维护前缀和,然后二分区间位置来进行查询。
1 | private static final int MOD = (int) 1e9 + 7; |
A Growing Tree
每个节点的编号是添加该节点时树的大小,因为修改操作不会影响还未添加到树上的节点,所以我们对每个修改操作添加一个编号(时间),表示修改所影响的范围。我们可以使用单点修改、区间查询的树状数组维护修改操作的编号,然后按照 DFS 序遍历树,每当遍历到一个节点,使用树状数组进行单点修改,因为遍历是 DFS 序,所以当前节点的祖先节点已经进行过修改操作,那么当前节点的答案就是所有大于等于该节点编号的修改操作之和。
那么有没有可能该答案会包含其他满足编号大于当前节点的非祖先节点的修改操作呢,不会包含,因为遍历是 DFS 序,DFS 返回时会取消对节点的修改操作,所以每当遍历到一个节点,修改操作只会包含其祖先节点的修改操作。特别注意,数组开 \(q+2\) 的大小,因为初始时有一个根节点,所以节点数量最多为 \(q+1\),然后编号从 \(1\) 开始。
1 | public static void solve() { |