AcWing蓝桥杯AB组辅导课10、疑难杂题

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

文章目录

前言

前段时间为了在面试中能够应对一些算法题走上了刷题之路大多数都是在力扣平台刷目前是400+再加上到了新学校之后了解到学校也有组织蓝桥杯相关的程序竞赛打算再次尝试一下就想系统学习一下算法再此之前是主后端工程为主算法了解不多刷过一小段时间前段时间也是第一次访问acwing这个平台感觉上面课程也是比较系统平台上题量也很多就打算跟着acwing的课程来走一段路大家一起共勉加油

  • 目前是打算参加Java组所以所有的题解都是Java。

所有博客文件目录索引博客目录索引(持续更新)

本章节复杂DP习题一览包含所有题目的Java题解链接

第十讲学习周期2023.2.2-2.4

image-20230205132721618

例题

习题

例题1AcWing 1242. 修改数组并查集

题目链接AcWing 1242. 修改数组

分析

首先看下数据量总共元素有10万个值最大为100万。时间复杂度应该控制在O(n.logn)或者O(n)。

本题可以使用平衡树O(n.logn)、并查集O(n+m)来进行解决。

并查集思路普通并查集主要是查找一个范围中的代表元素是树型的而在本题中可以转换为单链表型实际代码并没有多大的改动主要是思路上。

image-20230202110838128

核心思想对于并查集数组中通过对应数组位置的元素值应当存入下一个要找的点的值。

初始状态

image-20230202111507342

使用单链表并查集后状态

image-20230202111044244

实际上就是做一个find查询找到没有访问过的数然后我们来进行一个手动赋值操作。

题解单链表式并查集

复杂度分析时间复杂度O(n + m)空间复杂度O(n + m)

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

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    //最大情况就是Ai的最大值向后偏移10万数据
    static final int N = 1100010;
    static int n;
    //并查集
    static int[] p = new int[N];
    //存储读入数组
    // static int[] a = new int[N];
    
    //并查集查询下一个节点
    public static int find(int num) {
        if (num != p[num]) 
            p[num] = find(p[num]); //路径压缩
        return p[num];
        
    }
    
    public static void main(String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine());
        
        //初始化并查集
        for (int i = 0; i < N; i ++) {
            p[i] = i;
        }
        
        //读入数据
        String[] ss = cin.readLine().split(" ");
        for (int i = 0; i < n; i ++) {
            int num = Integer.parseInt(ss[i]);
            //查找最近元素
            int findNum = find(num);
            System.out.printf("%d ", findNum);
            p[findNum] = findNum + 1;
        }
        
    }
    
}

image-20230202111935946

例题2AcWing 1234. 倍数问题背包问题+贪心

题目链接AcWing 1234. 倍数问题

分析

本题的话是组合问题我们可以采用DP来进行解决。

闫式DP分析法

image-20230202131209703

下方DP的时间复杂度10万 * 3 * 1000大概4个亿会超时。

for (int i = 0; i < N; i ++)  //遍历i个数
  for (int j = 0; j < 3; j ++)  //前i个选择j个
  	for (int k = 0; k < K; k ++) //前i个选择j个的和 mod K 的目标余数为k
  		dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - 1][((k - a[i] % K) + K) % K] + a[i]);

正常DP流程会超时需要进行优化。

接着我们来使用贪心进行优化我们是否可以从i个数中去筛选出来一部分的数字呢

  • 由于我们在求dp[i][j][k]目标过程中实际上是来使用k-a[i] % K来进行操作的实际上对于10万个数每个数% K得到的值一定会是在[0, K - 1]范围中可能同一个余数对应好几个数那么我们是否可以找到对应%k中例如5 % 2 = 19%2 = 1我们只拿到对应最大的三个数这样即可将原本10万个数直接筛选为3*1000 = 3000个数。

通过贪心优化的时间复杂度筛选+排序(约15 * 10万)也就是150万再加上dp3000*3*1000900万实际上最终合起来为1000万运行量可以AC。

实际上对于dp[i][j][k]还可以进行状态压缩转为二维 不过对于这种转二维情况需要在内循环中进行逆序遍历。

题解101背包问题三维解法贪心优化

复杂度分析时间复杂度O(n.k)空间复杂度O(n.k)

//dp+贪心
import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int n, K;
    //DP数组
    static int[][][] fn = new int[3010][4][1010];
    //存储余数为[0, K - 1]的数对应数组下标为余数值
    static ArrayList<Integer>[] nums = new ArrayList[1010];
    //存储筛选过后的
    static int[] a = new int[3010];
    static int p;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        K = Integer.parseInt(ss[1]);
        //初始化集合
        for (int i = 0;i < K; i ++) {
            nums[i] = new ArrayList<Integer>();
        }
        
        //遍历所有的数来存储到对应下标为余数的集合中
        ss = cin.readLine().split(" ");
        for (int i = 0; i < n; i ++) {
            int num = Integer.parseInt(ss[i]);
            nums[num % K].add(num);
        }
        //对所有余数情况的集合来进行排序每个集合取前3个
        p = 1;
        for (int i = 0; i < K; i ++) {
            ArrayList<Integer> res = nums[i];
            //从大到小排序
            Collections.sort(res, (o1, o2) -> o2 - o1);
            //System.out.println(res);
            for (int j = 0; j < 3 && res.size() > j; j ++) {
                a[p++] = res.get(j);
            }
        }
        
        //dp数组初始化
        //全部赋初值
        for (int i = 0; i < p; i ++) {
            for (int j = 0; j < 4; j ++) {
                Arrays.fill(fn[i][j], Integer.MIN_VALUE);
            }
        }
        for (int i = 0; i < p; i ++) {
            fn[i][0][0] = 0;
        }
        
        //DP
        for (int i = 1; i < p; i ++)   //筛选过后的数
            for (int j = 1; j <= 3; j ++)  //选择j个数  01背包循环要逆序
                for (int k = 0; k < K; k ++) {
                    fn[i][j][k] = Math.max(fn[i - 1][j][k], fn[i - 1][j - 1][(k - a[i] % K + K) % K] + a[i]);
                }
                    
        
        System.out.println(fn[p - 1][3][0]);
        
    }
    
}

image-20230202155539430

题解2题解1基础上三维转二维

复杂度分析时间复杂度O(n.k)空间复杂度O(k)

//dp+贪心
import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static int n, K;
    //DP数组
    static int[][] fn = new int[4][1010];
    //存储余数为[0, K - 1]的数对应数组下标为余数值
    static ArrayList<Integer>[] nums = new ArrayList[1010];
    //存储筛选过后的
    static int[] a = new int[3010];
    static int p;
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        K = Integer.parseInt(ss[1]);
        //初始化集合
        for (int i = 0;i < K; i ++) {
            nums[i] = new ArrayList<Integer>();
        }
        
        //遍历所有的数来存储到对应下标为余数的集合中
        ss = cin.readLine().split(" ");
        for (int i = 0; i < n; i ++) {
            int num = Integer.parseInt(ss[i]);
            nums[num % K].add(num);
        }
        //对所有余数情况的集合来进行排序每个集合取前3个
        for (int i = 0; i < K; i ++) {
            ArrayList<Integer> res = nums[i];
            //从大到小排序
            Collections.sort(res, (o1, o2) -> o2 - o1);
            //System.out.println(res);
            for (int j = 0; j < 3 && res.size() > j; j ++) {
                a[p++] = res.get(j);
            }
        }
        
        //System.out.println(Arrays.toString(a));
        
        //dp数组初始化
        for (int i = 0; i < 4; i ++) 
            Arrays.fill(fn[i], Integer.MIN_VALUE);
        
        fn[0][0] = 0;
        
        //DP
        for (int i = 0; i < p; i ++)   //筛选过后的数
            for (int j = 3; j >= 1; j --)  //选择j个数
                for (int k = 0; k < K; k ++) //余数为k
                    fn[j][k] = Math.max(fn[j][k], fn[j - 1][(k - a[i] % K + K) % K] + a[i]);
                    
        
        System.out.println(fn[3][0]);
        
    }
    
}

image-20230202155903430

例题3AcWing 1213. 斐波那契快速幂、龟速乘、分类讨论第五届蓝桥杯

题目链接AcWing 1213. 斐波那契

分析

首先理解题意目标求的式子为[f(1)+f(2)+...+f(n)] mod f(m) mod p而由于nm都为1018次方非常大我们只有对其式子进行化解取mod才能够取得最终结果我们最终的方案为矩阵快速幂+龟速乘法+分类讨论。

学习参考博客AcWing 1213. 斐波那契

优化1[f(1)+f(2)+...+f(n)] => f(n + 2) - 1

f(1) = f(3) - f(2)
f(2) = f(4) - f(3)
f(3) = f(5) - f(4)
...
f(n) = f(n + 2) - f(n + 1)
将f(1)+...+f(n) = f(n + 2) - f(2) = f(n + 2) - 1

此时目标式子为[f(1)+f(2)+...+f(n)] mod f(m) => [f(n + 2) - 1] mod f(m) 。

我们现将[f(n + 2) - 1] mod f(m) 看作为整体f(n) mod f(m)

优化2f(n) mod f(m) => f(n mod m) * f(m - 1)n/m

f(n) mod f(m)

n >= m
f(m + 1) = f(m) + f(m - 1)       mod f(m)    =>      f(m + 1) = f(m - 1)
f(m + 2) = f(m + 1) + f(m)       mod f(m)    =>      f(m + 2) = f(m + 1) = f(m - 1) 
f(m + 3) = f(m + 2) + f(m + 1)   mod f(m)    =>      f(m + 3) = 2 * f(m - 1)
f(m + 4) = f(m + 3) + f(m + 2)   mod f(m)    =>      f(m + 4) = 3 * f(m - 1)
...  最终左边的系数即为f(k)
f(m + k) mod f(m) = f(k) * f(m - 1)
此时推出结论f(n) mod f(m) = f(m + k) = f(n - m) * f(m - 1)

又n可能>多个m乘积即f(n - m) * f(m - 1)
				  f(n - 2m) * f(m - 1)^2
				  ...
				  f(n mod m) *  f(m - 1)^(n/m)

接着我们来针对于f(n mod m) * f(m - 1)n/m来继续进行化解针对于 f(m - 1)n/m。

  • 根据结论f(n)2 = (-1)(n+1) + f(n-1) * f(n+1)。

  • //可以来尝试代入n=3计算
f(3)^2 = 4
(-1)^(3+1) + f(3-1) * f(3+1) = (-1)^4 + f(2) * f(4) = 1 + 3 = 4
//得证
    
//代入n=n-1来尝试进行推导到f(n)^2
f(n - 1)^2 = (-1)^n + f(n - 2) * f(n)
           = (-1)^n + [f(n) - f(n-1)] * f(n)
           = (-1)^n + [f(n)]^2 - f(n - 1) * f(n)
//左右移项
[f(n)]^2 = (-1)^(n+1) + f(n-1)^2 + f(n) * f(n-1)
         = (-1)^(n+1) + (f(n) + f(n - 1)) * f(n - 1)
         = (-1)^(n+1) + f(n + 1) * f(n - 1)   //推导成功

通过小结论f(n)2 = (-1)(n+1) + f(n-1) * f(n+1)可以得到f(m - 1)2 = (-1)m+ f(m - 2) * f(m)

f(m - 1)2是f(m - 1)n/m中的一部分可以说是由若干个f(m - 1)2和f(m - 1)组成这就需要进行额外讨论了要看n/m为奇偶数情况。

此时我们要对f(n mod m) * f(m - 1)n/m进行分类讨论

  • 数/偶=奇、数/偶=偶。

情况1当m为偶数时

① n m n \over m mn​为偶数 【f(n mod m)】

此时就有偶数个f(m-1)[f(m-1)] n/m mod f(m)结果就为1。

f(n mod m) * f(m - 1)n/m = f(n mod m)

**② n m n \over m mn​为奇数 ** 【f(n mod m) * f(m-1)】

此时有奇数个f(m-1)此时[f(m-1)] n/m同余为f(m-1)

f(n mod m) * f(m - 1)n/m = f(n mod m) * f(m-1)

情况2当m为奇数

① n m n \over m mn​为偶数 n 2 m n \over 2m 2mn​为偶数 【 f(n mod m)】

此时有偶数个f(m-1)并且内部为偶数个–1乘

f(n mod m) * f(m - 1)n/m = f(n mod m)

② n m n \over m mn​为偶数 n 2 m n \over 2m 2mn​为奇数【f(m) - f(n mod m)】

偶数个f(m-1)有奇数个-1相乘

f(n mod m) * f(m - 1)n/m = f(n mod m)*-1又该数不能为负最终要加上f(m)此时变为

f(n mod m) * f(m - 1)n/m = f(m) - f(n mod m)

③ n m n \over m mn​为奇数 n 2 m n \over 2m 2mn​为偶数【f(m - 1) * f(n mod m)】

此时由奇数个f(m - 1)偶数个-1相乘

f(n mod m) * f(m - 1)n/m = f(m - 1) * f(n mod m)

④ n m n \over m mn​为奇数 n 2 m n \over 2m 2mn​为奇数 【f(m) - f(m - 1) * f(n mod m)】

此时由奇数个f(m - 1)奇数个-1相乘

f(n mod m) * f(m - 1)n/m = -f(m - 1) * f(n mod m)有可能为负数最终要加上f(m)此时变为

f(n mod m) * f(m - 1)n/m = f(m) - f(m - 1) * f(n mod m)

在上面分类讨论中你可以看到有类似于f(n) * f(m)的情况由于题目给出的数据量十分大可能就会造成溢出所以我们这里需要将一个乘法转变为加法在这个加法过程中来减少溢出的情况即龟速乘法。

  • a*b看做是b个a进行相加即可对在过程中进行一个预处理a + 2a + 4a…+ 2n-1 * a

题解矩阵快速幂+龟速乘法+分类讨论

复杂度分析时间复杂度O(logn)空间复杂度O(1)

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

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static long n, m, p;
    
    //龟速乘法
    //a*b => 例如5a  a + 2a + 2a
    static long qmul(long a, long b) {
        long res = 0;
        while (b != 0) {
            if ((b & 1) == 1) res = (res + a) % p;
            a = (a + a) % p;
            b >>= 1;
        }
        return res;
    }
    
    //矩阵乘法
    static void mul(long[][] a, long [][] b) {
        //临时矩阵
        long[][] temp = new long[2][2];
        for (int i = 0; i < 2; i ++) 
            for (int j = 0; j < 2; j ++)
                for (int k = 0; k < 2; k ++) 
                    temp[i][j] = (temp[i][j] + qmul(a[i][k], b[k][j])) % p;
        //拷贝
        for (int i = 0; i < 2; i ++) 
            for (int j = 0; j < 2; j ++)
                a[i][j] = temp[i][j];
    }
    
    //计算f(n)
    static long F(long n) {
        //极端情况
        if (n == 0) return 0;
        //根据fn来进行构造矩阵
        //fn分别为f(1) f(2)
        long[][] f = {
            {1, 1},
            {0, 0}
        };
        //累乘矩阵
        long[][] a = {
            {0, 1},
            {1, 1}
        };
        //快速幂
        for (long k = n - 1; k != 0; k >>= 1){
            if ((k & 1) == 1) mul(f, a);
            mul(a, a);
        }
        return f[0][0];
    }
    
    //(F(m - 1) * F(n % m) - 1) mod F(m)
    //(F(m - 1) * F(k) - 1) mod F(m)
    public static long H(long m, long k) {
        //若是n mod m为奇数
        if (k % 2 == 1) return F(m - k) - 1;
        else 
        {   // n mod m为偶数
            //结论f(m - 1)* f(k) = f(m) - f(m - k)
            //判断f(m) - f(m - k)是否相等
            //情况1k == 0f(m - k) = f(m)
            //情况2f(2) - f(1) = 0
            if (k == 0 || m == 2 && m - k == 1) return F(m) - 1;
            else return F(m) - F(m - k) - 1;
        }
    }
    
    //F(n) - 1  %  F(m)
    static long G(long n, long m) { 
        //情况1m为偶数
        if (m % 2 == 0) {
            //n/m是偶数  f(n mod m)
            if (n / m % 2 == 0) 
            {
                //特判情况
                if (n % m == 0) return F(m) - 1;
                else return F(n % m) - 1;
            }else
            {
                // n/m为奇数  f(n mod m) * f(m-1)
                return H(m, n % m);
            }
        }else { //情况2m为奇数
            //n/m为偶数n/2m为偶数  f(n mod m)
            if (n / m % 2 == 0 && n / (2 * m) % 2 == 0)
            {
                //特判
                if (n % m == 0) return F(m) - 1;
                else return F(n % m) - 1;
            }
            else if (n / m % 2 == 0 && n / (2 * m) % 2 == 1)  //n/m为偶数n/2m为奇数  f(m) - f(n mod m)
            {   
                //特判f(m) - f(n mod m)为0情况  当f(m) == f(n % m),即m=2,n%m=1时
                //f(m) - f(n mod m) = 0时
                if (m == 2 && n % m == 1) return F(m) - 1;
                else return F(m) - F(n % m) - 1;
            }
            else if (n / m % 2 == 1 && n / (2 * m) % 2 == 0)  //n/m为奇数n/2m为偶数  f(m - 1) * f(n mod m)
            {   
                return H(m, n % m);
            }
            else 
            {
                //n/m为奇数n/2m为奇数  f(m) - f(m - 1) * f(n mod m)
                //n mod m为奇数
                if (n % m % 2 == 1) 
                {
                    if (m == 2 && m - n % m == 1) return F(m) - 1;
                    else return F(m) - F(m - n % m) - 1;
                }else 
                {
                    //n mod m为偶数
                    //判断f(m - n mod m)是否为0
                    return F(m - n % m) - 1;
                }
            }
        }
    }
    
    //判断是否读到空行
    static boolean canRead() throws Exception{
        String line = cin.readLine();
        if (line == null || line.length() == 0) return false;
        String[] ss = line.split(" ");
        n = Long.valueOf(ss[0]);
        m = Long.valueOf(ss[1]);
        p = Long.valueOf(ss[2]);
        return true;
    }
    
    public static void main(String[] args) throws Exception {
        while (canRead()) {
            //[f(n + 2) - 1] mod f(m) 
            System.out.println((G(n + 2, m) % p + p) % p);
        }
    }
    
}

image-20230203182107668

例题4AcWing 1171. 距离tarjan 离线LCA

题目链接AcWing 1171. 距离

分析

思路

1、存储所有的查询以每个起始点为集合来存储对应的目标点以及对应的序号。

2、维护一个dist数组来存储每个节点到节点1(默认设置其为根节点)的距离使用dfs来进行求取。

3、维护一个并查集在回溯的过程中去维护并查集目的是能够去构建当前的指定子树的祖先结点同时在回溯的过程中去遍历以当前u结点初始节点出发的集合遍历每一个目标节点若是该目标节点已经在此之前回溯完成了那么此时可以进行两个结点最小路径的计算起始结点距离根节点距离 + 目标节点距离根节点距离 - 2 * 初始目标节点的祖先结点距离根节点距离 = 两个结点最短路径。

看下这个过程起始点为蓝色目标点为红色

image-20230204010445097

当我们去回溯到红色点时由于之前查询节点添加了两个方向所以可以查到红色的目标值为蓝色点而此时蓝色点已经回溯过了为2此时就可以去找到蓝色的祖先结点接着求得两个点的最小路径了。

image-20230204010557706

实际上对于祖先结点的定位查找我们是根据在回溯的过程中去维护一个并查集这样我们就能够在回溯时找到祖先节点从而求得最小距离起始结点距离根节点距离 + 目标节点距离根节点距离 - 2 * 初始目标节点的祖先结点距离根节点距离 = 两个结点最短路径

image-20230204010926257

题解思路tarjan 离线LCA

复杂度分析时间复杂度O(m+n)空间复杂度O(n)

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

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 200010, M = N * 2;
    //读入结点
    static int n, m;
    //单链表式的邻接表
    static int[] e = new int[M], ne = new int[M], h = new int[N], w = new int[M];
    static int idx;
    //维护查询集合
    static ArrayList<int[]>[] queries = new ArrayList[N];
    //dist记录每个节点距离根节点1的长度
    //p维护并查集
    //res维护查询结果
    static int[] dist = new int[N], p = new int[N], res = new int[N];
    //记录在tarjan中是否进行访问过节点  1表示已访问2表示已回溯完成
    static int[] st = new int[N];
    
    //添加节点到邻接表中
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    //并查集查找祖先结点
    static int find(int u) {
        if (p[u] != u) p[u] = find(p[u]);
        return p[u];
    }
    
    //dfs
    static void dfs(int u, int fa) {
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j != fa) {
                //记录距离注意w[i]这里是在单链表中存储的值
                dist[j] = dist[u] + w[i];
                dfs(j, u);
            }
        }
    }
    
    //tarjan离线计算
    static void tarjan(int u) {
        st[u] = 1;//1表示已经访问过了
        //遍历单链表
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            //表示还没有访问过
            if (st[j] == 0) {
                tarjan(j);
                //维护并查集节点
                p[j] = u;
            }
        }
        //访问所有的查询节点
        ArrayList<int[]> queriesList = queries[u];
        if (queriesList != null) {
            for (int[] query: queriesList) {
                //y表示目标点id表示查询的序号用于存储结果值
                int y = query[0], id = query[1];
                if (st[y] == 2) {
                    //通过并查集找到当前y的祖先结点
                    int anc = find(y);
                    res[id] = dist[y] + dist[u] - 2 * dist[anc];
                }
            }
        }
        //整体回溯完成设置st状态
        st[u] = 2;
    }
    
    public static void main(String[] args) throws Exception{
        String[] ss = cin.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        //初始化所有单链表的头结点
        Arrays.fill(h,-1);
        
        //读入初始节点与目标节点
        for (int i = 1; i < n; i ++ ) {
            ss = cin.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            int c = Integer.parseInt(ss[2]);
            add(a, b, c);
            add(b, a, c);
        }
        
        //读入查询节点的最小路径
        for (int i = 0; i < m; i ++) {
            ss = cin.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            if (a == b) continue;
            if (queries[a] == null) queries[a] = new ArrayList<>();
            if (queries[b] == null) queries[b] = new ArrayList<>();
            //添加对应查询集合的目标节点与对应的查询次序
            queries[a].add(new int[]{b, i});
            queries[b].add(new int[]{a, i});
        }
        
        //进行dfs来取得每一个节点距离根节点1的长度
        dfs(1, -1);
        
        //初始化并查集
        for (int i = 1; i <= n; i ++) p[i] = i;
        
        //进行离线计算
        tarjan(1);
        
        //打印所有结果
        for (int i = 0; i < m; i ++) {
            System.out.println(res[i]);
        }
        
    }
    
}

image-20230204011033455

习题1AcWing 1206. 剪格子困难DFS+并查集判断连通性

题目链接AcWing 1206. 剪格子

分析

需要着重注意的几个问题

①判断只有两个连通块情况。【可能会出现多个连通块】

image-20230204163350312

②不仅仅只搜一笔的连通块。【大多数的题解都是搜一笔】

③包含两笔及多笔情况。

image-20230204163052667

  • dfs基本都是一笔画问题对于二笔画就没有什么用。

整个DFS过程中包含一些函数该DFS是多笔画的

  • checkConnection判断连通性需要访问数组、并查集根据传入进来的k确定还没有被访问的数接着去遍历整个数组对每个结点进行上下左右尝试访问这个过程中去使用并查集来维护连通性。
  • checkExist检测是否访问过该条路径需要一个hashset将访问过的节点集合进行排序并通过一定规则计算得到一个数vv = v * p + x + 1p为133或者13331。

题解并查集+DFS判断连通性

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

class Main {
    
    static final Scanner cin = new Scanner(System.in);
    static final int N = 12, INF = Integer.MAX_VALUE;
    //整个格子
    static int[][] g = new int[N][N];
    //n, m读入格子的宽高
    //sum所有格子的总和
    static int n, m, sum, res = INF;
    //已经记录的格子真正来去进行搜索的格子记录
    static Pair[] records = new Pair[N * N];
    //表示当前已经访问过该格子
    static boolean[][] vt = new boolean[N][N];
    //并查集检测是否联通
    static int[] p = new int[N * N];
    //用于检测路径是否已访问过
    static Set<Long> hasVtPath = new HashSet<Long>();
    //上下左右四个方向
    static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    
    //用于记录坐标
    static class Pair implements Comparable<Pair> {
        public int x, y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        //根据在二维表中的xy左边进行排序
        @Override
        public int compareTo(Pair p) {
            return this.x == p.x ? this.y - p.y : this.x - p.x;
        }
        
        @Override
        public boolean equals(Object o) {
            if (o == null) return false;
            Pair p = (Pair)o;
            if (this.x == p.x && this.y == p.y) return true;
            return false;
        }
    }
    
    //测试剩余未访问过的节点是否连通
    public static boolean checkConnection(int k) {
        //初始化并查集
        for (int i = 0; i < n *m ; i ++) 
            p[i] = i;
        //计算剩余未访问过的节点数量
        int cnt = n * m - k;
        
        //遍历整个矩阵
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++) {
                //若是当前没有访问过找没有访问的节点
                if (!vt[i][j]) {
                    //遍历四个方向
                    for (int d = 0; d < 4; d ++) {
                        int x = dx[d] + i, y = dy[d] + j;
                        //若是越界或者已经访问过那么直接结束
                        if (x < 0 || y < 0 || x >= n || y >= m || vt[x][y]) continue;
                        //开始查找临近点是否有并查集
                        int p1 = find(i * m + j), p2 = find(x * m + y);
                        //若是两个点当前没有连通
                        if (p1 != p2) {
                            //进行连通
                            p[p1] = p2;
                            cnt--;
                        }
                    }
                }
            }
        }
        //若是最终元素数量为1此时表示剩余未访问过的元素是连通的
        if (cnt == 1) return true;
        return false;
    }
    
    //并查集查询
    public static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    
    
    //检测records这条路径再此之前是否有访问过
    public static boolean checkExist(int k) {
        //拷贝一份来去进行排序后进行组合数字
        Pair[] kb = records.clone();
        //对访问路径进行排序
        Arrays.sort(kb, 0, k);
        //记录x值
        long x = 0;
        final int p = 133;//容错性比较高的一个值
        for (int i = 0; i < k; i ++) {
            x = x * p + kb[i].x + 1;//防止出现0的情况
            x = x * p + kb[i].y + 1;
        }
        //判断是否已经访问过
        if (hasVtPath.contains(x)) return true;
        //没有访问过存储下返回
        hasVtPath.add(x);
        return false;
    }
    
    //深搜
    //k表示目前的记录数s表示已经记录格子的综合
    public static void dfs(int k, int s) {
        //当前值已经满足题目要求
        if (s == sum / 2) {
            //测试目前分成的两个部分是否连通借助并查集来对没有访问过的节点进行测试连通
            if (checkConnection(k)) {
                res = Math.min(res, k);
            }
            return;
        }
        
        //遍历现有已经添加到记录中的节点各个结点的上下左右去尝试将符合条件的一些节点添加到points中
        //对应record每次赋值也仅仅只是为了在进行checkExist时进行检测是否之前已访问过了
        List<Pair> points = new ArrayList<Pair>();
        for (int i = 0; i < k; i ++) {
            //获取到当前已经访问过的节点
            int x = records[i].x, y = records[i].y;
            //尝试去走每一个已访问过节点的上下左右节点
            for (int d = 0; d < 4; d ++) {
                //目标坐标
                int a = x + dx[d], b = y + dy[d];
                //若是越界或者已访问过直接忽略
                if (a < 0 || b < 0 || a >= n || b >= m || vt[a][b]) continue;
                //临时添加下当前节点
                records[k] = new Pair(a, b);
                //剪枝若是当前k的值是在结果数量下或者是否之前已访问过该节点
                if (k + 1 < res && !checkExist(k + 1)) {
                    //添加到收集点中去
                    points.add(new Pair(a, b));
                }
            }
        }
        //优化搜索优先去访问靠后的节点
        Collections.sort(points);
        for (int i = points.size() - 1; i >= 0; i --) {
            //去除相同的节点情况
            if (i == 0 || !points.get(i).equals(points.get(i - 1))) {
                //更新最新当前访问的节点
                records[k] = points.get(i);
                //尝试去进行访问该节点
                int x = records[k].x, y = records[k].y;
                //设置现场
                vt[x][y] = true;
                dfs(k + 1, s + g[x][y]);
                //恢复现场
                vt[x][y] = false;
            }
        } 
        
    }

    
    public static void main(String[] args) {
        m = cin.nextInt();
        n = cin.nextInt();
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                g[i][j] = cin.nextInt();
                sum += g[i][j];
            }
        }
        
        //若是总和是偶数才有可能进行划分
        if (sum % 2 == 0) {
            //添加起始点
            records[0] = new Pair(0, 0);
            //表示已经访问过初始点
            vt[0][0] = true;
            //开始进行深搜
            dfs (1, g[0][0]);
        }
        
        System.out.println(res == INF ? 0 : res);
    }
    
}

image-20230204161955232

习题2AcWing 523. 组合数问题数论+前缀和

题目链接AcWing 523. 组合数问题

分析

题目给出了一个组合公式实际上给定n与m让我们求得这个C。

image-20230204195146391

看下数据量n与m是两千询问组数为10000组并且题目说让你求得求得一个范围中(i,j)满足k的倍数数量。仅仅只是说让你计算这个C组合数及组数以及让你取统计这个范围中的数就是2000*2000*10000就直接超时了。

我们看下有哪些可以优化的点

①计算 C n m C_n^m Cnm​原本需要O(n)时间通过组合恒等式可以通过前几个数进行递推此时即为O(1)时间。

  • 初始话计算机出所有 C n m C_n^m Cnm​ 需要O(n2)复杂度这是计算所有情况。

通过下面的一个恒等式我们可以将对应的组合数使用一个二维数组来存储起来计算c[n][m] = c[n - 1][m] + c[n - 1][m - 1]。

image-20230204200138029

推导过程如下所示数学一分钟 计数原理 组合数性质证明 孟孟数学老师

image-20230204200315447

②计算组合 C n m C_n^m Cnm​中多少个能够mod k = 0的情况原本需要O(n)借助前缀和得到一组统计情况也只需要O(1)。

  • 计算出所有范围内指定的nm的C组合数同样需要O(n2)

我们通过一个二维表来统计出所有关于总共n个选取m个的组合数

image-20230204200605240

我们可以使用二维前缀和来进行快速得到对应n、m的满足条件组合数的数量。

每次处理一个查询时间复杂度为O(1)。

题解数论+前缀和

复杂度分析时间复杂度O(n2)空间复杂度O(n2)

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

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 2010;
    static int k;
    //计算Cij的值%k取模之后的
    static int[][] c = new int[N][N];
    //前缀和数组
    static int[][] s = new int[N][N];
    
    
    public static void main(String[] args)throws Exception {
        String[] ss = cin.readLine().split(" ");
        int t = Integer.parseInt(ss[0]);
        k = Integer.parseInt(ss[1]);
        
        //预处理
        for (int i = 0; i < N; i ++) {
            for (int j  = 0; j <= i; j ++) {  //注意这里是j<=i仅仅只对三角区域进行处理
                //选0中必然是
                if (j == 0) c[i][j] = 1 % k;
                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k; //计算对k取模的值若是能够整除则为0
                
                //如果当前整除则为1表示该cij符合题目要找的k倍数情况方便之后前缀和进行计算
                if (c[i][j] == 0)
                    s[i][j] = 1;//若是能够被整除设置s[i][j]为1默认是0
            }
        }
        
        //开始进行计算前缀和
        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < N; j ++) {
                //前缀和公式s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + c[i][j]
                //c[i][j]是在之前预处理时就进行设置了初始值默认为1或者
                //下面的if都是越界条件情况
                if (i != 0) s[i][j] += s[i - 1][j];
                if (j != 0) s[i][j] += s[i][j - 1];
                if (i != 0 && j != 0) s[i][j] -= s[i - 1][j - 1];
            }
        }
        
        //查询
        while (t-- != 0) {
            ss = cin.readLine().split(" ");
            int n = Integer.parseInt(ss[0]);
            int m = Integer.parseInt(ss[1]);
            System.out.println(s[n][m]);
        }
    }
    
}

image-20230204201412200

API

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

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010;
    static int n;
    static HashSet<Integer> set = new HashSet<>();
    
    public static void main(String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine());
        while (n-- != 0) {
            String[] ss = cin.readLine().split(" ");
            String type = ss[0];
            int num = Integer.parseInt(ss[1]);
            if ("I".equals(type)) {
                set.add(num);
            }else {
                System.out.println(set.contains(num) ? "Yes" : "No");
            }
        }
    }
    
}

image-20230204202428939

习题3AcWing 840. 模拟散列表拉链法开放地址法

题目链接AcWing 840. 模拟散列表

题解1拉链法

复杂度分析

  • 时间复杂度query()为O(1)insert(1)
  • 空间复杂度O(n)
import java.util.*;
import java.io.*;

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = (int)(1e5 + 3);
    static int n;
    //开一个槽邻接表写法单列表
    static int[] e = new int[N], ne = new int[N], h = new int[N];
    static int idx;
    
    public static void insert(int num) {
        int k = (num % N + N) % N;
        //创建一个节点
        e[idx] = num;
        ne[idx] = h[k];
        //插入到对应的插槽中
        h[k] = idx++;
    }
    
    public static boolean query(int num) {
        int k = (num % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i]) {
            if (e[i] == num) return true;
        }
        return false;
    }
    
    public static void main(String[] args) throws Exception{
        n = Integer.parseInt(cin.readLine());
        //初始化槽
        Arrays.fill(h, -1);
        
        while (n-- != 0) {
            String[] ss = cin.readLine().split(" ");
            String type = ss[0];
            int num = Integer.parseInt(ss[1]);
            if ("I".equals(type)) {
                insert(num);
            }else {
                System.out.println(query(num) ? "Yes" : "No");
            }
        }
    }
    
}

image-20230204203258404

题解2开放寻址法

复杂度分析时间复杂度O(n)空间复杂度O(1)

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

class Main {
    
    static final BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    //开放寻址法N一般开数据范围的2到3倍。大于数据范围的第一个质数
    //规定空指针范围为最大
    static final int N = (int)(2e5 + 3), Nll = Integer.MAX_VALUE; 
    static int[] h = new int[N];
    
    //寻找到一个开放的空间位置
    public static int find(int x) {
        int k = (x % N + N) % N;
        //寻找到一个为空的位置 或者说找到目标x的位置结束
        while (h[k] != Nll && h[k] != x) {
            //地址进行+1
            k++;
            if (k == N) k = 0;
        }
        return k;
    }
    
    
    
    public static void main(String[] args) throws Exception{
        int n = Integer.parseInt(cin.readLine());
        //初始化槽
        Arrays.fill(h, Nll);
        
        while (n-- != 0) {
            String[] ss = cin.readLine().split(" ");
            String type = ss[0];
            int num = Integer.parseInt(ss[1]);
            if ("I".equals(type)) {
                //找到对应位置为NILL的进行插入
                h[find(num)] = num;
            }else {
                //若是对应的空间位置为NLL表示没有找到
                System.out.println(h[find(num)] != Nll? "Yes" : "No");
            }
        }
    }
    
}

image-20230204204735332

参考文章

[1]. AcWing 1242. 修改数组AcWing 1242. 修改数组——并查集的简单应用、AcWing 1242. 修改数组蓝桥杯C++ AB组辅导课

[2]. AcWing 1234. 倍数问题AcWing 1234. 倍数问题Java 背包解法 Or 余数枚举 、AcWing 1234. 倍数问题(三维普通WA代码+三维优化AC+二维AC代码) 、AcWing 1234. 倍数问题蓝桥杯C++ AB组辅导课

[3]. AcWing 1213. 斐波那契AcWing 1213. 斐波那契、AcWing 1213. 斐波那契、AcWing 1213. 斐波那契蓝桥杯C++ AB组辅导课

[4]. AcWing 1171. 距离AcWing 1171. 距离、AcWing 1171. 距离

[5]. AcWing 1206. 剪格子AcWing 1206. 剪格子(含AC注释代码)、AcWing 1206. 剪格子、AcWing 1206. 剪格子(含AC注释代码) 、AcWing 1206. 剪格子蓝桥杯C++ AB组辅导课

[6]. AcWing 523. 组合数问题AcWing 523. 组合数问题、AcWing 523. 组合数问题–前缀和+组合数、AcWing 523. 组合数问题蓝桥杯C++ AB组辅导课

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：【C++之类和对象】初始化列表，C++11初始化新玩法，static成员，友元

下一篇：3. Pytorch中数据预处理和加载

“AcWing蓝桥杯AB组辅导课10、疑难杂题” 的相关文章

目标跟踪心得篇五：MOT数据集标注、DarkLabel不能自动跟踪解决方案1年前 (2023-02-02)
Ubuntu下的LGT8F328P MiniEVB Arduino开发和烧录环境1年前 (2023-02-02)
proteus常用元件图示和名称(持续更新...)_proteus元件库对照表图片1年前 (2023-02-02)
0xcdcdcdcd异常值引发C++程序崩溃问题的详细分析1年前 (2023-02-02)
学习笔记——redis中的数据类型（List、Set、Hash）1年前 (2023-02-02)
真题解析 | 2022数模美赛C题：股票投资策略1年前 (2023-02-02)
【C++ 数据结构：链表】二刷LeetCode707设计链表1年前 (2023-02-02)
在外打工好久不回老家，用python为家里贴上新年春联1年前 (2023-02-02)
Redis缓存的主要异常及解决方案1年前 (2023-02-02)
23年 车辆检测+车距检测+行人检测+车辆识别+车距预测（附yolo v5最新版源码）1年前 (2023-02-02)

阿里云国际版