P3156 【深基15.例1】询问学号

解题思路

很简单的一道题，但是由于n、m的数据很大，要用Java的I/O流读入和输出。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.PrintWriter;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(System.out);StreamTokenizer st = new StreamTokenizer(br);// 读取学生个数 n 和询问次数 mst.nextToken();int n = (int) st.nval;  // 学生个数st.nextToken();int m = (int) st.nval;  // 询问次数// 存储学号的数组int[] id = new int[n];// 读取学号for (int i = 0; i < n; i++) {st.nextToken();id[i] = (int) st.nval;}// 处理查询并输出结果for (int j = 0; j < m; j++) {st.nextToken();int index = (int) st.nval;// 因为输入的查询索引是从 1 开始的，所以我们需要减去 1pw.println(id[index - 1]);}// 关闭 PrintWriterpw.flush();pw.close();br.close();}
}

P3613 【深基15.例2】寄包柜

解题思路

1. 数据结构选择

• 使用 HashMap：由于柜子的数量和每个柜子的格子数量都是动态的，使用 HashMap 是最合适的选择。外层 HashMap 存储每个柜子的状态，内层 HashMap 存储柜子内每个格子的物品。

2. 处理存储操作

• 对于操作 1 i j k：
  • 检查柜子 i 是否存在，如果不存在，初始化一个新的 HashMap。
  • 如果 k 是 0，则清空格子 j 的物品；否则，将物品 k 存入格子 j。

3. 处理查询操作

• 对于操作 2 i j：
  • 直接从柜子 i 的格子 j 中获取物品并输出。因为题目保证了查询的格子一定存有物品，因此不需要额外的检查。

import java.util.*;public class Main{public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt(); // 板子的数量int q = input.nextInt(); // 操作次数// 使用 HashMap 存储每个寄包柜的状态Map<Integer, Map<Integer, Integer>> lockers = new HashMap<>();for (int i = 0; i < q; i++) {int operationType = input.nextInt();int iLocker = input.nextInt();if (operationType == 1) { // 存储操作int jSlot = input.nextInt();int kItem = input.nextInt();// 存储物品 k 到柜子 i 的格子 jlockers.putIfAbsent(iLocker, new HashMap<>());if (kItem == 0) {lockers.get(iLocker).remove(jSlot); // 清空该格子} else {lockers.get(iLocker).put(jSlot, kItem); // 存入物品}} else if (operationType == 2) { // 查询操作int jSlot = input.nextInt();// 查询柜子 i 的格子 j 中的物品System.out.println(lockers.get(iLocker).get(jSlot));}}}
}

P1449 后缀表达式

解题思路

• 数据结构：使用栈（Stack）来存储操作数。后缀表达式是逆波兰表示法，适合用栈来处理。

• 遍历表达式：逐字符遍历后缀表达式字符串，处理每个字符：

  • 数字处理：当遇到数字时，读取完整的数字（可能是多位数），将其转换为整数后压入栈中。
  • 运算符处理：当遇到运算符（+, -, *, /）时，从栈中弹出两个数字（注意顺序），执行相应的运算，然后将结果再次压入栈中。
  • 结束符处理：遇到结束符@时，停止计算。

import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);String expression = input.next();System.out.println(evaluatePostfix(expression)); // 输出结果}public static int evaluatePostfix(String expression) {Stack<Integer> stack = new Stack<>();int i = 0;while (i < expression.length()) {char c = expression.charAt(i);if (Character.isDigit(c)) {StringBuilder number = new StringBuilder();// 读取完整的数字while (i < expression.length() && Character.isDigit(expression.charAt(i))) {number.append(expression.charAt(i));i++;}// 将数字压入栈中stack.push(Integer.parseInt(number.toString()));} else if (c == '@') {break; // 结束符，停止计算} else {// 处理运算符int b = stack.pop();int a = stack.pop();int result = 0;switch (c) {case '+':result = a + b;break;case '-':result = a - b;break;case '*':result = a * b;break;case '/':// 整数除法，向零取整result = a / b;break;}stack.push(result); // 将结果压入栈中}i++; // 移动到下一个字符}// 最终结果return stack.pop();}
}

P1996 约瑟夫问题

解题思路

1. 数据结构:使用一个布尔数组 flag 来记录每个人是否已经出队。数组的大小设置为n+1.

2. 循环出队:

   • 外层循环 k 从0到n-1，表示每次出队的操作（总共出队 n 次）。
   • 内层循环 i 控制实际的跳过人数，目标是找到第 m 个未被访问的人。
   • 每次循环：
     • 先将 s 加1（代表当前位置），如果 s 超过 n，则重置为1（实现循环）。
     • 检查 visit[s]，如果 s 已经被访问过，i-- 使得这个循环不会结束，继续寻找未访问的下一个人。
   • 当找到可以出队的人后，输出这个人的位置 s，并将 visit[s] 标记为 true。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int m = input.nextInt();int index = 0;boolean[] flag = new boolean[200]; // 访问用默认值初始化的数组(false)for (int i = 0; i < n; i++) { // 总共n次退出队列for (int j = 0; j < m; j++) {index++; // 增量索引if (index > n) index = 1; // 如果index超过n，就绕行到1if (flag[index]) j--; // 如果已经访问过，则递减j以重复循环}System.out.print(index + " "); //输出当前位置flag[index] = true; //标记位置索引}}
}

P1160 队列安排

解题思路

链表

• 数据结构：定义了一个Student类，包含左右指针和一个标记，用于表示学生是否输出。

• 操作：通过add方法将学生插入到链表中，支持在左边或右边插入。

• 输入处理：首先输入学生数量，接着依次输入每个学生的编号和插入位置（左或右）。链表的初始状态是只有一个头结点。

• 标记处理：读取需要标记为不输出的学生编号，并将其flag设为1。

• 输出未标记学生：遍历链表，从头结点开始，输出所有flag为0的学生编号。

import java.util.Scanner;// 学生类，包含左右指针和输出标记
class Student {int l, r; // 左右手，表示链表中的前驱和后继int flag; // 标记该学生是否输出
}public class Main {static final int mx = 100010; // 最大学生数量static int n, m; // 学生数量和标记数量static Student[] stu = new Student[mx]; // 学生数组// 静态代码块，初始化学生数组static {for (int i = 0; i < mx; i++) {stu[i] = new Student(); // 创建每个学生对象}}// 插入学生到链表中public static void add(int i, int k, int f) {if (f == 1) { // 如果在左边插入stu[k].r = stu[i].r; // k的右指针指向i的右指针stu[k].l = i; // k的左指针指向istu[i].r = k; // i的右指针指向kstu[stu[k].r].l = k; // k的右指针的左指针指向k} else { // 如果在右边插入stu[k].r = i; // k的右指针指向istu[k].l = stu[i].l; // k的左指针指向i的左指针stu[i].l = k; // i的左指针指向kstu[stu[k].l].r = k; // k的左指针的右指针指向k}}public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt(); // 输入学生数量stu[0].r = 0; // 初始化头结点的右指针stu[0].l = 0; // 初始化头结点的左指针add(0, 1, 1); // 将第一个学生添加到链表// 依次添加学生for (int i = 2; i <= n; i++) {int x = input.nextInt(); // 插入位置int f = input.nextInt(); // 插入方向（左或右）add(x, i, f); // 添加学生}m = input.nextInt(); // 输入需要标记的学生数量while (m-- > 0) {int x = input.nextInt(); // 需要标记的学生编号stu[x].flag = 1; // 标记学生为不输出}// 输出未标记的学生for (int i = stu[0].r; i > 0; i = stu[i].r) {if (stu[i].flag == 0) { // 如果学生未被标记System.out.print(i + " "); // 输出学生编号}}}
}

树（不能AC，最后两个测试点会空间超限）：仅供参考

• 数据结构：使用一个结构体（Node）表示树的每个节点，包含左右子节点指针和一个标记变量用于表示节点是否被删除。

• 树的构建：

  • 从输入中读取节点数量，然后逐个输入节点的父节点和插入位置（左或右）。
  • 根据输入信息，动态构建树的结构，设置节点的左右子节点。

• 节点删除：

  • 在输入中读取需要删除的节点编号，并将其标记为被删除（v=1）。

• 中序遍历：

  • 实现中序遍历（左子树 -> 当前节点 -> 右子树），在遍历过程中检查每个节点的删除标记，只有未被删除的节点才会被输出。

• 输出结果：

  • 最终输出所有未被标记为删除的节点编号，按照中序遍历的顺序。

import java.util.Scanner;class Node {int lc, rc, v; // lc: 左儿子, rc: 右儿子, v: 是否被删
}public class Main {static Node[] d = new Node[101000]; // 节点数组// 中序遍历输出static void dfs(int x) {if (x == -1) return; // -1 表示没有节点dfs(d[x].lc); // 搜索左儿子if (d[x].v == 0) System.out.print(x + " "); // 输出未被删的节点dfs(d[x].rc); // 搜索右儿子}public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt(); // 输入节点数量d[1] = new Node();d[1].v = 0;d[1].lc = d[1].rc = -1; // 初始化第一个节点// 初始化节点for (int i = 2; i <= n; i++) {int x = input.nextInt();int y = input.nextInt();d[i] = new Node();d[i].lc = d[i].rc = -1; // 初始化当前节点if (y == 0) { // 插入左儿子if (d[x].lc != -1) {d[i].lc = d[x].lc; // 当前节点的左儿子设为 d[x] 的左儿子d[x].lc = i; // d[x] 的左儿子设为当前节点} else {d[x].lc = i; // 否则，把 d[x] 的左儿子设为当前节点}} else { // 插入右儿子if (d[x].rc != -1) {d[i].rc = d[x].rc; // 当前节点的右儿子设为 d[x] 的右儿子d[x].rc = i; // d[x] 的右儿子设为当前节点} else {d[x].rc = i; // 否则，把 d[x] 的右儿子设为当前节点}}}int m = input.nextInt(); // 输入删除数量for (int i = 1; i <= m; i++) {int x = input.nextInt();d[x].v = 1; // 删除节点}dfs(1); // 从根节点开始中序遍历输出}
}

P1540 [NOIP2010 提高组] 机器翻译

解题思路

• 数据结构选择：

  • 使用一个队列（ArrayDeque或LinkedList）来存储当前内存中的单词。
  • 使用一个集合（HashSet）来快速查找当前内存中是否已有某个单词。

• 处理输入：

  • 读取内存容量 M 和文章长度 N，以及接下来的 N 个单词。

• 遍历单词列表：

  • 对于每个单词：
    • 如果单词已在内存中（即在集合中），则不查词典。
    • 如果单词不在内存中，则查词典，增加查字典的次数，并将单词添加到内存中。
      • 如果内存已满，首先从队列中移除最早加入的单词（FIFO），并从集合中删除。
      • 然后，将新单词加入队列和集合。

• 输出结果：

  • 输出总的查字典次数。

代码在编译器中会报错：拆箱的 'memoryQueue.poll()' 可能产生 'java.lang.NullPointerException'，

不过测试数据都有效，所以可以AC。 

import java.util.*;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);// 读取内存容量和文章长度int M = input.nextInt();int N = input.nextInt();// 读取单词列表int[] words = new int[N];for (int i = 0; i < N; i++) {words[i] = input.nextInt();}// 使用队列和集合来管理内存Queue<Integer> memoryQueue = new LinkedList<>();Set<Integer> memorySet = new HashSet<>();int dictionaryLookups = 0;for (int word : words) {// 如果单词已在内存中if (memorySet.contains(word)) {continue; // 不查字典}// 如果不在内存中，查字典dictionaryLookups++;if (memoryQueue.size() == M) {// 内存已满，移除最早的单词int oldestWord = memoryQueue.poll();memorySet.remove(oldestWord);}// 添加新单词到内存memoryQueue.offer(word);memorySet.add(word);}// 输出查字典的次数System.out.println(dictionaryLookups);}
}

P2058 [NOIP2016 普及组] 海港

解题思路

我们需要跟踪过去 24 小时内每个乘客的国籍。可以使用一个数组 w 来记录每个国籍的乘客数量。如果某个国籍在当前时间窗口中第一次出现，就把它加入计数；如果在窗口外移除了最后一个该国籍的乘客，就将其从计数中移除。

• 滑动窗口：

  • 每艘船到达时，我们需要把时间窗口移动到船到达的时间，计算过去 24 小时内的船只。使用一个队列或数组来保存每个乘客的信息（即乘客的国籍和到达时间）。
  • 对于每次新船到达时，我们需要：
    • 把新乘客的国籍加入窗口中。
    • 移除超出 24 小时时间范围的乘客。

• 具体步骤：

  • 维护乘客队列：我们使用两个数组：
    • x[r] 记录每个乘客的国籍；
    • y[r] 记录每个乘客的到达时间。
  • 维护国籍计数：使用数组 w，大小为 100001（假设国籍编号最大为 100000），用于记录每个国籍在当前窗口内出现的次数。如果一个国籍第一次出现，就增加总国籍数量计数；如果国籍数量降为 0，减少总国籍数量计数。

• 算法流程：

  • 对于每艘船：
    • 读取该船的到达时间 t 和船上乘客的数量 k；
    • 遍历该船的乘客，将每个乘客的国籍记录到数组 x 中，并记录到达时间到数组 y 中。
    • 更新窗口，将 24 小时以外的乘客移出窗口，并更新相应的国籍计数。
    • 统计当前 24 小时内的不同国籍数量，输出结果。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));StringBuilder output = new StringBuilder();int n = Integer.parseInt(reader.readLine()); // 读取船只数量int[] w = new int[100001]; // 记录国籍出现次数的数组int[] x = new int[300002]; // 记录每个乘客的国籍int[] y = new int[300002]; // 记录每个乘客的到达时间int s = 0; // 记录当前窗口内不同国籍的数量int r = 0; // 当前乘客的索引int i = 0; // 左边界的索引// 遍历每一艘船for (int j = 0; j < n; j++) {StringTokenizer st = new StringTokenizer(reader.readLine());int t = Integer.parseInt(st.nextToken()); // 船的到达时间int k = Integer.parseInt(st.nextToken()); // 船上乘客的数量// 遍历船上的每个乘客for (int p = 0; p < k; p++) {r++; // 更新乘客的索引y[r] = t; // 记录乘客的到达时间x[r] = Integer.parseInt(st.nextToken()); // 记录乘客的国籍// 如果这个国籍是第一次出现，增加不同国籍的数量if (w[x[r]] == 0) {s++;}// 增加该国籍的乘客计数w[x[r]]++;}// 移除24小时以外的乘客while (t - y[i] >= 86400) {// 如果移除该乘客后，该国籍没有人在窗口内，减少不同国籍数if (--w[x[i]] == 0) {s--;}i++; // 左边界右移}// 将当前窗口内不同国籍的数量加入输出output.append(s).append('\n');}// 输出结果System.out.print(output);}
}

P1241 括号序列

解题思路

• 使用栈：

  • 利用栈的数据结构来帮助我们跟踪未匹配的左括号。
  • 当遇到左括号时，将其索引压入栈中。
  • 当遇到右括号时，检查栈顶的左括号是否可以与之匹配。如果可以匹配，则将左括号从栈中弹出；如果不匹配，则记录需要插入的左括号。

• 记录匹配状态：

  • 使用一个字符数组 match 来记录每个字符的配对状态：
    • 当左括号被匹配后，将其在 match 中标记为空格。
    • 当右括号没有匹配的左括号时，在 match 中记录需要插入的左括号。

• 构建结果：

  • 遍历输入字符串和 match 数组，构建最终的输出字符串：
    • 如果 match[i] 为左括号，输出该左括号和原字符。
    • 如果 match[i] 为右括号，输出原字符和该右括号。
    • 如果 match[i] 为 ' '，则仅输出原字符。

• 边界情况：

  • 输入字符串可能为空，代码需要能处理这种情况。
  • 输入中可能有多个未匹配的括号，代码应该确保正确处理这些情况。

import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str = input.nextLine(); // 读取输入字符串System.out.println(completeBracketSequence(str));}public static String completeBracketSequence(String input) {StringBuilder result = new StringBuilder(); // 用于构建结果字符串Stack<Integer> stack = new Stack<>(); // 存储左括号的索引char[] chars = input.toCharArray(); // 转换为字符数组char[] match = new char[chars.length]; // 存储配对的字符for (int i = 0; i < chars.length; i++) {char ch = chars[i];if (ch == '(' || ch == '[') {stack.push(i); // 左括号入栈match[i] = (ch == '(') ? ')' : ']'; // 记录匹配的右括号} else if (ch == ')') {if (!stack.isEmpty() && chars[stack.peek()] == '(') {match[stack.pop()] = ' '; // 成功匹配，清空左括号的位置} else {match[i] = '('; // 不能匹配，记录需要插入的左括号}} else if (ch == ']') {if (!stack.isEmpty() && chars[stack.peek()] == '[') {match[stack.pop()] = ' '; // 成功匹配，清空左括号的位置} else {match[i] = '['; // 不能匹配，记录需要插入的左括号}}}// 构建结果字符串for (int i = 0; i < chars.length; i++) {if (match[i] == '(' || match[i] == '[') {result.append(match[i]).append(chars[i]); // 左括号和原字符} else if (match[i] == ')' || match[i] == ']') {result.append(chars[i]).append(match[i]); // 原字符和右括号} else {result.append(chars[i]); // 原字符}}return result.toString(); // 返回最终结果}
}

P4387 【深基15.习9】验证栈序列

解题思路

如果出现MLE，请多提交几次。（因为题目测试点有多组数据）

• 入栈和出栈序列：在每个测试中，给定两个序列 push 和 pop，分别表示入栈和出栈序列。我们的任务是判断是否能按照给定的顺序完成栈操作。

• 栈模拟：

  • 使用栈 stack 来模拟入栈和出栈过程。
  • 遍历出栈序列 pop：
    • 如果当前栈顶元素等于 pop[i]，则直接出栈。
    • 否则，不断将入栈序列中的元素压入栈，直到找到匹配的元素或入栈序列耗尽。

• 返回结果：

  • 如果能够按照出栈序列成功完成所有操作，则输出 "Yes"。
  • 如果无法完成操作，则输出 "No"。

import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int t = input.nextInt();  // 读取测试组数while (t-- > 0) {int n = input.nextInt();  // 读取序列长度int[] push = new int[n + 1]; // 入栈序列int[] pop = new int[n + 1];  // 出栈序列for (int i = 1; i <= n; i++) push[i] = input.nextInt();  // 读取入栈序列for (int i = 1; i <= n; i++) pop[i] = input.nextInt();   // 读取出栈序列if (isValidSequence(n, push, pop)) {System.out.println("Yes");} else {System.out.println("No");}}}public static boolean isValidSequence(int n, int[] psh, int[] pp) {Stack<Integer> stack = new Stack<>();int k = 1;  // 当前入栈序列的指针for (int i = 1; i <= n; i++) {if (!stack.isEmpty() && stack.peek() == pp[i]) {stack.pop();  // 如果栈顶元素等于出栈序列当前元素，出栈continue;}while (k <= n && psh[k] != pp[i]) {stack.push(psh[k]);  // 不断将入栈序列的元素入栈，直到找到匹配的出栈序列元素k++;}if (k > n) return false;  // 如果所有元素都无法匹配，返回falsek++;  // 匹配成功后指向下一个入栈元素}return true;}
}

P2234 [HNOI2002] 营业额统计

解题思路

• 暴力方法：对于每一天，检查之前所有天的营业额，并计算差值最小的情况，这种方法的时间复杂度为，当 n 接近 32767 时，会导致过高的运行时间，不能满足要求。

• 平衡树/有序数据结构：为了优化，利用平衡树等数据结构，能够快速地查找、插入，并维护一个动态有序的数据集合。

  • 每天处理当前的营业额时，我们将之前的营业额插入到集合中。
  • 查找与当前营业额差值最小的值，可以通过寻找前驱和后继元素（即比当前营业额小的最大值和比当前营业额大的最小值）。

import java.util.Scanner;
import java.util.TreeSet;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[] revenue = new int[n];for (int i = 0; i < n; i++) {revenue[i] = input.nextInt();}// 第一项直接是营业额值int totalFluctuation = revenue[0];// 用 TreeSet 来存储前几天的营业额，支持有序查询TreeSet<Integer> previousRevenues = new TreeSet<>();// 第一项我们已经处理，加入集合previousRevenues.add(revenue[0]);// 从第二天开始计算最小波动值for (int i = 1; i < n; i++) {int currentRevenue = revenue[i];// 寻找比当前值小的最大值和比当前值大的最小值Integer lower = previousRevenues.floor(currentRevenue); // 前驱（<= currentRevenue）Integer higher = previousRevenues.ceiling(currentRevenue); // 后继（>= currentRevenue）// 计算最小波动值int minFluctuation = Integer.MAX_VALUE;if (lower != null) {minFluctuation = Math.min(minFluctuation, Math.abs(currentRevenue - lower));}if (higher != null) {minFluctuation = Math.min(minFluctuation, Math.abs(currentRevenue - higher));}// 累加最小波动值totalFluctuation += minFluctuation;// 将当前营业额加入集合previousRevenues.add(currentRevenue);}// 输出结果System.out.println(totalFluctuation);}
}