第一题:小美的彩带
输入：
6 3
1 1 4 5 1 4
L 2
L 3
R 12
输出：
1
3
3
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取 n 和 qint n = scanner.nextInt();int q = scanner.nextInt();// 读取彩带的颜色数组Set<Integer> totalColor = new HashSet<>();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();totalColor.add(a[i]);}// 全部颜色的种类int diffColor = totalColor.size();// 初始位置设为 0int startLeft = 0, startRight = n - 1;// 处理每次剪彩带的操作for (int i = 0; i < q; i++) {char c = scanner.next().charAt(0);int x = scanner.nextInt();Set<Integer> colorSet = new HashSet<>();// 优化：如果 x >= n，直接输出 diffColorif (x >= n) {System.out.println(diffColor);// 更新起始位置if (c == 'L') {startLeft = (startLeft + x) % n;} else {startRight = (startRight - x + (x / n + 1) * n) % n;}continue;}// 剪裁操作if (c == 'L') {// 从左往右剪for (int j = 0; j < x; j++) {colorSet.add(a[(startLeft + j) % n]); // 使用模运算来处理循环数组}startLeft = (startLeft + x) % n;} else if (c == 'R') {// 从右往左剪for (int j = 0; j < x; j++) {colorSet.add(a[(startRight - j + n) % n]); // 从右侧剪裁，计算索引}startRight = (startRight - x + n) % n;}// 输出当前剪裁段的不同颜色的数量System.out.println(colorSet.size());}scanner.close();}
第二题：捕获敌人
题目描述
解题方法：二维前缀和 + 计算范围
import java.util.Scanner;public class Main {static final int N = 1000;static int[][] g = new int[N + 10][N + 10];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();a++; b++; // 最大间隔++，前缀和下标从1开始处理，防止边界问题// 与N取mina = Math.min(a, N);b = Math.min(b, N);for (int i = 0; i < n; i++) {int x = sc.nextInt(), y = sc.nextInt();g[x][y]++; // 读入敌人坐标}for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) {g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1]; // 二维前缀和预处理 公式一}}int res = 0;// 枚举一下所有长宽是ab的矩形，(i,j)为右下角，取maxfor (int i = a; i <= N; i++) {for (int j = b; j <= N; j++) {res = Math.max(res, g[i][j] - g[i - a][j] - g[i][j - b] + g[i - a][j - b]); // 求某一个子矩阵的值 公式二}}System.out.println(res);}
}
第三题：购买物品
解法：三维01背包dp[i][j][k]表示在前 i 个物品，一共拥有 j 元，拥有 k 个折扣券的情况下,最多可以买到多少物品。cost[i][j][k]表示在上述的购买情况并且使用优惠券的情况下，最低的开销。
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();int[] original = new int[n + 1], discount = new int[n + 1];int[][][] dp = new int[n + 1][x + 1][y + 1], cost = new int[n + 1][x + 1][y + 1];for (int i = 1; i <= n; i++) {original[i] = sc.nextInt();discount[i] = sc.nextInt();}for (int i = 1; i <= n; i++) {for (int j = 1; j <= x; j++) {for (int k = 0; k <= y; k++) {// 情况1：不买dp[i][j][k] = dp[i - 1][j][k];cost[i][j][k] = cost[i - 1][j][k];// 情况2：直接买if (j - original[i] >= 0) {if (dp[i - 1][j - original[i]][k] + 1 > dp[i][j][k]) {dp[i][j][k] = dp[i - 1][j - original[i]][k] + 1;cost[i][j][k] = cost[i - 1][j - original[i]][k] + original[i];}else if (dp[i - 1][j - original[i]][k] + 1 == dp[i][j][k]) {cost[i][j][k] = Math.min(cost[i][j][k], cost[i - 1][j - original[i]][k] + original[i]);}}// 情况3：拿优惠券买if (j - discount[i] >= 0 && k >= 1) {if (dp[i - 1][j - discount[i]][k - 1] + 1 > dp[i][j][k]) {dp[i][j][k] = dp[i - 1][j - discount[i]][k - 1] + 1;cost[i][j][k] = cost[i - 1][j - discount[i]][k - 1] + discount[i];}else if (dp[i - 1][j - discount[i]][k - 1] + 1 == dp[i][j][k])cost[i][j][k] = Math.min(cost[i][j][k], cost[i - 1][j - discount[i]][k - 1] + discount[i]);}}}}// 统计最低开销int res = Integer.MAX_VALUE;for (int i = 1; i <= n; i++) {for (int j = 1; j <= x; j++) {for(int k = 0; k <= y; k++) {if (dp[i][j][k] == dp[n][x][y]) {res = Math.min(res, cost[i][j][k]);}}}}System.out.println(dp[n][x][y] + " " + res);sc.close();}
}