题目

RGB转十六进制

解题思路

如何将十进制转为十六进制？

通用方法：除 16 取余法（推荐掌握）

这是进制转换的通用算法，适用于任何进制：

💡 为什么逆序？
因为我们先得到的是个位，再是十位、百位……所以要反过来。

特殊技巧：格式化输出（竞赛可用，但非本质）

因为本题数据范围小（0~255），也可以用 Java 的字符串格式化：

String.format("%02X", num)

• %02X：输出大写十六进制，不足两位前面补 0
• 简洁，但“取巧”，不体现算法思维

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int g = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        // 方法一: 通用除16取余法(推荐掌握)
        String hex1 = "#" +
                toHex(r) +
                toHex(g) +
                toHex(b);
        System.out.println(hex1);

        // 方法二: 格式化输出(竞赛可用, 简洁)
        // String hex2 = String.format("#%02X%02X%02X", r, g, b);
        // System.out.println(hex2);
    }

    /**
     * 将 0~255 的十进制数转换为两位大写十六进制字符串
     * 使用通用的“除16取余法”
     *
     * @param num 十进制数
     * @return 两位十六进制字符串(如 "1A", "05", "FF")
     */
    private static String toHex(int num) {
        // 十六进制字符映射表
        char[] hexMap = {'0', '1', '2', '3', '4', '5', '6', '7',
                '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

        // 用于存储每一位(从低位到高位)
        StringBuilder digits = new StringBuilder();

        // 核心: 反复除以16, 取余数
        do {
            int remainder = num % 16;           // 取余数
            digits.append(hexMap[remainder]);   // 转为对应字符, 加入结果
            num = num / 16;                     // 更新为商, 继续循环
        } while (num > 0);

        // 此时 digits 是倒的(低位在前), 需要反转
        digits.reverse();

        // 确保结果是两位: 如果只有一位, 前面补 '0'
        if (digits.length() == 1) {
            digits.insert(0, '0'); // 在开头插入 '0'
        }

        return digits.toString();
    }

    /**
     * 优化方法: 针对 0~255 特化处理(可选, 竞赛中更快)
     * 直接取高位和低位, 无需循环
     */
    private static String toTwoDigitHex(int num) {
        char[] hexMap = {'0', '1', '2', '3', '4', '5', '6', '7',
                '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
        return "" + hexMap[num / 16] + hexMap[num % 16];
    }
}

---

相或为k

解题思路

定 n 个非负整数，问：是否能选出若干个数，使得它们的按位或（OR）结果等于 k？

核心观察

按位或的性质：

• 或运算只会让位变成 1，不会变回 0
• 一旦某一位是 1，就永远是 1

所以：

✅ 如果某个数 a[i] 在 k 没有的位上是 1，那它一定不能选！

例如：k = 6（二进制 110）

• 如果 a[i] = 5（二进制 101），它的第 0 位是 1，但 k 的第 0 位是 0 → 不能选！
• 因为一旦选了，结果的第 0 位就是 1，永远无法变回 0，不可能等于 k

筛选候选数

我们只考虑满足：(num | k) == k的数。

这个条件的含义是：

num 的所有 1 的位，都必须在 k 的 1 的位范围内

换句话说：num 是 k 的“子集”（按位意义）

贪心合并

把所有满足条件的数进行或运算，得到最终结果 result。

• 如果 result == k → 说明我们成功构造出了 k → 输出 Yes
• 否则 → 无法构造 → 输出 No

✅ 正确性：因为或运算是单调的，能选的都选上，结果最大，如果最大都不到 k，那就无解

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while (T-- > 0) {
            int n = sc.nextInt(); // 数字个数
            int k = sc.nextInt(); // 目标或值

            int result = 0; // 用于记录选出来的数的或运算结果, 初始为 0

            while (n-- > 0) {
                int num = sc.nextInt(); // 读入当前数字

                // 关键判断: 如果 num 的二进制 1 的位置, 超出了 k 的范围
                // 即: num 在某个 k 为 0 的位上是 1, 那么 num 不能被选
                // 条件 (num | k) == k 等价于: num 是 k 的子集（按位）
                // 举例: k=6 (110), num=2 (010) → 010|110=110 == k → 可选
                //       k=6 (110), num=5 (101) → 101|110=111 != k → 不可选
                if ((num | k) == k) {
                    // 如果 num 是 k 的子集, 则可以考虑选它
                    // 将它加入或运算结果中
                    result |= num;
                    // result = result | num, 逐步构造最终值
                }
                // 如果不满足条件, 跳过, 相当于不选这个数
            }

            // 最终检查: 是否成功构造出 k
            if (result == k) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

---

前缀和与前缀异或和

解题思路

为什么异或也可以用前缀？

我们熟悉加法的前缀和：
定义 prefixSum[i] = a[1] + a[2] + ... + a[i]，
那么区间和 sum(l, r) = prefixSum[r] - prefixSum[l-1]，
这是因为加法的逆运算是减法。

异或虽然不是加法，但它也满足类似的性质！

异或的“逆运算”是它自己

异或有两个关键性质：

• 任何数异或自己等于 0：x ^ x = 0
• 任何数异或 0 等于自己：x ^ 0 = x

因此，异或具有自逆性。
这意味着：
prefixXor[r] ^ prefixXor[l-1] = a[l] ^ ... ^ a[r]

因为前面重复的部分会被“抵消”（异或后变 0），只留下区间内的值。

类比记忆

运算	前缀数组	区间计算方式	逆运算
加法 +	prefixSum	prefixSum[r] - prefixSum[l-1]	减法 -
异或 ^	prefixXor	prefixXor[r] ^ prefixXor[l-1]	异或 ^

只要一个运算满足结合律和可逆性，就可以用前缀思想优化查询。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 数组长度
        int q = sc.nextInt(); // 询问次数

        // 存储原数组, 下标从 1 开始(方便前缀和计算)
        long[] nums = new long[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextLong();
        }

        // ========== 预处理前缀和 ========== //
        long[] prefixSum = new long[n + 5]; // 前缀和: 加法
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
            // prefixSum[i] 表示前 i 个数的和
        }

        // ========== 预处理前缀异或和 ========== //
        long[] prefixXor = new long[n + 5]; // 前缀异或和
        for (int i = 1; i <= n; i++) {
            prefixXor[i] = prefixXor[i - 1] ^ nums[i];
            // prefixXor[i] 表示前 i 个数的异或结果
        }

        // ========== 处理 q 次询问 ========== //
        while (q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            // 计算区间和: 利用前缀和的差
            long sum = prefixSum[r] - prefixSum[l - 1];
            // 计算区间异或和: 利用前缀异或和的异或
            // 因为: prefixXor[r] ^ prefixXor[l-1] = a[l] ^ ... ^ a[r]
            long xor = prefixXor[r] ^ prefixXor[l - 1];

            // 判断是否相等
            if (sum == xor) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

---

区间次方和

解题思路

为什么不能每次查询都暴力计算？

每个查询要求计算区间 [l, r] 内所有元素的 k 次方和。

如果每次暴力遍历区间并快速幂计算 a[i]^k，时间复杂度为 O(m⋅n⋅log⁡k)，在 n, m ≤ 1e5 下会超时。

我们必须通过预处理来实现快速查询。

关键观察：k 的范围非常小

题目保证：1 ≤ k ≤ 5，这是一个非常重要的突破口！

这意味着我们最多只需要处理每个数的 1~5 次方。

预处理每个数的幂次

我们可以预先计算每个 a[i] 的：

• a[i]^1
• a[i]^2
• a[i]^3
• a[i]^4
• a[i]^5

然后对每个幂次分别建立前缀和数组，这样就能在 O(1)O(1) 时间内回答任意区间查询。

多维前缀和思想

定义二维数组 prefix[i][k] 表示：

前 i 个数的 k 次方之和（对 10^9+7 取模）

这样，对于查询 l, r, k，答案就是： prefix[r][k] - prefix[l-1][k]

注意：由于是模运算下的减法，需要加上模数再取模，避免负数。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int MOD = 1000_000_007;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long[] nums = new long[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextLong();
        }
        // 预处理前缀和数组: 因为 k 最大为 5, 所以我们为 k=1 到 5 分别维护一个前缀和
        // prefix[i][k] 表示前 i 个数的 k 次方之和
        long[][] prefix = new long[n + 5][6]; // 第二维大小为 6, 使用 1~5 索引
        for (int i = 1; i <= n; i++) {
            long cur = 1; // 用于累乘计算 a[i]^k
            for (int k = 1; k <= 5; k++) {
                cur = (cur * nums[i]) % MOD; // 计算 a[i]^k
                prefix[i][k] = (prefix[i - 1][k] + cur) % MOD; // 前缀和累加
            }
        }
        while (m-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int k = sc.nextInt();
            // 查询区间 [l, r] 的 k 次方和
            long ans = (prefix[r][k] - prefix[l - 1][k] + MOD) % MOD;
            System.out.println(ans);
        }
    }
}

---

K倍区间

解题思路

暴力解法的问题

最直接的想法是枚举所有区间 [i, j]，计算子数组和并判断是否为 k 的倍数，时间复杂度是O(n^3)。
使用前缀和可以快速得到区间和，但总时间复杂度仍为 O(n^2)。
当 n ≤ 1e5 时，n^2=1e10，会超时(算法赛中我们一般要求计算规模最多为1e8~1e9)。

核心观察：同余定理

我们要求区间 [i, j] 的和是 k 的倍数，即： (prefix[j] - prefix[i-1]) % k == 0

根据同余定理，这等价于： prefix[j] % k == prefix[i-1] % k

也就是说：两个前缀和模 k 同余，它们之间的区间和就是 k 的倍数。

例如看样例:

// nums     = 1  2  3  4   5
// prefix   = 1  3  6  10  15
// 取余k     = 1  0  0  0   1
// 我们可以任意找两个余数为0的前缀和作差, 得到的子数组的和一定是k的倍数
// 那么问题就转化成了, 现在有3个0, 任意选两个作差, 有多少种选法, 即求组合数C(3, 2)

利用哈希表优化计数

我们不需要知道具体是哪两个位置，只需要知道：

对于每一个余数 r，有多少个前缀和的余数等于 r

设余数 r 出现了 cnt 次，那么从中任选两个位置（前后顺序确定），就能构成一个 K 倍区间。
组合数为：C(cnt, 2) = cnt * (cnt - 1) / 2

特别注意：前缀和从 0 开始

我们要考虑从下标 1 开始的区间，即 [1, j]，它的和是 prefix[j] - prefix[0]。
如果 prefix[j] % k == 0，那么 [1, j] 就是 K 倍区间。
所以必须初始化：余数 0 出现了 1 次（对应 prefix[0] = 0）

参考代码

方法一: 前缀和代码(不能AC)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }
        // 记录前缀和
        long[] prefix = new long[n + 5];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                // 计算子数组 [i, j] 的和
                long sum = prefix[j] - prefix[i - 1];
                if (sum % k == 0) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

方法二: AC代码

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }
        // prefix[i] 存储前缀和模 k 的结果
        int[] prefix = new int[n + 5];
        // 用哈希表记录每个余数出现的次数
        Map<Integer, Integer> remainderCnt = new HashMap<>();
        // 初始化: 前缀和为 0 的情况（即 prefix[0]）余数为 0，出现 1 次
        remainderCnt.put(0, 1);
        for (int i = 1; i <= n; i++) {
            // 计算当前前缀和模 k
            prefix[i] = (prefix[i - 1] + nums[i]) % k;
            // 将当前余数的计数加 1
            remainderCnt.put(prefix[i], remainderCnt.getOrDefault(prefix[i], 0) + 1);
        }
        // 变成了组合数学问题, 对于每种余数可以得到的k倍区间个数就是C(cnt, 2)
        // 因为我们需要的是不同位置的作差, 所以是组合而不是排列
        // 所以我们需要对每个余数的出现次数进行组合计算
        // 例如前缀和余数为1的情况有cnt个, 那么任意选2个不同位置作差, 得到的就是k倍区间, 所以组合数就是C(cnt, 2)
        long ans = 0;
        // 遍历每个余数的出现次数
        for (int cnt : remainderCnt.values()) {
            // 组合数学: C(cnt, 2) = cnt * (cnt - 1) / 2
            ans += (long) cnt * (cnt - 1) / 2;
        }
        System.out.println(ans);
    }
}

---

商品库存管理

解题思路

核心观察：撤销一个操作的影响范围

每个操作是对区间 [L, R] 内所有商品库存 +1。
如果我们撤销第 i 个操作，相当于对这个区间内的每个商品库存 -1。

• 如果某个商品当前库存 > 1，减 1 后仍 > 0，不会变成 0。
• 如果某个商品当前库存 == 1，减 1 后变为 0，会新增一个零库存商品。
• 如果某个商品当前库存 == 0，减 1 后变为 -1（但实际不会发生，因为原操作没执行），但在我们的模型中，这类商品不受影响。

因此，只有当前库存为 1 的商品，在被撤销操作覆盖时，才会变成 0。

分步求解策略

1. 先模拟所有操作的最终状态
   使用差分数组快速处理所有区间 +1 操作，还原出最终的库存数组。
2. 统计初始零库存商品数
   记录所有库存为 0 的商品数量，记为 zeroCnt。
3. 预处理“库存为 1”的前缀和
   构建一个前缀和数组 onePrefix[i]，表示前 i 个商品中，库存为 1 的数量。
   这样可以在 O(1)时间内查询任意区间 [L, R] 内有多少个库存为 1 的商品。
4. 回答每个查询
   对于第 i 个操作 [L, R]，如果不执行它：
   • 原来的 zeroCnt 个零库存商品仍然为 0
   • 区间 [L, R] 内所有库存为 1 的商品都会变成 0
   • 所以答案 = zeroCnt + (onePrefix[R] - onePrefix[L-1])

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        // 记录每次操作的左右端点
        int[][] op = new int[m][2];
        // 差分数组, 初始都是 0
        int[] diff = new int[n + 5];

        for (int i = 0; i < m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            diff[l]++;
            diff[r + 1]--;
            op[i][0] = l;
            op[i][1] = r;
        }

        // 还原为原数组, 顺便统计一下现在有多少个 0
        int[] nums = new int[n + 5];
        int zeroCnt = 0;
        for (int i = 1; i <= n; i++) {
            nums[i] = nums[i - 1] + diff[i];
            zeroCnt += (nums[i] == 0 ? 1 : 0);
        }

        // 现在要计算的是撤销某个操作后为 0 的有多少个
        // 只有元素为 1 的值撤销后会有影响
        // 所以我们需要记录一个前缀和表示 1 的个数
        int[] onePrefix = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            onePrefix[i] = onePrefix[i - 1] + (nums[i] == 1 ? 1 : 0);
        }

        // 尝试对每一个操作都撤销一次, 并计算撤销后为 0 的个数
        for (int i = 0; i < m; i++) {
            int l = op[i][0];
            int r = op[i][1];
            int cnt = onePrefix[r] - onePrefix[l - 1] + zeroCnt;
            System.out.println(cnt);
        }
    }
}

---

闪耀的灯光

解题思路

核心观察：开关操作的循环节

每盏灯的亮度变化具有周期性：

• 初始亮度为 a[i][j]
• 每按一次开关，亮度减 1，直到 a[i][j] - c
• 再按一次，亮度恢复为 a[i][j]

这意味着：每按下 c + 1 次开关，灯的状态回到初始值。
因此，实际有效操作次数为：k % (c + 1)。

例如，若 c = 3，则周期为 4：

按 0 次：a
按 1 次：a-1
按 2 次：a-2
按 3 次：a-3
按 4 次：a（恢复）
按 5 次：a-1（同按 1 次）

所以只需计算 k_mod = k % (c + 1) 次真实减量。

问题转化：区间和与统一减法

每次操作后，矩形区域内每盏灯都减少了 k_mod，因此总亮度减少量为： k_mod * 区间内元素个数

最终答案 = 原始区间和 - 减少的总量。

使用二维前缀和优化查询

我们需要快速计算任意矩形区域的初始亮度和。
定义 prefix[i][j] 为从 (1,1) 到 (i,j) 的子矩阵和：

prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

对于查询 (x1,y1) 到 (x2,y2) 的和：

sum = prefix[x2][y2] - prefix[x2][y1-1] - prefix[x1-1][y2] + prefix[x1-1][y1-1]

这样每次查询可在 O(1) 时间完成。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int c = sc.nextInt();
        int[][] matrix = new int[n + 5][m + 5];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        // 预处理二维前缀和数组
        long[][] prefix = new long[n + 5][m + 5];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                prefix[i][j] = matrix[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            }
        }

        int T = sc.nextInt();
        while (T-- > 0) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            int k = sc.nextInt();
            // 计算原始区间和
            long sum = prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1];
            // 实际有效操作次数: 利用循环节性质
            k %= (c + 1);
            // 计算区间内元素个数
            int cnt = (x2 - x1 + 1) * (y2 - y1 + 1);
            // 总亮度 = 原始和 - 每个元素减少的量 * 元素个数
            long ans = sum - (long) k * cnt;
            System.out.println(ans);
        }
    }
}