刷题总结（分类）

难崩侠 #技术

刷题总结（分类）

动态规划DP

P1164 小A点菜

  1. 理解题意
    1. 题目大意是说，给你n个菜的价格，要你组成m这个总金额，总共有多少种方法
  2. 每个菜可以选，可以不选
    1. 这样很符合dfs，但是题目要求1s内，所以不考虑，记忆化递归也没有很好写
    2. 所以我们考虑dp，每个菜可以选可以不选，这个和0/1背包问题很像，所以套01背包的模板
  3. dp
    1. 设dp[i][j]为前i个数组成m这个金额的方法数
    2. 由于第i个数可以选，可以不选，那么 前i个数组成m的方法为 选的情况的方法数+不选的情况的方法数 即，dp[i][j]=选的情况的方法数+不选的情况的方法数
    3. 如果选了第i个数，由于 $ a_i $会占用金额，那我们减去$ a_i $即可，又因为第i个选了，我们只需要求前i-1个的方法即可 即 选的情况的方法数=dp[i-1][j-$ a_i $] 注意这里要i-1,写代码的时候就是错在这里
    4. 如果不选第i个数，没有 $ a_i $占用金额，我们还是求前i-1达到金额 j 的方法数就行了 即 不选的情况的方法数=dp[i-1][j]
    5. 所以可以得到 状态转移方程 dp[i][j]=dp[i-1][j-$ a_i $ + dp[i-1][j-$ a_i $]
    6. 初始化条件为 dp[0][0]=1; ,注意这里，写代码的时候初始化条件是其他导致出错
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static Long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    public static void main(String[] args) throws IOException {
        int n=nextInt(),m=nextInt();
        int[] price=new int[n];
        int cnt=0;
        for (int i = 0; i < n; i++) {
            price[i]=nextInt();
        }
        int[][]dp=new int[n+1][m+1];


        dp[0][0]=1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) { //TODO 为啥j从0开始和从1开始不一样，
                dp[i][j]=dp[i-1][j];        //同一个状态转移方程，需要判断的条件不一行
                if (price[i-1]<=j)dp[i][j]+=dp[i-1][j-price[i-1]];
            }
        }
        out.println(dp[n][m]);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}

import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static Long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    public static void main(String[] args) throws IOException {
        int n=nextInt(),m=nextInt();
        int[] price=new int[n];
        int cnt=0;
        for (int i = 0; i < n; i++) {
            price[i]=nextInt();
        }
        for (long i = 1; i <= (1L << n); i++) {
            int sum=0;
            for (int j = 0; j < n; j++) {
                if ((i&(1L<<j))>0)sum+=price[j];
            }
            if (sum==m)cnt++;
        }
        out.println(cnt);
        
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}

import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static Long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    public static void main(String[] args) throws IOException {
        int n=nextInt(),m=nextInt();
        int[] price=new int[n];
        int cnt=0;
        for (int i = 0; i < n; i++) {
            price[i]=nextInt();
        }
        int[][]dp=new int[2][m+1];


        dp[0][0]=1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) { //TODO 为啥j从0开始和从1开始不一样，
                dp[i&1][j]=dp[(i-1&1)][j];        //同一个状态转移方程，需要判断的条件不一行
                if (price[i-1]<=j)dp[i&1][j]+=dp[(i-1)&1][j-price[i-1]];
            }
        }
        out.println(dp[n&1][m]);

        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}

状态压缩DP

P1433 吃奶酪

  1. 理解题意
    1. 给定n个坐标，要求走完这这n个坐标的最短距离，
    2. 经典的旅行商问题
  2. 做题
    1. 方法一（dfs+剪枝）
      1. 我们可以使用dfs遍历所有的可能，然后求出所有的可能的最短路径就行，
      2. 然而这样百分百TLE，我们还可以剪枝，但是也还是会TLE
    2. 方法二（状态压缩DP）
      1. 我们可以用二进制数来表示当前的状态（状态压缩），即Musk
      2. 定义dp[i][Musk],表示当前停在第i个坐标，musk表示选了哪个元素（如果那个二进制位有1的话），即当前停在第i个坐标，当前选了musk元素的最短路径
      3. 那么递推公式怎么写呢
      4. dp[i][musk]=dp[j][preMusk]+distance[j][i]
      5. j表示从musk状态选了一个坐标，preMusk表示没有i坐标的状态，distance[j][i]表示从i跳到j的距离
      6. 那么这个公式就很明确了
      7. 从musk状态选一个元素i作为终点元素，再选一个j作为前一个的终点，看看哪个（j跳到i的距离+j状态的preMusk的最短距离)最小，那么dp[i][musk]就等于j到i的距离+dp[j][preMusk]的最短距离
  3. 代码
public static void main(String[] args) throws IOException {
        int n=nextInt();
        double[] dx=new double[n+1];
        double[] dy = new double[n+1];
        dx[0]=dy[0]=0;
        double[][] distance=new double[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            dx[i]=nextDouble();
            dy[i]=nextDouble();
        }
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                distance[i][j]=distance[j][i]=Math.hypot(dx[i]-dx[j],dy[i]-dy[j]);
            }
        }
        double[][] dp = new double[n + 1][1 << n];
        for (double[] doubles : dp) {
            Arrays.fill(doubles,Double.MAX_VALUE);
        }
        for (int i = 1; i <= n; i++) {
            dp[i][1<<(i-1)]=distance[0][i];
        }
        for (int musk = 1; musk < (1 << (n)); musk++) {
            for (int i = 1; i <= n; i++) {
                if ((musk&(1<<(i-1)))==0)continue;
                for (int j = 1; j <= n; j++) {
                    int premusk=musk^(1<<(i-1));
                    if (i==j||((premusk&1<<(j-1))==0))continue;
                    dp[i][musk]=Math.min(dp[j][premusk]+distance[j][i],dp[i][musk]);
                }
            }
        }
        double ans=Double.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            ans=Math.min(ans,dp[i][(1<<n)-1]);
        }
        out.printf("%.2f",ans);

        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

递归/递推

P3612 [USACO17JAN] Secret Cow Code S

  1. 理解题意
    1. 这道题让我们复制字符串，先将原字符串的最后一位移到第一位，然后将这个字符拼接到原字符串的后面
    2. 例子
      1. COW -> COW WCO -> COWWCO OCOWWC
  2. 递推/递归 映射
    1. 我们可以将拼接后的字符串看成前后两部分，
    2. 先假设要找的字符串在后面的那串字符串里面，（万一在前面，后面步骤解决）
    3. 又因为后面的那串字符串是由前面复制而来的，所以我们可以找到某种关系，来找到后面的字符串的那个位置的字符对应在前面那个字符串的位置
    4. 我们发现，
      1. 如果那个位置的字符是后面串的第一位，那么就对应前面串的最后一位
      2. 如果是其他位置，那么 该字符在后面字符串的位置 ==前面字符串的该位置减去1
      3. 如 在后面字符串位置为2，那么对应的位置为前面字符串的1（2-1）
      4. 那么如果知道 该字符在后面字符串的位置呢，就用 该字符在完整字符串的位置n - 整个字符串的长度L/2
      5. 那么该字符在前字符串的位置即如 步骤iii所说 ，减去1即可 即为 n(在前串的新位置)=n - （L/2） - 1
      6. 此时前串成为一个大的字符串
    5. 又因为前串是不会变的，我们可以一直缩小，一直到可以刚刚使得n刚刚成为后串的位置，然后重复 步骤d.iv和步骤d.v ,直到位置n小于原始字符串的长度，这样n就是在原始字符串的位置，直接输出即可
    6. 注意点，
      1. 位置index将极大，使用long接受
      2. 不仅仅index要long ，用于计算刚刚比index大的字符串长度的变量 i也要使用long，不然会超过限制，即第8行
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        String str=sc.next();
        long index=sc.nextLong();
        int length=str.length();
        while (length<index){
            long i=length;
            while (i<index)i*=2;
            i/=2;
            index-=(i+1);
            if (index==0)index=i;
        }
        System.out.println(str.charAt((int) (index-1)));

        sc.close();
    }
}

贪心算法

P1090 [NOIP 2004 提高组] 合并果子

  1. 理解题意
    1. 题目要求我们将所有的果子合并成一堆，新合并的一堆消耗的体力等于新的那一堆果子的重量（即合并前的两堆果子之和），问合并消耗的体力最小
    2. 这里要注意的点是，新合并的堆也要和所有的堆比较，
    3. 那么从测试用例很容易看出，这里的贪心选择就是每次选择最小的两堆进行合并
  2. 做题
    1. 那么我们每次将最小的两堆进行合并，然后将新堆放进队列里面，然后再重新选择两个最小的即可
    2. 这道题的关键点在，要维护动态极值
  3. 两种方法
    1. 优先队列
      1. 维护动态极值，我们很容易想到优先队列
      2. 创建一个优先队列，
      3. 合并两个最小的堆，得到一个新堆
      4. 将这个新堆的重量加入体力值
      5. 将新建的这个堆重新加入优先队列
      6. 然后重复三四五步骤
    2. 桶排序+双队列
      1. 由于输入的每一个堆 $ a_i $有$ 1≤a_i≤20000 $,这样的数据比较集中，
      2. 我们就可以考虑桶排序，桶排序的时间复杂度可以达到$ O(n) $
      3. 创建一个20001的数组t，即创建20000个桶
      4. 然后 将数组放进对应的桶内，即 t[nextInt()]++,不用真的放，加1即可
      5. 然后从小到大把桶中的数取出来
      6. 这样就排好序了
      7. 然后我们用两个数组存放堆
      8. 一个存原来的堆
      9. 一个存合并后的堆
      10. 我们现在比较这两个堆最前面的数，取出最小的两个数，合并成一个新的堆
      11. 然后加到合并的堆的数组的后面（这里有个疑问，为什么加到合并数组后是从小到大的呢，后面解释）
      12. 将这个新的堆加到体力消耗里面
      13. 重复8到12步即可
      14. 为什么加到合并数组后是从小到大的呢
        1. 设当前最小的两个数为 A，B
        2. 那么下一个循环的最小的两个数C,D必然有
        3. $ A,B<=C,D $
        4. 那么有$ A+B<=C+D $
        5. 那么就可以看出下一个循环得到的堆必然大于前一个循环得到的堆
  4. 注意点
    1. 注意桶排序的代码的19行
    2. 他的终止条件是合并n-1次即可
    3. 而我之前想的是a1数组的剩余元素为空即停止循环
    4. 这种是错的
public static void main(String[] args) throws IOException {
        int n=nextInt();
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            minHeap.add(nextLong());
        }
        long tili=0;
        while (minHeap.size()>1){
            long temp=minHeap.poll()+minHeap.poll();
            tili+=temp;
            minHeap.add(temp);
        }

        out.println(tili);

        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

public static void main(String[] args) throws IOException {
        int n=nextInt(),time=1;
        long[] temp=new long[20002],a1=new long[10001],a2=new long[10001];
        int n1 = 0,n2=0,s1=0,s2=0;
        long tili=0;
        for (int i = 0; i < a1.length; i++) {   //设置哨兵值
            a1[i]=Long.MAX_VALUE;
            a2[i]=Long.MAX_VALUE;
        }
        for (int i = 0; i < n; i++) {   //桶排序，20000个桶
            temp[nextInt()]++;
        }
        for (int i = 1; i < temp.length; i++) {  //从桶中拿出来
            while (temp[i]>0){
                a1[n1++]=i;
                temp[i]--;
            }
        }
        while (time<n){
            long num=0;
            if (a1[s1]<=a2[s2]){
                num=a1[s1++];
            }else num=a2[s2++];

            if (a1[s1]<=a2[s2]){
                num+=a1[s1++];
            }else num+=a2[s2++];
            time++;
            tili+=a2[n2++]=num;
        }
        out.println(tili);

        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
  1. 注意下面的代码
  2. 注意第43行和45行
  3. 要注意此时的条件是
  4. 若表达式为true，则选择a1，若为false，则选择a2
  5. s2 >= n2 的意思是若a2没有元素了，那么就选择a1即可，注意第3点
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static Long nextLong() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int[] temp = new int[20001];
        for (int i = 0; i < n; i++) {
            temp[nextInt()]++;
        }

        // 初始化数组，容量设为 n+1 防止溢出
        long[] a1 = new long[n + 1];
        long[] a2 = new long[n + 1];
        int n1 = 0, n2 = 0; // 有效元素数量
        int s1 = 0, s2 = 0; // 当前指针位置

        // 填充 a1（桶排序）
        for (int i = 1; i <= 20000; i++) {
            while (temp[i]-- > 0) {
                a1[n1++] = i;
            }
        }

        long tili = 0;
        int time = 0;

        while (time < n - 1) { // 需合并 n-1 次
            // 取第一个最小值
            long first = (s1 < n1 && (s2 >= n2 || a1[s1] <= a2[s2])) ? a1[s1++] : a2[s2++];
            // 取第二个最小值
            long second = (s1 < n1 && (s2 >= n2 || a1[s1] <= a2[s2])) ? a1[s1++] : a2[s2++];
            
            long merged = first + second;
            tili += merged;
            a2[n2++] = merged; // 合并结果存入 a2
            time++;
        }

        out.println(tili);
        out.flush();
        out.close();
    }
}

import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static Long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    public static void main(String[] args) throws IOException {
        int n=nextInt();
        MinHeap minHeap = new MinHeap();
        for (int i = 0; i < n; i++) {
            minHeap.add(nextLong());
        }
        long tili=0;
        while (minHeap.size>1){
            long temp=minHeap.poll()+minHeap.poll();
            tili+=temp;
            minHeap.add(temp);
        }

        out.println(tili);

        out.flush(); // 刷新输出流
        out.close();//关闭流

        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}
class MinHeap{
int size=0;
long[] heap=new long[20001];

    public long peek(){
        return heap[0];
    }
    public void swap(int index1,int index2){
        long temp=heap[index1];
        heap[index1]=heap[index2];
        heap[index2]=temp;
    }
    private void siftUp(int index){
        while (index > 0&&index<size) {
                int parent=(index-1)/2;
                if (heap[parent]<=heap[index])break;
                swap(parent,index);
                index=parent;
        }
    }
    private void siftDown(int index){
        while (index<size){
            int lch=2*index+1;
            int rch=2*index+2;
            int smallest=index;
            if (lch<size&&heap[lch]<heap[smallest])smallest=lch;
            if (rch<size&&heap[rch]<heap[smallest])smallest=rch;
            if (index==smallest)break;
            swap(smallest,index);
            index=smallest;
        }

    }
    public void add(long data){
        heap[size++]=data;
        siftUp(size-1);

    }
    public long poll(){
        long smal=peek();
        heap[0]=heap[--size];
        siftDown(0);
        return smal;

    }
}

P5019 [NOIP 2018 提高组] 铺设道路

  1. 理解题意
    1. 铺设道路，每段道路的深度为$ a_i $每天都可以铺设一段道路，但是每天铺设的道路不能为0，问最少几天可以铺完
  2. 做题
    1. 对于第i个元素，如果第i-1个元素不为0，那么第i个元素必定要减去第i个元素的高度
    2. 因为每次填都要尽可能的填多一格区域
    3. 设第i-1个元素的高度为$ a_{i-1} $,那么第i个元素必定要减去 $ a_{i-1} $,因为这两个元素可以组成一个连续的非0区域,
    4. 那么对于第i个元素,高度$ a_{i-1} $由第i-1个元素填补了,只需要关注多出的部分要填补多少天即可,即 剩下部分要填补的天数=$ a_i-a_{i-1} $
    5. 如果第i个元素小于第i-1个元素,那么就不用管,因为会被i-1个元素的高度自动减掉
    6. 那么总的要填补的天数=每个坑位要填补的天数之和
    7. 对于第一个元素因为前面没有元素,那么可以将前面那个元素视为0,那么第一个格子要填补的天数是第一个格子的高度

P4447 [AHOI2018初中组] 分组

  1. 理解题意
    1. 我们要对一个序列进行分组,分的组别不限,但每个组的数字要连续的
    2. 求如何分组使得最少人数的组和别的分组方案的最少人数的组比最多
  2. 做题
    1. 假设现在已经分好组了,现在要添加一个元素,那我们要将这个元素分到哪个组呢
    2. 首先我们要考虑那些组可以分
    3. 筛选出来后,假设我们要分到最多人的那组,那么最少人数的那组的人数没有任何变化,那就不构成最少人数的那组人数最多了
    4. 那么我们的贪心操作就是,选择符合条件的组,然后选择人数最少的组进行加入,若没有符合条件的,那么就新建一个组
  3. 方法
    1. 普通分组$ O(n^2) $
      1. 记录每个组的最后一个元素,和最后一个元素相同的组的不同长度
      2. 为每个元素选择符合条件的组,然后选择一个长度最小的组进行加入
      3. 代码
public static void main(String[] args) throws IOException {
        int n=nextInt();
        long[] duiYuans=new long[n];
        for (int i = 0; i < n; i++) {
            duiYuans[i]=nextInt();
        }
        Arrays.sort(duiYuans);
        HashMap<Long, ArrayList<Integer>> group = new HashMap<>();
        int minLength=Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            long duiYuan=duiYuans[i];
            ArrayList<Integer> groupIns = group.get(duiYuan-1);
            ArrayList<Integer> groupThis = group.get(duiYuan);

            Integer min=0;
            if (groupIns !=null){

                min = groupIns.stream().min(Integer::compare).get();
                groupIns.remove(min);
                if (groupIns.isEmpty()){
                    group.remove(duiYuan-1);
                }

            }
            if (groupThis==null){
                groupThis=new ArrayList<>();
            }
            groupThis.add(min+1);
            group.put(duiYuan,groupThis);
        }
        for (Long l : group.keySet()) {

            minLength=Math.min(minLength,group.get(l).stream().min(Integer::compare).get());
        }
        out.println(minLength);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

2. 优先队列$ O(nlogn) $
    1. 使用优先队列维护同一个最后一个相同元素不用组的极值
    2. 这样每次查询的时候就不用一个一个找最小的组了,直接poll出堆顶即可,耗费$ O(1) $时间
    3. 代码

public static void main(String[] args) throws IOException {
        int n=nextInt();
        long[] duiYuans=new long[n];
        for (int i = 0; i < n; i++) {
            duiYuans[i]=nextInt();
        }
        Arrays.sort(duiYuans);
        HashMap<Long, PriorityQueue<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long cur=duiYuans[i];
            long pre=cur-1;
            int min=0;
            if (groups.containsKey(pre)){
                PriorityQueue<Integer> preMin = groups.get(pre);
                min = preMin.poll();
                if (preMin.isEmpty()){
                    groups.remove(pre);
                }
            }
            if (!groups.containsKey(cur)){
                groups.put(cur,new PriorityQueue<>());
            }
            groups.get(cur).add(min+1);

        }
        int minLength=Integer.MAX_VALUE;
        for (PriorityQueue<Integer> value : groups.values()) {
            minLength=Math.min(minLength,value.peek());
        }
        out.println(minLength);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

3. 二分查找
    1. 使用二分查找来找到第一个符合条件的组,然后找到循环找到最后一个符合条件的组,此时这个组就是长度最小的符合条件的组(第二步解释)
    2. 为什么向后循环到最后一个就是长度最小的那个组呢,因为每次插入都从后面插入,后面插入的组会比前的组的长度更小
    3. **<font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);">操作顺序</font>**<font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);">：每次将新元素添加到 </font>`<font style="background-color:rgb(252, 252, 252);">q[]</font>`<font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);"> 中最后一个合法的组（即通过 </font>`<font style="background-color:rgb(252, 252, 252);">while (pos < top && q[pos+1] == current) pos++;</font>`<font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);"> 找到最右侧可接续的组）。</font>
    4. <font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);">这种设计下，</font>**<font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);">较短的组会优先被填充</font>**<font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);">。因为当多个组的 </font>`<font style="background-color:rgb(252, 252, 252);">q[x]</font>`<font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);"> 值相同时，算法会选择最后一个组（即最晚创建的组），而较晚创建的组往往更短（因为早期创建的组可能已经扩展多次）</font>
    5. <font style="color:rgba(0, 0, 0, 0.9);background-color:rgb(252, 252, 252);">代码</font>

public static void main(String[] args) throws IOException {
        int n=nextInt();
        int[] duiyuan=new int[n];
        for (int i = 0; i < n; i++) {
            duiyuan[i]=nextInt();
        }
        Arrays.sort(duiyuan);
        int[] groupExpect =new int[200000];
        int[]  size=new int[200000];
        int groupNum=0;
        for (int i = 0; i < n; i++) {
            int cur=duiyuan[i];
            int left=0,right=groupNum;
            int pos=groupNum;
            while (left<=right){
                int mid=(left+right)/2;
                if (groupExpect[mid]>=cur){
                    pos=mid;
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }
            while (pos<groupNum&&groupExpect[pos+1]==cur){
                pos++;
            }

            if (pos<groupNum&&groupExpect[pos]==cur){//TODO >=可能有点问题
                groupExpect[pos]=cur+1;
                size[pos]++;
            }else {
                groupExpect[groupNum]=cur+1;
                size[groupNum]++;
                groupNum++;
            }
        }
        int min=Integer.MAX_VALUE;
        for (int i = 0; i < groupNum; i++) {
            min=Math.min(min,size[i]);
        }
        out.println(min);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

    6. <font style="background-color:#DF2A3F;">注意</font>
        1. 如果要排序,就不要选择多一个空间了,因为多出的0也会被加入排序中,相当于多了一个元素
        2. 或者选择区间排序

P1873 [COCI 2011/2012 #5] EKO / 砍树

  1. 理解题意
    1. 给定一排高度的树木,再给一个需要的木头,再给一个高度,只取这个高度上面的木头,问这个高度最高是多高,才能够取到需要的木头,即这个高度再小一点就取不到需要的木头
  2. 做题
    1.
    1. 如果我么将树木从小到大排序,那么如果锯子高度刚好是第i个树木的高度,那么就会将后面超出此高度的木头全部砍掉,
    2. 那么后面会砍掉多少呢,
    3. 如果我们从后面往前面推的话,
    4. 第n-1个会砍掉 n-1和n的差值
    5. 第n-2个会砍掉 第n-1个砍的+后面树木的棵树* (第n-2和 第n-1高度的差值)
    6. 第n-3个会砍掉 第n-1个砍的+后面树木的棵树* (第n-3和 第n-2高度的差值)
    7. 那么就可以得到递推公式
    8. 第i棵树木高度砍的木头=第i+1颗树木高度砍掉的木头+后面树木的棵树*(第i+1棵树木高度-第i棵树木高度)
    9. 然后我们只需要找到哪一个树木高度要砍掉的木头大于要砍的木头,然后再加上砍多的差值即可
    10. 代码
public static void main(String[] args) throws IOException {
        int n=nextInt();
        long m=nextLong();
        long[] hight= new long[n];
        long[] sum= new long[n];
        for (int i = 0; i < n; i++) {
            hight[i]=nextLong();
        }
        Arrays.sort(hight);
        for (int i = n - 2; i >= 0; i--) {
            sum[i]=sum[i+1]+(n-i-1)*(hight[i+1]-hight[i]);
        }

        int left=0,right=n-1;
        int pos=-1;
        while (left<=right){
            int mid=(left+right)/2;
            if (sum[mid]<m){
                right=mid-1;
            }else {
                pos=mid;
                left=mid+1;
            }
        }
        long ans=hight[pos];
        if (sum[pos]!=m){
//            long cha=hight[pos+1]-hight[pos];
//            while ((cha*(n-pos-1)+sum[pos+1])>=m){
//                cha--;
//            }
//            ans=hight[pos+1]-(cha+1);
            ans=hight[pos]+((sum[pos]-m)/(n-pos-1));
        }
        out.println(ans);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

2. 我们考虑优化
    1. 我们看到二分查找也是找那个刚好大于m的sum,
    2. 那么我么可以不用数组了,每次累加sum即可,然后,大于就停
    3. 代码

public static void main(String[] args) throws IOException {
        int n=nextInt();
        long m=nextLong();
        long[] hight= new long[n];
        long sum=0;
        for (int i = 0; i < n; i++) {
            hight[i]=nextLong();
        }
        Arrays.sort(hight);
        int i;
        for (i = n - 2; i >= 0; i--) {
            sum=sum+(n-i-1)*(hight[i+1]-hight[i]);
            if (sum>m)break;
        }
        long ans=sum;
        if (ans!=m){
            ans=hight[i]+((sum-m)/(n-i-1));
        }
        out.println(ans);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

二分答案

P2440 木材加工

  1. 理解题意
    1. 给n个木头,分成k段,每段的长度l都要一样,问长度l最长为多少段
  2. 做题
    1. 从题意可以看出,当长度l越短的时候,就越容易分成功,长度越长的时候,就越难分成功,
    2. 即设长度为l时,可以成功分成k段,那么当分的长度比l短的时候,若为l-1,则百分百会分成功
    3. 那么这道题就适合用二分答案了
  3. 二分答案
    1. 目标: 找到最大的l
    2. 那么l可能的长度为1~sum/k段,或者1~max(木头长)
    3. 上面那一步就确定了左右区间
    4. 那么怎么判定这个长度行不行呢
    5. 我们用每个木头长度/这个长度,然后累加可切割的木头数,
    6. 若是累加的木头数超过了目标切割段数k,那么这个长度就是可行的
    7. 如果这个长度可行,那么左边界就等于这个长度+1
    8. 如果不行,右边界等于这个长度-1
    9. 这一步相当于二分查找的mid
    10. 代码
      1. 注意点
        1. 注意第24行
        2. (left+right)/2变成left+(right-left)/2
        3. 这样可以防止溢出
        4. 公式推导
        5. left-left/2+right/2=left/2+right/2
public static void main(String[] args) throws IOException {
        int n=nextInt();
        int k=nextInt();

        long[] woods = new long[n];
        long sum=0;
        for (int i = 0; i < n; i++) {
            woods[i]=nextLong();
            sum+=woods[i];

        }


        long left=1;
        long right= Math.min(sum / k, Arrays.stream(woods).max().getAsLong());
        long ans=0;

        if (right<1) {
            out.println(0);
            out.flush();
            return;
        }
        while (left<=right){
            long mid =left+(right-left)/2;
            long cnt=0;
            for (int i = 0; i < n; i++) {
                cnt+= (woods[i]/mid);
                if (cnt>=k)break;
            }

            if (cnt>=k){
                ans=mid;
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        out.println(ans);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

P3743 小鸟的设备(实数二分,100次循环保证精度就行)

  1. 理解题意
    1. 题目说有n个设备,每个设备每秒消耗$ a_i $格电量,而每个设备自带$ b_i $格电,并且你还有一个充电宝,你可以给每个设备每秒冲$ p $格电,注意,消耗的电和冲进去的电都是连续的,即你可以给$ a_i $冲 0.1秒的电,即$ 0.1\times p $格电,问最久的可使用时间
  2. 做题
    1. 最久的可使用时间,我们可以想到二分答案,即找最优值
    2. 确定参数,即可使用时间
    3. 范围就是0~1e10即可,题目要求double
    4. 确定check函数要怎么写
    5. 给定一个mid可使用时间,要怎么判断能不能达到呢
    6. 可以累加mid时间后,每个设备电量的缺口,即$ a_i \times mid-b_i $
    7. 若是累加后的需要的缺口sum比$ mid \times p $还要多,证明没法填补,那么这个时间就不行
    8. 代码
public static void main(String[] args) throws IOException {
        int n=nextInt(),p=nextInt();
        phones = new long[n][2];
        long sumAi=0;
        for (int i = 0; i < n; i++) {
            phones[i][0]=nextLong();
            phones[i][1]=nextLong();
            sumAi+=phones[i][0];
        }
        if (sumAi<=p){
            out.println(-1);
            out.flush();
            return;
        }

        double left=0,right=1e10;
        double ans=1e10+1;
        for (int i = 0; i < 100; i++) {
            double mid=left+(right-left)/2;
            if (check(mid,n,p)){
                ans=mid;
                left=mid;
            }else {
                right=mid;
            }
        }

        out.printf("%.10f",ans);



        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
    public static boolean check(double mid,int n,int p){
        double sum=0;
        for (int i = 0; i < n&&sum<=(mid*p); i++) {
            sum+=Math.max(0,(phones[i][0]*mid-phones[i][1]));
        }
        return sum<=(mid*p);
    }

广度优先搜索(BFS)

P1443 马的遍历

  1. 理解题意
    1. 给一个$ n \times m $的棋盘给你,再给一个 (x,y),在这个点上有一个马,然后问你,马走到棋盘上的任意一个点的最短路径是什么
    2. 对于最短路径问题,我们可以使用bfs
  2. 做题
    1. 我们先写出马的八个方向的坐标值变化
    2. 那么bfs的每一层就是八个方向中的可到达的点,
    3. 那么就很明确了,
    4. 先从队列中poll出最前面的点,
    5. 然后求出可到达并且没有到过的点(没到过,说明是最短路径,bfs的性质决定,可以问问ai),
    6. BFS的层级遍历特性保证首次访问即最短路径，无需额外判断。
    7. 将可到达的点入队,
    8. 更新可到达点的步数,即用当前点+1即可
  3. 注意,
    1. 这道题的起始坐标点的坐标系是从1,1开始算的,在写代码的时候要-1
  4. 代码
static int[] col={-2,-1,1,2,2,1,-1,-2};
    static int[] row={-1,-2,-2,-1,1,2,2,1};
    static int n,m,x,y;

    public static void main(String[] args) throws IOException {
        int[][] qiPan;
        n=nextInt();
        m=nextInt();
        x=nextInt()-1;
        y=nextInt()-1;
        Queue<int[]> queue=new ArrayDeque<>();
        qiPan=new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(qiPan[i],-1);
        }
        qiPan[x][y]=0;
        queue.offer(new int[]{x, y});

        while (!queue.isEmpty()){
            int[] cur = queue.poll();
            for (int i = 0; i < 8; i++) {
                int[] newPoint = new int[2];
                newPoint[0]=cur[0]+row[i];
                newPoint[1]=cur[1]+col[i];

                if (newPoint[0]>=0&&newPoint[0]<n&&newPoint[1]>=0&&newPoint[1]<m&&qiPan[newPoint[0]][newPoint[1]]==-1){
                    qiPan[newPoint[0]][newPoint[1]]=qiPan[cur[0]][cur[1]]+1;
                    queue.offer(newPoint);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                out.printf("%-5d",qiPan[i][j]);
            }
            out.println();
        }

        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

P2895 [USACO08FEB] Meteor Shower S

  1. 理解题意
    1. 给一个格子,某个时间点会砸陨石,坐标为(x,y),时间为$ t_i $,你要从原点出发,走到永远不会砸陨石的地方,注意(陨石会将陨石坐标,和上下左右五个格子砸到,然后你就不能走了)
  2. 做题
    1. 求最短步骤,即广度优先搜索
  3. 坑
    1. 坐标不能低于0，但可以超300！
    2. 流星定时砸下；
    3. 流星砸下时间已最早的那个为准！
    4. 如果出不去还要输出-1！
  4. 代码
static int[] forwordX={-1,0,1,0,0};
    static int[] forwordY={0,1,0,-1,0};
    public static void main(String[] args) throws IOException {
        int m=nextInt();
        int[][] start = new int[302][302];
        int[][] step = new int[302][302];
        for (int i = 0; i < start.length; i++) {
            Arrays.fill(start[i],Integer.MAX_VALUE);
            Arrays.fill(step[i],-1);

        }
        step[0][0]=0;

        for (int i = 0; i < m; i++) {
            int x = nextInt();
            int y = nextInt();
            int t = nextInt();

            for (int j = 0; j < 5; j++) {
                int nx=x+forwordX[j];
                int ny=y+forwordY[j];
                if (nx>=0&&nx<=301&&ny>=0&&ny<=301){
                    start[nx][ny]=Math.min(t,start[nx][ny]);
                }
            }
        }
        Queue<int[]> queue=new ArrayDeque<>();
        queue.offer(new int[]{0,0,0});
        int ans=-1;
        boolean flag=true;
        while (!queue.isEmpty()&&flag){
            int[] cur = queue.poll();
            for (int i = 0; i < 4&&flag; i++) {
                int nx=cur[0]+forwordX[i];
                int ny=cur[1]+forwordY[i];
                int nt=cur[2]+1;
                if (nx>=0&&ny>=0&&nt<start[nx][ny]&&step[nx][ny]==-1){
                    step[nx][ny]=step[cur[0]][cur[1]]+1;
                    if (start[nx][ny]==Integer.MAX_VALUE){
                        ans=step[nx][ny];
                        flag=false;
                        break;
                    }
                    queue.offer(new int[]{nx,ny,nt});

                }

            }
        }
        out.println(ans);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }

P1032 [NOIP 2002 提高组] 字串变换

  1. 理解题意
    1. 给定a，b两个字符串，并给定一系列的规则，每个规则为将字符串里面的 字符进行转换，如将‘a’->'nb’这样转换，问你最短几步可以从a字符串转到b字符串
  2. bfs
    1. 由于bfs的特性，总是先访问离起点比较近的，所以我们使用bfs
    2. 我们首先以a字符串为起点
    3. 然后每一层为所有的规则，这里要注意，每一层即每一个规则在上一个字符串中有多种可能，即每一层不一定为规则数，如 字符串’aaaaaa’，替换规则为，‘a’->‘nb’,那么这一层就有6种可能，将a替换成’nb’
    4. 将每一种可能转换，并进行入队
  3. 注意
    1. 需要判断一下这个可能又没有被访问过，如果访问过就跳过，使用set来存储访问过的可能，
    2. 注意40行
import java.util.*;

public class Main  {
    static int step=-1;
    static ArrayList<String[]> rules;
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a =sc.next(),b=sc.next();
    sc.nextLine();
    rules=new ArrayList<>();
    while (sc.hasNextLine()){
        rules.add(sc.nextLine().split(" "));
    }
    Queue<ArrayList> queue=new ArrayDeque();
    ArrayList<Object> first = new ArrayList<>();
    HashSet<String> visted = new HashSet<>();
    visted.add(a);
    first.add(a);
    first.add(0);
    queue.add(first);
    while (!queue.isEmpty()){
        ArrayList arr = queue.poll();
        String strPrototype = (String) arr.get(0);
        int steptemp = (int) arr.get(1);
        if (strPrototype.equals(b)) {
            step=steptemp;
            break;
        }
        if (steptemp>10)break;
        for (int i = 0; i < rules.size(); i++) {
            String[] strArr = rules.get(i);
            String strRuleA=strArr[0];
            String strRuleB=strArr[1];
            int res=0;
            while (true){
                res = strPrototype.indexOf(strRuleA,res);
                StringBuilder str = new StringBuilder(strPrototype);
                if (res ==-1)break;
                str.replace(res,res+strRuleA.length(),strRuleB);
                if (!visted.contains(str.toString())){
                    ArrayList<Object> element = new ArrayList<>();
                    element.add(str.toString());
                    element.add(steptemp+1);
                    queue.offer(element);
                    visted.add(str.toString());
                }
                res++;
            }
        }
    }
    if (step!=-1){
        System.out.println(step);
    }else System.out.println("NO ANSWER!");
    sc.close();
    }

}

并查集

P8654 [蓝桥杯 2017 国 C] 合根植物

  1. 理解题意
    1. 给一个大格子，每个小格子里面的植物可以和上下左右的格子合并成一个植物，给一个k，表示两个格子合并了，问最后一共有多少个植物
  2. 做题
    1. 标准的求连通分量数的问题
    2. 并查集
    3. 首先我们用并查集把能连的都连起来，
    4. 然后我们可以一个一个遍历并查集里面的prev，如果当前的prev[i]==i的，那么就是顶点，那么就是一个连通分量
    5. 或者我们可以使用hashset，在遍历的时候直接添加当前节点的顶点，然后利用set的特性进行去重就行了
  3. 代码
import java.io.*;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    public static void main(String[] args) throws IOException {
        int n=nextInt(),m=nextInt();
        int k=nextInt();
        int cnt=0;
        UnionFind uf = new UnionFind(n * m + 1);
        for (int i = 0; i < k; i++) {
            int a=nextInt(),b=nextInt();
            uf.Union(a,b);
        }
        for (int i = 1; i <= n * m; i++) {
            if (uf.prev[i]==i)cnt++;
        }
        out.println(cnt);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}
class UnionFind{
    int[] prev;
    int[] rank;
    public UnionFind(int size){
        prev=new int[size];
        rank=new int[size];
        Arrays.fill(rank,1);
        for (int i = 0; i < size; i++) {
            prev[i]=i;
        }
    }
    public int find(int x){
        if(prev[x]==x)return x;
        return prev[x]=find(prev[x]);
    }

    public boolean Union(int x,int y){
        int prevX=find(x);
        int prevY=find(y);
        if (prevX==prevY)return false;
        if (rank[prevX]<rank[prevY]){
            prev[prevX]=prevY;
            rank[prevY]+=rank[prevX];
        }else{
            prev[prevY]=prevX;
            rank[prevX]+=rank[prevY];
        }
        return true;
    }
}

蓝桥杯历届试题-国王的烦恼

  1. 理解题意
    1. 给定n个岛，并且给定m个桥，每个桥两端连接两个小岛，每个小岛之间可以有多个桥
    2. 每个桥有时间限制，到时间了会断快，以后就用不了了，
    3. 当断开的时候并且两个小岛无法互相到达的后一天，村民就会抗议一天
    4. 问你一共抗议了多少天
  2. 做题
    1. 逆向思维，默认小岛都是被桥连着的，那我返过来呢，默认桥是空的，即每个小岛都是孤岛，只有当两个岛成功连通的时候，那么这个时候才记录天数，即该桥是连接两颗树的关键通路
    2. 那么这样就很符合并查集的并操作了，所以使用并查集
    3. 先将桥逆序排序，
    4. 然后模拟桥的修建
    5. 当两座岛同属于同一个数的时候就记录天数，使用set记录，避免重复
  3. 代码
import java.io.*;
import java.util.*;

public class Main {
    static class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int size) {
            parent = new int[size + 1]; // 岛屿编号从1开始
            rank = new int[size + 1];
            for (int i = 0; i <= size; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return false;
            }
            // 按秩合并，这里秩是集合大小
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                rank[rootY] += rank[rootX];
            } else {
                parent[rootY] = rootX;
                rank[rootX] += rank[rootY];
            }
            return true;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<int[]> bridges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            bridges.add(new int[]{a, b, t});
        }

        // 按t降序排序
        Collections.sort(bridges, (o1, o2) -> o2[2] - o1[2]);

        UnionFind uf = new UnionFind(n);
        Set<Integer> protestDays = new HashSet<>();

        for (int[] bridge : bridges) {
            int a = bridge[0];
            int b = bridge[1];
            int t = bridge[2];

            if (uf.union(a, b)) {
                protestDays.add(t);
            }
        }

        System.out.println(protestDays.size());
    }
}

P1596 [USACO10OCT] Lake Counting S

  1. 理解题意
    1. 这道题本来是dfs或者bfs的题，但是这道题也可以用并查集做
    2. 题意要求给定一个农田，然后格子里面是w表示有水，8个方向的水可以相互连通成一滩水，问一共有多少滩水
  2. 做题
    1. dfs
      1. 如果遇到w就开始搜索，然后水的数量+1
      2. 每一层的搜索决策为8个方向，如果是w，就变为.即可，
      3. 递归结束的时候这滩水就没了
    2. 并查集
      1. 我们也可以枚举每个格子，如果是w,则判断8个方向，如果为w则加入同一滩水所在的树中
    3. 代码
import java.util.Scanner;

public class Main {
    static char[][] ponds;
    static int[] fowordX={-1,-1,0,1,1,1,0,-1};
    static int[] fowordY={0,1,1,1,0,-1,-1,-1};
    static boolean[][] reach;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        sc.nextLine();
        ponds=new char[n][m];
        reach=new boolean[n][m];
        for (int i = 0; i < n; i++) {
            ponds[i]=sc.nextLine().toCharArray();
        }
        int cnt=0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (ponds[i][j]=='W'){
                    cnt++;
                    reach[i][j]=true;
                    dfs(i,j,n,m);
                }
            }
        }

        System.out.println(cnt);
        sc.close();
    }
    public static void dfs(int x,int y,int n,int m){
        if (ponds[x][y]=='.')return;
        for (int i = 0; i < 8; i++) {
            int nx=x+fowordX[i];
            int ny=y+fowordY[i];
            if (nx<0||nx>=n||ny<0||ny>=m)continue;
            if (ponds[nx][ny]=='.')continue;
            if (reach[nx][ny])continue;
            reach[nx][ny]=true;
            dfs(nx,ny,n,m);
            reach[nx][ny]=false;
        }
        ponds[x][y]='.';

    }
}

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    static int[] fowordX={-1,-1,0,1,1,1,0,-1};
    static int[] fowordY={0,1,1,1,0,-1,-1,-1};
    public static void main(String[] args) throws IOException {
        int n=nextInt(),m=nextInt();

        char[][] field=new char[n][m];
        for (int i = 0; i < n; i++) {
            field[i]=br.readLine().toCharArray();
        }
        UnionFind uf = new UnionFind(n * m);
        int cnt=0;
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m; j++) {
                if (field[i][j]=='.')continue;
                for (int k = 0; k < 8; k++) {
                    int nx=i+fowordX[k];
                    int ny=j+fowordY[k];
                    if (nx<0||nx>=n||ny<0||ny>=m)continue;
                    if (field[nx][ny]=='.')continue;
                    uf.union(i*m+j,nx*m+ny);
                }
            }
        }
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m; j++) {
                if (field[i][j]=='.')continue;
                if (uf.prev[i*m+j]==i*m+j)cnt++;
            }
        }
        out.println(cnt);
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}
class UnionFind{
    int[] prev;
    int[] rank;
    public UnionFind(int size){
        prev=new int[size];
        rank=new int[size];
        Arrays.fill(rank,1);
        for (int i = 0; i < size; i++) {
            prev[i]=i;
        }
    }
    public int find(int x){
        if (prev[x]==x)return x;
        return prev[x]=find(prev[x]);
    }

    public boolean union(int x,int y){
        int prevX=find(x);
        int prevY=find(y);
        if (prevX==prevY)return false;
        if (rank[prevX]<rank[prevY]){
            prev[prevX]=prevY;
            rank[prevY]+=rank[prevX];
        }else {
            prev[prevY]=prevX;
            rank[prevX]+=rank[prevY];
        }
        return true;
    }
}

P8686 [蓝桥杯 2019 省 A] 修改数组

  1. 理解题意
    1. 题目要求给一个数组，要求改数组，使得第i个元素和前面的0~(i-1)个元素不同
  2. 并查集
    1. 方法一
      1. 这道题我们可以使用并查集来做，如果是相同的数字，那么就不能加入同一个集合，那么就可以将这个数字一直加一，直到找到不同的数字
    2. 方法二
      1. 我们可以优化一下这个并查集，将顶点的元素记录为下一个最近的可使用元素，这样，我们在查找可用元素的时候就会快很多
    3. 代码
import java.io.*;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    public static void main(String[] args) throws IOException {
        int n=nextInt();
        int[] num=new int[n];
        for (int i = 0; i < n; i++) {
            num[i]=nextInt();
        }
        UnionFind uf = new UnionFind(1000000+1);
        for (int i = 1; i < n; i++) {
            num[i]--;
            while (!uf.Union(++num[i],num[i-1]));
        }
        for (int i = 0; i < n; i++) {
            out.print(num[i]+" ");
        }
        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}
class UnionFind{
    int[] prev;
    int[] rank;
    public UnionFind(int size){
        prev=new int[size+1];
        rank=new int[size+1];
        Arrays.fill(rank,1);
        for (int i = 1; i <= size; i++) {
            prev[i]=i;
        }
    }
    public int find(int x){
        if (prev[x]==x)return x;
        return prev[x]=find(prev[x]);
    }
    public boolean Union(int x,int y){
        int prevX=find(x);
        int prevY=find(y);
        if (prevX==prevY)return false;
        if (rank[prevX]<rank[prevY]){
            prev[prevX]=prevY;
            rank[prevY]+=rank[prevX];
        }else {
            prev[prevY]=prevX;
            rank[prevX]+=rank[prevY];
        }
        return true;
    }
}

import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in=new StreamTokenizer(br); // 最优输入流
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); // 最优输出流

    static int nextInt() throws IOException { // 输入流的封装函数
        in.nextToken();
        return (int) in.nval;
    }
    static Double nextDouble() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  in.nval;
    }
    static long nextLong() throws IOException { // 输入流的封装函数
        in.nextToken();
        return  (long) in.nval;
    }
    static int find(int x){
        if (pre[x]==x)return x;
        return pre[x]=find(pre[x]);
    }
    static int[] pre;
    public static void main(String[] args) throws IOException {
        int n=nextInt();
        pre=new int[100000+2];
        for (int i = 0; i < pre.length; i++) {
            pre[i]=i;
        }
        int[] num=new int[n];
        for (int i = 0; i < n; i++) {
            int a=nextInt();
            int val=find(a);
            num[i]=val;
            pre[val]=find(val+1);
        }
        for (int i = 0; i < n; i++) {
            out.print(num[i]+" ");
        }

        out.flush(); // 刷新输出流
        out.close();//关闭流
    }
}

更新: 2025-04-08 20:23:50
原文: https://www.yuque.com/duifangzhengzaishuru-rqbua/axyc58/geag8ohrp1fiiypq