P1551 亲戚

解题思路

这个问题可以通过 并查集（Union-Find） 来解决。并查集是一种非常适合处理这种动态连通性问题的数据结构。每个人可以看成一个节点，如果两个人是亲戚，就可以将它们所在的集合合并起来。接着，对于每个查询，我们只需要判断两个节点是否属于同一个集合即可。

并查集的基本操作

1. Find (查找根节点): 查找某个元素属于哪个集合，即找到该元素的根节点。
2. Union (合并两个集合): 将两个元素所在的集合合并为一个集合。
3. 路径压缩: 在 find 操作时，直接将路径上的节点连接到根节点，以提高后续查询效率。
4. 按秩合并: 在 union 操作时，总是将节点数较少的集合合并到节点数较多的集合，进一步提升效率。

解决思路

1. 初始化：首先为每个人初始化一个集合，每个人是自己集合的根。
2. 处理亲戚关系：对于每个输入的亲戚关系，使用并查集的 union 操作将两个有亲戚关系的人连接起来。
3. 查询亲戚关系：对于每个查询，使用并查集的 find 操作判断两个节点是否在同一个集合中，若是则输出 "Yes"，否则输出 "No"。

import java.util.Scanner;

public class Main {
    // 定义一个数组来表示每个人的根节点
    static int[] parent;

    // 初始化并查集
    public static void initialize(int n) {
        parent = new int[n + 1]; // n个人，编号1~n
        for (int i = 1; i <= n; i++) {
            parent[i] = i; // 每个人的初始根节点是自己
        }
    }

    // 查找某个元素的根节点，同时进行路径压缩
    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并两个集合
    public static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 将x的根节点指向y的根节点
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // 读入 n, m, p
        int n = input.nextInt(); // n个人
        int m = input.nextInt(); // m个亲戚关系
        int p = input.nextInt(); // p个询问

        // 初始化并查集
        initialize(n);

        // 处理 m 个亲戚关系
        for (int i = 0; i < m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            union(a, b); // 将a和b合并到同一个集合
        }

        // 处理 p 个询问
        for (int i = 0; i < p; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            // 判断x和y是否属于同一个集合
            if (find(x) == find(y)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

P1536 村村通

解题思路

1. 初始化并查集：

   • 每个城镇都作为一个独立的连通分量。
   • 初始状态下，城镇之间没有道路相连时，每个城镇的根节点是它自己。

2. 处理道路信息：

   • 每读取到一条道路，就将道路两端的城镇进行合并，表示这两个城镇之间可以互相到达。
   • 合并操作使用并查集中的 union 函数完成，将两个不同集合的根节点合并在一起。

3. 统计连通分量：

   • 遍历所有城镇，找出它们的根节点（即每个连通分量的代表）。这些根节点的数量就是连通分量的数量。
   • 每个连通分量中的城镇已经可以互相到达，但不同连通分量之间需要修建新的道路才能互通。

4. 计算最少需要建设的道路数：

   • 如果存在 k 个连通分量，则最少需要 k - 1 条道路连接它们，确保所有城镇都可以互相到达。

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    static final int max = 1001; // 定义常量 max 作为数组大小
    static int[] a = new int[max]; // 并查集数组 a
    static boolean[] barrel = new boolean[max]; // 桶

    // 并查集查找函数，路径压缩
    static int find(int x) {
        if (a[x] == x) return x;
        else return a[x] = find(a[x]);
    }

    // 合并函数
    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        a[rootX] = rootY;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n, m, x, y, ans;

        while (true) {
            n = input.nextInt(); // 先读一个数据
            if (n == 0) break; // 如果 n 为 0，停止输入

            m = input.nextInt(); // 读取道路数量
            ans = 0; // 集合数量

            // 初始化并查集
            for (int i = 1; i <= n; ++i) {
                a[i] = i;
            }

            // 读取 m 条道路信息，并进行合并
            for (int i = 1; i <= m; ++i) {
                x = input.nextInt();
                y = input.nextInt();
                union(x, y); // 合并 x 和 y 所在的集合
            }

            // 查找有多少个连通分量（桶排序标记）
            for (int i = 1; i <= n; ++i) {
                barrel[find(i)] = true; // 标记该集合的代表
            }

            // 统计连通分量数目
            for (int i = 1; i <= n; ++i) {
                if (barrel[i]) ans++;
            }

            // 输出答案
            System.out.println(ans - 1);

            // 清空桶标记
            Arrays.fill(barrel, false);
        }
    }
}

P3370 【模板】字符串哈希

解题思路

• 输入读取：输入 N?个字符串。
• 哈希值计算：对每个字符串通过哈希函数生成唯一哈希值。
• 排序：将哈希值排序。
• 去重统计：统计不同哈希值的数量。
• 输出结果。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    // 定义全局常量
    static final long BASE = 131;
    static final long MOD = 212370440130137957L; // 大质数，避免冲突
    static long[] hashValues = new long[10010]; // 存储字符串的哈希值
    static String s;
    static int n, ans = 1;

    // 计算字符串的哈希值
    static long hashString(String s) {
        long hashValue = 0;
        for (int i = 0; i < s.length(); i++) {
            hashValue = (hashValue * BASE + s.charAt(i)) % MOD;
        }
        return hashValue;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        // 读取字符串的数量
        n = input.nextInt();

        // 逐个读取字符串并计算哈希值
        for (int i = 1; i <= n; i++) {
            s = input.next();
            hashValues[i] = hashString(s);
        }

        // 对哈希值数组进行排序
        Arrays.sort(hashValues, 1, n + 1);

        // 计算不同的哈希值的数量
        for (int i = 2; i <= n; i++) {
            if (hashValues[i] != hashValues[i - 1]) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}

P3405 [USACO16DEC] Cities and States S

解题思路

• 输入数据：

  • 读取城市和州代码，将城市名称的前两个字母和州代码分别编码为整数。

• 处理组合：

  • 对每个城市，计算 (A, B) 和其反向组合 (B, A)，查找是否存在匹配。
  • 如果找到反向组合，累加计数。
  • 然后，将当前城市组合 (A, B) 存入哈希表，并更新组合出现的次数。

• 输出结果：

  • 输出特殊城市对的总数。

由于数据问题，不能AC的请多试几次。

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

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        HashMap mmp = new HashMap<>();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            String a = input.next();  // 读取城市名称
            String b = input.next();  // 读取州代码

            // 将城市名称的前两个字母转换为一个整数表示
            int A = (a.charAt(0) - 'A') * 26 + (a.charAt(1) - 'A');
            int B = (b.charAt(0) - 'A') * 26 + (b.charAt(1) - 'A');

            // 将组合(A, B)和(B, A)存入一个long型数值
            long keyAB = ((long) A << 32) | (B & 0xffffffffL);  // A在高32位, B在低32位
            long keyBA = ((long) B << 32) | (A & 0xffffffffL);  // B在高32位, A在低32位

            // 如果存在B -> A的组合，则统计它们为匹配对
            if (mmp.containsKey(keyBA)) {
                ans += mmp.get(keyBA);
            }

            // 如果A和B相等，需要在计数时减去匹配对
            if (A == B && mmp.containsKey(keyAB)) {
                ans -= mmp.get(keyAB);
            }

            // 更新mmp中的记录 (A -> B)
            mmp.put(keyAB, mmp.getOrDefault(keyAB, 0) + 1);
        }

        // 输出结果
        System.out.println(ans);
    }
}

P5250 【深基17.例5】木材仓库

解题思路

• 使用 TreeSet 来存储仓库中的木材长度，保证木材的长度是唯一的，并且是有序的。
• 对于每个操作：
  • 进货操作：如果木材已经存在，则输出 "Already Exist"。否则，将木材长度插入到 TreeSet 中。
  • 出货操作：如果 TreeSet 为空，则输出 "Empty"。否则，找到与目标长度最近的木材，优先选择比目标长度小的最大值，如果没有则选择比目标长度大的最小值。
• 使用 TreeSet 的 floor() 和 ceiling() 方法分别找到不大于和不小于指定长度的木材。

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(); // 操作的数量

        TreeSet woodSet = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            int op = input.nextInt();
            int length = input.nextInt();

            if (op == 1) { // 进货操作
                if (woodSet.contains(length)) {
                    System.out.println("Already Exist");
                } else {
                    woodSet.add(length);
                }
            } else if (op == 2) { // 出货操作
                if (woodSet.isEmpty()) {
                    System.out.println("Empty");
                } else {
                    Integer floor = woodSet.floor(length);   // 找到 <= length 的最大值
                    Integer ceiling = woodSet.ceiling(length); // 找到 >= length 的最小值

                    if (floor == null && ceiling == null) {
                        System.out.println("Empty");
                    } else if (floor == null) {
                        System.out.println(ceiling);
                        woodSet.remove(ceiling);
                    } else if (ceiling == null) {
                        System.out.println(floor);
                        woodSet.remove(floor);
                    } else {
                        if (Math.abs(floor - length) <= Math.abs(ceiling - length)) {
                            System.out.println(floor);
                            woodSet.remove(floor);
                        } else {
                            System.out.println(ceiling);
                            woodSet.remove(ceiling);
                        }
                    }
                }
            }
        }
    }
}

P5266 【深基17.例6】学籍管理

解题思路

• 插入与修改：使用 HashMap 存储学生姓名和成绩。如果学生已存在，则更新其成绩；如果不存在，则插入新记录。
• 查询：通过姓名查找 HashMap，如果找到则输出成绩，否则输出“Not found”。
• 删除：通过姓名查找 HashMap，如果找到则删除并输出“Deleted successfully”，否则输出“Not found”。
• 汇总：直接输出 HashMap 中的元素数量。

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

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        HashMap studentMap = new HashMap<>();

        int n = input.nextInt();  // 读取操作数
        for (int i = 0; i < n; i++) {
            int operation = input.nextInt();
            String name;
            switch (operation) {
                case 1:  // 插入与修改操作
                    name = input.next();
                    int score = input.nextInt();
                    studentMap.put(name, score);
                    System.out.println("OK");
                    break;
                case 2:  // 查询操作
                    name = input.next();
                    if (studentMap.containsKey(name)) {
                        System.out.println(studentMap.get(name));
                    } else {
                        System.out.println("Not found");
                    }
                    break;
                case 3:  // 删除操作
                    name = input.next();
                    if (studentMap.containsKey(name)) {
                        studentMap.remove(name);
                        System.out.println("Deleted successfully");
                    } else {
                        System.out.println("Not found");
                    }
                    break;
                case 4:  // 汇总操作
                    System.out.println(studentMap.size());
                    break;
                default:
                    break;
            }
        }
    }
}

P1102 A-B 数对

解题思路

双指针

• 输入处理：

  • 输入的第一个数 n 表示数组的大小，第二个数 c 表示我们要找的差值。
  • 接下来输入一个长度为 n 的数组 a，代码会将其存储在大小为 200010 的数组中。

• 排序数组：

  • 代码首先使用 Arrays.sort(a, 1, n + 1) 对输入的数组从索引 1 到 n 进行排序，这样可以简化查找差值为 c 的数对的过程。

• 双指针法：

  • 使用双指针（r1 和 r2）从左向右扫描数组，来确定符合条件的数对。
  • 对于每个位置 l，指针 r1 寻找数组中第一个满足 a[r1] - a[l] > c 的位置，指针 r2 寻找第一个满足 a[r2] - a[l] >= c 的位置。
  • 然后，若 a[r2] - a[l] == c 且 a[r1 - 1] - a[l] == c，说明从 r2 到 r1 - 1 之间的数都满足条件，可以将其加入结果。

• 结果统计：

  • 对于每个 l，都根据指针 r2 和 r1 计算并统计满足条件的数对。

import java.util.Arrays;
import java.util.Scanner;

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

        // 读取输入的 n 和 c
        int n = input.nextInt();  // 数组的长度
        int c = input.nextInt();  // 目标差值 c
        
        // 初始化长度足够大的数组，避免索引越界
        int[] a = new int[200010]; // 假设最大输入 n 为 200,000，这里稍微开大点数组以防溢出

        // 读取输入的数组数据，从索引 1 开始存储
        for (int i = 1; i <= n; i++) {
            a[i] = input.nextInt();
        }

        // 对数组的前 n 个元素进行排序
        Arrays.sort(a, 1, n + 1);

        // 初始化双指针和结果变量
        int l = 1, r1 = 1, r2 = 1; 
        long ans = 0;  // 用于记录满足条件的数对数量

        // 固定左边界 l，从 1 到 n 进行遍历
        for (l = 1; l <= n; l++) {
            // 移动 r1，找到 a[r1-1] - a[l] <= c 的最大 r1
            while (r1 <= n && a[r1] - a[l] <= c) r1++;
            
            // 移动 r2，找到 a[r2] - a[l] >= c 的最小 r2
            while (r2 <= n && a[r2] - a[l] < c) r2++;
            
            // 检查是否存在 a[r2] - a[l] == c 且 r1-1 的差值也为 c
            if (r2 <= n && a[r2] - a[l] == c && a[r1 - 1] - a[l] == c && r1 - 1 >= 1) {
                ans += r1 - r2; // 计算当前满足条件的数对个数
            }
        }

        // 输出满足条件的数对数量
        System.out.println(ans);
    }
}

哈希映射

• 使用一个哈希映射 HashMap 来存储每个数的出现次数或者出现位置。
• 对于每个数 a[i]，检查是否存在 a[i] + c 或 a[i] - c 的值在哈希映射中出现。
• 如果找到满足条件的数对，则计数增加。

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

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

        int n = input.nextInt();  // 数组长度
        int c = input.nextInt();  // 目标差值

        HashMap map = new HashMap<>();  // 用于存储数字及其出现次数
        int[] a = new int[n];  // 存储输入的数组
        
        // 读取数组输入
        for (int i = 0; i < n; i++) {
            a[i] = input.nextInt();
            // 将数字存储在哈希映射中
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
        }

        long ans = 0;  // 用于记录符合条件的对数

        // 遍历数组，寻找每个 a[i] 对应的 a[i] + c 或 a[i] - c 是否存在
        for (int i = 0; i < n; i++) {
            // 检查是否存在 a[i] + c
            if (map.containsKey(a[i] + c)) {
                ans += map.get(a[i] + c);  // 统计满足条件的对数
            }
        }

        // 输出符合条件的对数
        System.out.println(ans);
    }
}

P1918 保龄球

解题思路

• 构建数据结构：

  • 将每个瓶子的数量和它的原始位置打包成一个 Item 类。
  • 对 Item 类的数组按瓶子数进行升序排序。

• 处理查询：

  • 使用标准的二分查找算法，在排序后的数组中查找目标瓶子数。
  • 如果找到，返回其原始位置；找不到则输出 0。

（数据较大，使用I/O流输入输出）

import java.io.*;
import java.util.Arrays;

class Item {
    int g;  // 瓶子的个数
    int w;  // 位置

    Item(int g, int w) {
        this.g = g;
        this.w = w;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 和 BufferedWriter 进行高效 I/O
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        // 读取位置数 n
        int n = Integer.parseInt(reader.readLine());
        Item[] gs = new Item[n];

        // 读取每个位置的瓶子数并存储
        String[] bottleCounts = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            gs[i] = new Item(Integer.parseInt(bottleCounts[i]), i + 1);
        }

        // 根据瓶子数排序
        Arrays.sort(gs, (x, y) -> Integer.compare(x.g, y.g));

        // 读取查询次数 m
        int m = Integer.parseInt(reader.readLine());

        // 处理每次查询
        for (int i = 0; i < m; i++) {
            int wt = Integer.parseInt(reader.readLine());  // 读取每个查询的目标瓶子数
            int position = binarySearch(gs, wt);
            writer.write(position + "\n");  // 写入结果
        }

        // 刷新并关闭输出流
        writer.flush();
        writer.close();
        reader.close();
    }

    // 二分查找函数：查找瓶子数为 wt 的位置
    private static int binarySearch(Item[] gs, int wt) {
        int left = 0, right = gs.length - 1;

        // 标准二分查找模板
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (gs[mid].g == wt) {
                return gs[mid].w;  // 找到，返回位置
            } else if (gs[mid].g < wt) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 没找到返回 0
        return 0;
    }
}

P1525 [NOIP2010 提高组] 关押罪犯

解题思路

• 初始化并查集：对于每个罪犯 i，将其初始化为自己是独立的组，同时将每个罪犯的敌对身份 i+n也初始化为独立组。

• 仇恨关系的排序：所有的仇恨关系根据怨气值从大到小排序，这样我们可以从最容易导致冲突的怨气值开始处理。

• 并查集查找与合并：

  • 每次处理一对罪犯 a?和 b?时，检查它们是否已经被分配到了同一个监狱（通过判断它们是否在同一个集合中）。
  • 如果已经在同一个监狱中，说明无法避免冲突，直接输出怨气值。
  • 如果还没有冲突，就将 a?放在 b?的敌对监狱中，并更新并查集。

• 输出结果：如果遍历所有的仇恨关系后没有发现冲突，输出 0，表示罪犯分配合理，不会发生冲突。

import java.util.Arrays;
import java.util.Scanner;

// 定义 Crime 类，表示罪犯间的仇恨关系，实现 Comparable 接口以便排序
class Crime implements Comparable {
    int a, b, val;  // a 和 b 表示罪犯编号，val 表示怨气值

    public Crime(int a, int b, int val) {
        this.a = a;
        this.b = b;
        this.val = val;
    }

    // 按照怨气值降序排序
    @Override
    public int compareTo(Crime other) {
        // 如果当前对象的 val 比较大，则返回负数，表示当前对象排在前面
        return Integer.compare(other.val, this.val);
    }
}

public class Main {
    static final int MAXN = 100000 + 5;  // 最大罪犯数，稍微增加缓冲
    static int[] bin = new int[MAXN << 1];  // 并查集数组，存储每个罪犯的身份，<<1 相当于乘 2，表示每个罪犯的两种身份
    static Crime[] x = new Crime[MAXN];  // 存储每对罪犯的仇恨信息

    // 并查集的查找操作，路径压缩
    static int find(int x) {
        // 如果 x 是自己所在的集合代表，则返回 x，否则递归查找，路径压缩
        if (bin[x] == x) return x;
        return bin[x] = find(bin[x]);
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();  // 罪犯的数量 N
        int m = input.nextInt();  // 仇恨对的数量 M

        // 初始化并查集，每个罪犯有两种身份
        for (int i = 1; i <= n; ++i) {
            bin[i] = i;  // 罪犯 i 的身份 1 (属于监狱 A)
            bin[i + n] = i + n; // 罪犯 i 的身份 2 (属于监狱 B)
        }

        // 读取所有的仇恨关系，存储在 Crime 数组中
        for (int i = 1; i <= m; ++i) {
            int a = input.nextInt();  // 罪犯 a
            int b = input.nextInt();  // 罪犯 b
            int val = input.nextInt();  // 怨气值
            x[i] = new Crime(a, b, val);  // 将仇恨关系存入数组
        }

        // 按怨气值降序排序
        Arrays.sort(x, 1, m + 1);

        // 遍历所有的仇恨关系，从最大怨气值开始
        for (int i = 1; i <= m; ++i) {
            // 查找罪犯 a 和 b 的所属集合
            int fa = find(x[i].a);           // a 的身份（是否在监狱 A）
            int fb = find(x[i].b);           // b 的身份（是否在监狱 A）
            int ffa = find(x[i].a + n);      // a 的敌对身份（是否在监狱 B）
            int ffb = find(x[i].b + n);      // b 的敌对身份（是否在监狱 B）

            // 如果 a 和 b 在同一个监狱
            if (fa == fb) {
                // 输出当前的怨气值，因为这是市长看到的最大冲突事件
                System.out.println(x[i].val);
                return;  // 结束程序
            }

            // 将 a 放入 b 的敌对监狱，b 放入 a 的敌对监狱
            bin[fa] = ffb; // a 放入 b 的敌对集合
            bin[fb] = ffa; // b 放入 a 的敌对集合
        }

        // 如果遍历完所有的仇恨关系后没有冲突，输出 0
        System.out.println("0");
    }
}

P1621 集合

解题思路

• 初始化并查集：每个整数开始时都属于自己的集合。
• 找到所有质因数：遍历范围内的每个整数，找出它的质因数。
• 合并集合：对于每个质因数，如果它大于或等于 p，则找到拥有该质因数的所有整数，合并这些整数所在的集合。
• 统计结果：最终统计剩下的不同集合的数量。

import java.util.*;

public class Main {
    // 并查集类
    static class UnionFind {
        int[] parent; // 父节点数组
        int[] rank;   // 秩数组，用于优化合并

        UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            // 初始化，每个元素的父节点是自己，秩为1
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        // 查找元素的根节点，并进行路径压缩
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }

        // 合并两个集合
        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                // 按秩合并
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int a = input.nextInt(); // 输入范围的下界
        int b = input.nextInt(); // 输入范围的上界
        int p = input.nextInt(); // 输入质因数的阈值

        int size = b - a + 1; // 范围内的整数个数
        UnionFind uf = new UnionFind(size); // 初始化并查集

        // 存储质因数与其对应的整数
        Map> factorMap = new HashMap<>();

        // 第一步：收集范围内每个整数的质因数
        for (int num = a; num <= b; num++) {
            Set factors = getFactors(num); // 获取质因数
            for (int factor : factors) {
                if (factor >= p) { // 只考虑大于等于p的质因数
                    factorMap.putIfAbsent(factor, new ArrayList<>());
                    factorMap.get(factor).add(num); // 将整数添加到质因数对应的列表中
                }
            }
        }

        // 第二步：根据质因数合并集合
        for (List group : factorMap.values()) {
            for (int i = 1; i < group.size(); i++) {
                uf.union(group.get(0) - a, group.get(i) - a); // 合并集合
            }
        }

        // 第三步：统计不同的根节点数量
        Set uniqueRoots = new HashSet<>();
        for (int num = a; num <= b; num++) {
            uniqueRoots.add(uf.find(num - a)); // 查找并添加根节点
        }

        // 输出不同集合的数量
        System.out.println(uniqueRoots.size());
    }

    // 获取一个数的所有质因数
    private static Set getFactors(int n) {
        Set factors = new HashSet<>();
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) { // 如果i是n的因数
                factors.add(i); // 添加质因数
                while (n % i == 0) { // 去掉所有i的因子
                    n /= i;
                }
            }
        }
        if (n > 1) { // 如果n剩下的部分是质数
            factors.add(n);
        }
        return factors; // 返回质因数集合
    }
}

P1892 [BOI2003] 团伙

解题思路

• 数据结构：使用一个并查集（Union-Find）来管理每个人及其关系。为了处理敌人关系，我们为每个人维护两个集合，一个是他们自己，另一个是敌人的集合。因此，我们使用 2 * n 的大小来存储这两类关系。

• 初始化：在 main 方法中，首先初始化每个人的父亲指针 f，每个人的父亲指向自己。

• 处理关系：

  • 对于朋友关系 (F)，通过查找根节点并合并两个集合。
  • 对于敌人关系 (E)，将一个人的敌人与另一个人的集合合并，这里用到的技巧是将敌人的敌人看作朋友。具体而言，将 a 的敌人与 b 进行合并（a + n），并将 b 的敌人与 a 进行合并（b + n）。

• 统计团体数：最后，遍历每个人，如果一个人的父亲指向自己，说明这个人是一个团体的根节点，增加团体计数。

import java.util.Scanner;

public class Main {
    static int n, m, s = 0; // n: 人数, m: 关系数, s: 团体数
    static int[] f = new int[5000]; // 存放每个人的父亲（包括敌人）

    // 查找x的祖先，并进行路径压缩
    static int find(int x) {
        if (f[x] != x) {
            f[x] = find(f[x]); // 查找 + 路径压缩
        }
        return f[x];
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt(); // 输入人数
        m = input.nextInt(); // 输入关系数

        // 初始化每个人的父亲指针
        for (int i = 1; i <= 2 * n; i++) {
            f[i] = i; // 每个人的父亲初始为自己
        }

        // 处理关系
        for (int i = 1; i <= m; i++) {
            char ch = input.next().charAt(0); // 关系类型
            int a = input.nextInt(); // 第一个人
            int b = input.nextInt(); // 第二个人

            if (ch == 'F') {
                // 如果是朋友关系，合并
                f[find(a)] = find(b);
            } else {
                // 如果是敌人关系，合并反集合
                f[find(a + n)] = find(b); // a的敌人与b合并
                f[find(b + n)] = find(a); // b的敌人与a合并
            }
        }

        // 统计团体数
        for (int i = 1; i <= n; i++) {
            if (f[i] == i) {
                s++; // 每个根节点代表一个团体
            }
        }

        System.out.println(s); // 输出团体数
    }
}

P1955 [NOI2015] 程序自动分析

解题思路

• 问题理解：

  • 给定多个变量之间的相等和不等约束，判定是否可以为这些变量赋值，使所有约束同时成立。

• 并查集的应用：

  • 使用并查集数据结构来管理变量之间的相等关系。
  • 对于相等约束 xi=xjx_i = x_jxi?=xj?，使用 union 操作将它们合并到同一集合中。
  • 对于不等约束 xi≠xjx_i \neq x_jxi?=xj?，需要在所有相等约束处理完成后，检查这对变量是否在同一个集合中。如果在同一集合，则说明约束冲突，返回 "NO"。

import java.util.*;

public class Main {
    // 定义并查集类
    static class UnionFind {
        // 存储每个节点的父节点
        private final Map parent = new HashMap<>();

        // 查找节点x的根节点，带路径压缩
        public int find(int x) {
            // 如果节点x没有在parent中，初始化它的父节点为自己
            if (!parent.containsKey(x)) {
                parent.put(x, x);
            }
            // 如果x的父节点不是自己，递归查找并压缩路径
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x))); // 路径压缩
            }
            return parent.get(x);
        }

        // 合并两个节点x和y
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            // 如果x和y的根节点不同，则合并
            if (rootX != rootY) {
                parent.put(rootY, rootX); // 合并
            }
        }

        // 判断节点x和y是否在同一个集合中
        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }

    // 解决单个约束集的方法
    public static String solveCase(List constraints) {
        UnionFind uf = new UnionFind(); // 创建并查集实例
        List notEqualPairs = new ArrayList<>(); // 存储不等约束对

        // 遍历所有约束
        for (int[] constraint : constraints) {
            int x = constraint[0];
            int y = constraint[1];
            int e = constraint[2];
            if (e == 1) {
                uf.union(x, y); // 相等约束，合并集合
            } else {
                notEqualPairs.add(new int[]{x, y}); // 不等约束，记录
            }
        }

        // 检查不等约束
        for (int[] pair : notEqualPairs) {
            if (uf.connected(pair[0], pair[1])) {
                return "NO"; // 如果x和y在同一集合中，返回NO
            }
        }

        return "YES"; // 所有约束可以满足
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt(); // 读取测试用例的数量
        StringBuilder result = new StringBuilder(); // 用于存储结果

        // 遍历每个测试用例
        for (int i = 0; i < t; i++) {
            int n = input.nextInt(); // 读取约束条件的数量
            List constraints = new ArrayList<>(); // 存储约束条件
            for (int j = 0; j < n; j++) {
                int x = input.nextInt();
                int y = input.nextInt();
                int e = input.nextInt();
                constraints.add(new int[]{x, y, e}); // 记录约束条件
            }
            String res = solveCase(constraints); // 解决当前约束集
            result.append(res).append("\n"); // 添加结果到输出
        }

        System.out.print(result); // 输出所有结果
    }
}

P4305 [JLOI2011] 不重复数字

解题思路

• 读取输入：首先读取数据组数 T。
• 对于每组数据：
  • 读取数字的个数 n 和实际的数字序列。
  • 初始化一个 HashSet 用于存储已出现的数字。
  • 初始化一个 StringBuilder 用于存储去重后的数字。
  • 遍历输入的数字：
    • 对于每个数字，检查它是否已经在 HashSet 中。
    • 如果没有出现过，则将其添加到 HashSet 和 StringBuilder 中，并在 StringBuilder 中适当地添加空格作为分隔。
• 输出结果：在处理完所有组数据后，使用 PrintWriter 输出结果。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;

public class UniqueNumbers {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(System.out);
        
        int T = Integer.parseInt(reader.readLine().trim()); // 读取数据组数
        
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(reader.readLine().trim()); // 读取每组数据的数量
            String[] numbers = reader.readLine().split(" "); // 读取数字
            
            HashSet seen = new HashSet<>(); // 用于追踪已出现的数字
            StringBuilder result = new StringBuilder(); // 用于存储去重后的结果
            
            for (String num : numbers) {
                int number = Integer.parseInt(num); // 转换为整数
                if (seen.add(number)) { // 如果数字是第一次出现
                    if (result.length() > 0) {
                        result.append(" "); // 添加空格分隔
                    }
                    result.append(number); // 添加到结果
                }
            }
            
            writer.println(result); // 输出去重后的结果
        }
        
        writer.flush(); // 刷新输出流
        writer.close(); // 关闭输出流
        reader.close(); // 关闭输入流
    }
}

?

P3879 [TJOI2010] 阅读理解

解题思路

• 输入短文: 读取每篇短文及其包含的单词，并将每个单词及其对应的短文索引存入一个哈希表。
• 处理查询: 对于每个生词查询，直接从哈希表中获取对应的短文索引，并按要求格式输出。
• 输出格式: 确保输出的短文索引不重复且按升序排列，对于没有出现的生词输出空行。

import java.io.*;
import java.util.*;

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().trim()); // 读取短文数量
        Map> wordToArticles = new HashMap<>(); // 哈希表存储单词和其出现的短文索引

        // 读取每篇短文
        for (int i = 1; i <= N; i++) {
            String line = reader.readLine().trim(); // 读取一行短文
            String[] words = line.split(" "); // 按空格分割成单词
            int L = Integer.parseInt(words[0]); // 读取单词数

            // 遍历短文中的单词并记录索引
            for (int j = 1; j <= L; j++) {
                String word = words[j];
                wordToArticles.computeIfAbsent(word, k -> new HashSet<>()).add(i); // 将短文索引加入集合
            }
        }

        int M = Integer.parseInt(reader.readLine().trim()); // 读取查询的生词数量

        // 处理每个生词的查询
        for (int i = 0; i < M; i++) {
            String queryWord = reader.readLine().trim(); // 读取生词
            Set articles = wordToArticles.get(queryWord); // 获取该生词对应的短文索引

            if (articles != null && !articles.isEmpty()) {
                List sortedArticles = new ArrayList<>(articles); // 转换为列表
                Collections.sort(sortedArticles); // 排序
                // 构建输出字符串
                for (int index : sortedArticles) {
                    output.append(index).append(" "); // 添加短文索引
                }
                output.setLength(output.length() - 1); // 去掉最后一个空格
            }
            output.append("\n"); // 换行
        }

        System.out.print(output); // 一次性输出结果
    }
}

P2814 家谱

解题思路

• 构建家谱: 使用一个字典来记录每个人的父亲。
• 查找祖先: 对于每个查询，利用一个循环不断查找其父亲，直到找到没有父亲的人（即最早的祖先）。
• 输出结果: 按照要求的格式输出每个查询结果。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Map familyTree = new HashMap<>(); // 存储每个人的父亲
        String currentFather = null; // 当前的父亲

        String line;
        // 读取输入直到遇到 $
        while (!(line = reader.readLine()).equals("$")) {
            // 判断是父亲还是儿子
            if (line.startsWith("#")) {
                currentFather = line.substring(1); // 获取父亲名字
            } else if (line.startsWith("+")) {
                String son = line.substring(1); // 获取儿子名字
                familyTree.put(son, currentFather); // 将儿子与父亲关系存入字典
            } else if (line.startsWith("?")) {
                String query = line.substring(1); // 获取查询名字
                // 查找最早的祖先
                String ancestor = findAncestor(familyTree, query);
                // 输出结果
                System.out.println(query + " " + ancestor);
            }
        }
    }

    // 查找某个名字的最早祖先
    private static String findAncestor(Map familyTree, String name) {
        String ancestor = name; // 初始设为本人
        // 如果名字存在且有父亲，则继续查找
        while (familyTree.containsKey(ancestor)) {
            ancestor = familyTree.get(ancestor); // 更新为其父亲
        }
        return ancestor; // 返回没有父亲的名字，即最早的祖先
    }
}