25 – 09 – 06 (补于 25 – 09 – 10)
在 CUMCM 2025 A 的解析出来且解析明确表示这题不应该调参前，我将一以贯之的痛骂这道破调参题
今日份题面：
给你一个二维数组
queries，其中queries[i]形式为[l, r]。每个queries[i]表示了一个元素范围从l到r（包括 l 和 r ）的整数数组nums。在一次操作中，你可以：
- 选择一个查询数组中的两个整数
a和b。- 将它们替换为
floor(a / 4)和floor(b / 4)。你的任务是确定对于每个查询，将数组中的所有元素都变为零的 最少 操作次数。返回所有查询结果的总和。
题目难度标的是困难，但其实上 $O(\log(n))$ 的解法还好， $O(1)$ 的公式没点思路真想不到，只能说 为什么 0xf3 是神这一块./
ok 那么分析题目，其实重点在于如何对 $[l, r]$ 区间内的 /4 操作进行计数，显而易见的是 /4 操作就是右移两位，那么我们就可以对当前区间的每个数进行右移次数统计，而题目表示一次可以对两个数同时进行操作，直觉上来说次数相近的分为一组收益最大(花费次数最小)，那么记一次操作一个数时所需的总次数为 $x$ 的话，此时(一次操作两个数)的最小次数为 $\lceil\frac{x}{2}\rceil$.
所以第一稿代码如下：
class Solution {
private long minimumActions(int l, int r) {
long x = 0;
for (int n = l; n <= r; n++) {
if (n == 0) continue;
int bits = Integer.SIZE - Integer.numberOfLeadingZeros(n);
x += (bits + 1) / 2; // ceil(bits / 2)
}
return (long) Math.ceil(x / 2.0);
}
public long minOperations(int[][] queries) {
long res = 0;
for (int[] q : queries) {
res += minimumActions(q[0], q[1]);
}
return res;
}
}
但是运行时 TLE 了，显然问题出在 $O(n^2)$ 的循环上，考虑预处理：通过按二进制位分组计算从 1 到 n 的总操作需求，从而将时间复杂度降低到 $O(\log (n))$。对于每个查询 $[l, r]$，计算 $\text{getSum}\ (r)\ – \ \text{getSum}\ (l-1)$ 得到区间总需求 $x$，然后最小操作次数为 $(x + 1) / 2$（整数除法下等价于 $ceil(x/2)$）所以有了第二稿：
class Solution {
private long getSum(long num) {
if (num <= 0) return 0;
long sum = 0;
long base = 1;
int bits = 1;
while (base <= num) {
long end = Math.min(base * 2 - 1, num);
long count = end - base + 1;
long actionsPerNum = (bits + 1) / 2; // ceil(bits/2)
sum += actionsPerNum * count;
base *= 2;
bits++;
}
return sum;
}
public long minOperations(int[][] queries) {
long res = 0;
for (int[] q : queries) {
long l = q[0];
long r = q[1];
long totalActions = getSum(r) - getSum(l - 1);
long minOps = (totalActions + 1) / 2;
res += minOps;
}
return res;
}
}
灵神的公式还没细看，感觉是归纳推导通式解，以后再看吧(咕咕)
以上
发表回复