蓝桥杯总结

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

蓝桥杯总结

  1. 05-26

    • 数据结构

      今天学习到了两种特殊的数据结构哈希表的链表型实现和哈希集合的链表型实现这两种实现使哈希表和哈希集合有了顺序先插入的在前后插入的在后在之前的学习中散列表是无序的通过今天的学习很好的补充了有序这一块。

      复习了数据结构deque这种数据结构既能当栈用又能队列使用而且可以用数组实现和用链表实现两种方式非常的便捷

      package Test05_26;

import java.util.LinkedHashMap;
import java.util.LinkedHashSet;

public class Test1 {
    public static void main(String[] args) {
        LinkedHashMap linkedHashMap = new LinkedHashMap();
        linkedHashMap.put(1, 100);
        linkedHashMap.put(2, 10);
        linkedHashMap.put(999, 1000);
        System.out.println(linkedHashMap);
        linkedHashMap.remove(2);
        System.out.println(linkedHashMap);
        LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add(5);
        linkedHashSet.add(4);
        System.out.println(linkedHashMap);
        System.out.println(linkedHashSet);
    }
}

    • 心得体会

      做题第一步是要先把题目先看懂然后看数据的规模估计出需要什么样的时间复杂度才能完美通过评测然后设计出合适的算法若没有思路就寻求模拟-暴力的算法来解决算法尽可能要用到对应的数据结构才能发挥出最大效力

      每做一部分就测试一部分代码保证整个过程不出大的差错

    • 题目

      1. 左移右移

        数据规模: 1 <= N, M <= 2e5

        时间复杂度: O(N) ~ O(N*logN)

        package Test05_26;

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

/**
 * 左移-右移将数据分为三个部分最左边的前置-栈存储中间-顺序存储最右边的后置-顺序存储这里用哈希集合记录需要左移或右移的元素便于判断存储的方式
 * 注意:这里可能会对同一个数多次执行操作这里以最后一次操作为准
 */
public class Test2 {
    public static void main(String[] args) throws IOException {
        //这里用数组模拟栈
        Deque<Integer> left = new ArrayDeque<>();
        //左边和右边
        List<Integer>  right = new ArrayList<>();
        LinkedHashMap<Integer, Character> map = new LinkedHashMap<>();
        //输入输出
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        //这里可以替换成PrintWriter
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = in.readLine().split(" ");
        //变量
        int N = Integer.parseInt(s[0]), M = Integer.parseInt(s[1]);
        //处理以最后一次操作为准
        for (int i = 0; i < M; i++) {
            String[] line = in.readLine().split(" ");
            char c = line[0].charAt(0);
            int num = Integer.parseInt(line[1]);
            //判断是否存在对于该数的操作
            if(map.containsKey(num)) map.remove(num);
            map.put(num, c);
        }
        //遍历map根据entry中对数的操作类型将数分别放入栈中或者list中
        for(Map.Entry<Integer, Character> entry : map.entrySet()){
            int num = entry.getKey();
            char c = entry.getValue();
            if(c == 'L'){
                left.push(num);
            }else{
                right.add(num);
            }
        }
        //左部分
        while(!left.isEmpty()){
            out.write(left.pop() + " ");
        }
        //中间部分
        for (int i = 1; i <= N; i++) {
            if(!map.containsKey(i)){
                out.write(i + " ");
            }
        }
        //右边部分
        for(int i : right){
            out.write(i + " ");
        }
        //关键代码out.flush()
        out.flush();
        out.close();
        in.close();
    }
}

      2. 窗口(评测通过百分之10结果错误)

        数据规模: 1 <= N, M <= 256, 1 <= k <= 10000

        时间复杂度: O(N * logN)

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

public class Test3 {
    /**
     * 模拟题-窗口
     * 时间复杂度O(N) ~ O(N * logN)
     * 思路:
     * 1.输入我们使用BufferedReader来输入数据
     * 2.处理
     * 我们使用类来储存窗口的信息这里需要带一个额外的信息权重代表窗口所在的层次若窗口层次越高则权值越高这里使用max来保存当前最大的权值每次进行新的操作除了close外
     * 最大的权值都会+1然后将这个最大的权值作为新的层次对操作进行初始化待所有操作完毕后按权值大小对所有窗口进行降序排序
     * 3.渲染
     * 我们首先初始化一个矩阵view代表视图层以及一个vis代表试图对应的像素占用情况顺序遍历排序后的list根据window与view是否有交集决定是否要进行渲染
     * 在进行渲染时首先要求出交集的起始位置终止位置在横纵两个方向上这里分别用t,d,l,r表示然后我们扫描这个范围首先看该像素点是否已渲染数据若没有则根据要求进行渲染看是否是四个顶点是否是四条边或是中间的空格
     * 4.输出
     * 我们使用PrintWriter进行输出这里扫描view矩阵即可进行顺序输出注意每扫描完一行要跳到下一行
     * 关键:不要忘记用flush数据清空缓存然后关闭
     * @param args
     */
    public static void main(String[] args) throws IOException {
        new Test3().run();
    }
    Map<Integer, Window> map = new HashMap<>();

    void move(int pid ,int v, int h, int w){
        Window window = map.get(pid);
        window.left += h;
        window.top += v;
        window.w = w;
        map.put(pid, window);
    }

    void resize(int pid, int hgt, int wdh, int w){
        Window window = map.get(pid);
        window.hgt = hgt;
        window.wdh = wdh;
        window.w = w;
        map.put(pid, window);
    }

    void close(int pid){
        map.remove(pid);
    }

    void active(int pid, int w){
        Window window = map.get(pid);
        window.w = w;
        map.put(pid, window);
    }
    void run() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter printWriter = new PrintWriter(new OutputStreamWriter(System.out));

        String[] s = bufferedReader.readLine().split(" ");
        int N = Integer.parseInt(s[0]), M = Integer.parseInt(s[1]);
        char[][] view = new char[N][M];
        int K = Integer.parseInt(bufferedReader.readLine());
        //存储当前最大权重
        int max = 0;
        for (int i = 0; i < K; i++) {
            String[] line = bufferedReader.readLine().split(" ");
            String c = line[0];
            int pid = Integer.parseInt(line[1]);
            if(c.equals("new")){
                Window window = new Window(pid ,Integer.parseInt(line[2]), Integer.parseInt(line[3]), Integer.parseInt(line[4]), Integer.parseInt(line[5]), ++max);
                map.put(pid, window);
            }else if(c.equals("move")){
                move(pid, Integer.parseInt(line[2]), Integer.parseInt(line[3]), ++max);
            }else if(c.equals("resize")){
                resize(pid, Integer.parseInt(line[2]), Integer.parseInt(line[3]), ++max);
            }else if(c.equals("close")){
                close(pid);
            }else if(c.equals("active")){
                active(pid, ++max);
            }
        }
        //将map中的元素加入list中
        List<Window> list = new ArrayList<>();
        for(Map.Entry<Integer, Window> entry : map.entrySet()){
            list.add(entry.getValue());
        }
        //按权值大小对窗口进行降序排列
        Collections.sort(list, (o1, o2) -> o2.w - o1.w);
        //渲染
        boolean[][] vis = new boolean[N][M];
        //初始化
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                view[i][j] = '.';
            }
        }

        for (int i = 0; i < list.size(); i++) {
            Window window = list.get(i);
            int top = window.top, left = window.left, height = window.hgt, width = window.wdh;
            int bottom = top + height - 1, right = left + width - 1;
            if(right < 0 || left >= M || bottom < 0 || top >= N){
                break;
            }
            //求交集
            int l = left, r = right, t = top, b = bottom;
            if(left < 0) l = 0;
            if(right >= M) r = M - 1;
            if(top < 0) t = 0;
            if(bottom >= N) b = N - 1;


            for(int row = t; row <= b; row++){
                for(int col = l; col <= r; col++){
                    if(!vis[row][col]){
                        vis[row][col] = true;
                        boolean flag = false;
                        if(row == top || row == bottom){
                            flag = true;
                            //若为第一行或最后一行就为-
                            view[row][col] = '-';
                        }

                        if(col == left || col == right){
                            flag = true;
                            view[row][col] = '|';
                            //若是边角的四个点就为+
                            if(row == top || row == bottom) view[row][col] = '+';
                        }
                        //其他部分为空
                        if(!flag){
                            view[row][col] = ' ';
                        }
                    }
                }
            }

        }

        //输出
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                printWriter.print(view[i][j]);
            }
            printWriter.println();
        }
        printWriter.flush();
        printWriter.close();
        bufferedReader.close();


    }

    class Window{
        int pid, top, left, hgt, wdh, w;
        public Window(int pid, int top, int left, int hgt, int wdh, int w) {
            this.top = top;
            this.left = left;
            this.hgt = hgt;
            this.wdh = wdh;
            this.w = w;
            this.pid = pid;
        }

        @Override
        public String toString() {
            return "Window{" +
                    "pid=" + pid +
                    ", top=" + top +
                    ", left=" + left +
                    ", hgt=" + hgt +
                    ", wdh=" + wdh +
                    ", w=" + w +
                    '}';
        }
    }
}

  2. 05-27

  3. 窗口

    数据规模 1 <= N, M <= 10

    package demo05_27;

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

public class Test1 {
    final String F = "IGNORED";
    int top = 0, left = 0, bottom = 1439, right = 2559;
    public static void main(String[] args) {
        new Test1().run();
    }

    void run(){
        //输入
        Scanner sc = new Scanner(System.in);
        PrintWriter printWriter = new PrintWriter(System.out);
        int N = sc.nextInt(), M = sc.nextInt();
        int max = 0;
        for (int i = 0; i < N; i++) {
            int pid = i + 1;
            Window window = new Window(pid, sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(), ++max);
            map.put(pid, window);
        }
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < M; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            queue.offer(new int[] {x, y});
        }
        //处理
        List<Window> windows = new ArrayList<>();
        for(Map.Entry<Integer, Window> entry : map.entrySet()){
            windows.add(entry.getValue());
        }
        Collections.sort(windows, (o1, o2) -> o2.w - o1.w);

        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];
            boolean flag = false;
            for(int i = 0; i < N; i++){
                Window window = windows.get(i);
                int t = window.y1, b = window.y2, l = window.x1, r = window.x2;
                //若在范围内
                if(x >= l && x <= r && y >= t && y <= b){
                    flag = true;
                    window.w = ++max;
                    windows.set(i, window);
                    printWriter.println(window.pid);
                    //重新排序
                    Collections.sort(windows, (o1, o2) -> o2.w - o1.w);
                    break;
                }
            }
            if(!flag){
                printWriter.println(F);
            }
        }

        printWriter.flush();
        printWriter.close();
        sc.close();
    }

    Map<Integer, Window> map = new HashMap<>();

    class Window{
        int pid;
        int x1, y1, x2, y2, w;

        public Window(int pid, int x1, int y1, int x2, int y2, int w) {
            this.pid = pid;
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
            this.w = w;
        }

        @Override
        public String toString() {
            return "Window{" +
                    "pid=" + pid +
                    ", x1=" + x1 +
                    ", y1=" + y1 +
                    ", x2=" + x2 +
                    ", y2=" + y2 +
                    ", w=" + w +
                    '}';
        }
    }
}

05-28

  1. 题目

    1. 李白打酒加强版

      1. 分析

        数据规模: 1 <= N, M <= 100 很宽松

        题型动态规划参数4 矩阵3元

        package demo05_28;

import java.util.Scanner;

public class Test1 {
    public static void main(String[] args) {
        new Test1().run();
    }
    int mod = (int) (1e9 + 7);

    /**
     * 动态规划N店M花, k酒count种四个参数, 3维矩阵因为要把酒喝完所有 k == M
     * 已知最后一次遇到花因此dp[i][j - 1][1] = 1
     * 边界条件:dp[0][0][2] = 1, dp[0][1][1] = 1, dp[0][2][0] = 1
     * 状态转移方程划分根据酒为奇数还是偶数当酒为奇数上次肯定遇到花若为偶数可能遇到花也可能遇到店
     * 已知最后一次遇到花因此目标为dp[N][M - 1][1]
     */
    int[][][] dp = new int[110][110][110];
    void run(){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();
        //边界条件
        dp[0][0][2] = 1;
        dp[0][1][1] = 1;
        dp[0][2][0] = 1;
        //状态转移
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                for (int k = 0; k <= M; k++) {
                    if(k % 2 == 0){
                        if(i > 0) dp[i][j][k] += dp[i - 1][j][k / 2];//遇店
                        if(j > 0) dp[i][j][k] += dp[i][j - 1][k + 1];//遇到花
                    }else{
                        if(j > 0) dp[i][j][k] += dp[i][j - 1][k + 1];
                    }
                    dp[i][j][k] %= mod;
                }
            }
        }
        System.out.println(dp[N][M - 1][1]);
        sc.close();
    }
}

        总结

        动态规划的矩阵元数 = 参数个数 - 1

        动态规划的边界条件可能有多个

        动态规划的目标条件隐藏在题目中

    2. 2022

      1. **分析**数据规模 N = 2022

        **题型**动态规划参数4

        **TIPS**该题的数据规模很大需要用long类型的dp数组

        public class Test2 {
    public static void main(String[] args) {
        new Test2().run();
    }

    /**
     * 本题同样是动态规划从数字1~i中选j个数和为k的方案数因此用三维数组
     *边界条件dp[0][0][0] = 1,意思是都不选的话方案数为0
     * 状态转移方程:
     * 选i dp[i][j][k] = dp[i-1][j - 1][k - i],意思是若选当前数i的花那么方案数就等于从剩余的i-1个数中选j-1个数使之和为k-i
     * 不选i dp[i][j][k] += dp[i-1][j][k]
     * 两种情况累加就是dp[i][j][k]
     * 目标: dp[2022][10][2022]
     */
    int N = 2022;
    long[][][] dp = new long[N + 10][20][N + 10];
    void run(){
        //边界条件
        dp[0][0][0] = 1;
        //状态转移
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= 10; j++) {
                for (int k = 0; k <= N; k++) {
                    if(j - 1 >= 0 && k - i >= 0){
                        //选i等价于从剩余的i-1个数中选j-1个使得和为k-i的个数
                        dp[i][j][k] = dp[i - 1][j - 1][k - i];
                    }
                    //不选i,等价于从剩余的i-1个数中选j个使得和为k
                    dp[i][j][k] += dp[i - 1][j][k];
                }
            }
        }
        //目标
        System.out.println(dp[N][10][N]);
    }
}

    3. 最大数字

      1. 分析

        数据规模 1 <= N <= 10^17, 0 <= A, B <= 100

        时间复杂度: O(logN)

        import java.util.Scanner;

public class Test3 {
    public static void main(String[] args) {
        new Test3().run();
    }

    /**
     * 思路-贪心我们优先处理最高位首先我们看该数是否位9若是则跳过再看AB是不是都大于0若是这里我们最高位到0还是到10哪边近哪边近就执行哪一个
     * 然后次数-1, A对应+1B对应-1
     */
    void run(){
        Scanner sc = new Scanner(System.in);
        char[] nums = sc.next().toCharArray();
        int A = sc.nextInt(), B = sc.nextInt(), n = nums.length;
        for (int i = 0; i < n; i++) {
            if(nums[i] == '9') continue;
            //若A,B都不为0
            int num = nums[i] - '0';
            //A操作和B操作的花费
            int a = 9 - num, b = num + 1;
            //若两种操作都可以就选操作数最少的
            if(A >= a && B >= b){
                if(a <= b){
                    A -= a;
                    nums[i] = '9';
                }else{
                    B -= b;
                    nums[i] = '9';
                }
            }
            //若A够
            else if(A >= a){
                A -= a;
                nums[i] = '9';
            }
            //若B够
            else if(B >= b){
                B -= b;
                nums[i] = '9';
            }

            //这里若B不够就不用考虑若A > 0则能时该数变大
            else if(A > 0){
                nums[i] = (char)('0' + num + A);
                A = 0;
            }
        }
        System.out.println(new String(nums));
        sc.close();
    }
}

    4. 斐波那契与7

      1. **分析:**首先斐波那契数列就非常特殊然后可以这个数又非常大因此本题是一道找规律的题

        //测试代码
public class Test4 {
    public static void main(String[] args) {
        new Test4().run();
    }
    long[] arr = new long[80];
    int[] idx = new int[80];
    void run(){
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 2;
        recur(3);
        for (int i = 0; i < 80; i++) {
            idx[i] = i + 1;
        }
        int count = 0;
        for (int i = 0; i < 80; i++) {
            if(arr[i] % 10 == 7) {
                count++;
                System.out.println("idx :" + (i + 1) + " num : " + arr[i] + " count : " + count);
            }
        }
        System.out.println(count);
    }
    void recur(int a){
        if(a == 80) return;
        arr[a] = arr[a - 1] + arr[a - 2];
        recur(a + 1);
    }
}
//解题代码
public class Test5 {
    public static void main(String[] args) {
        long ans = 0, num = 202202011200l;
        ans += num / 60 * 8;
        System.out.println(ans);
        //System.out.println(num % 60);
    }
}

    5. 好数之和

      1. 分析

        数据规模:1 <= N <= 10^9

        **思路:**暴力枚举肯定不实际这里需要直接生成然后看数是否再left和right之间以及是否重复然后累加到ans上

        import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Test1 {
    public static void main(String[] args) {
        new Test1().run();
    }

    /**
     * 生成含2022的数
     * 两种情况: 含2022 不含2022
     *
     */
    void run(){
        Scanner sc = new Scanner(System.in);
        long L = sc.nextLong(), R = sc.nextLong();
        int lLen = (L + "").length(), rLen = (R + "").length();
        //判断
        if(rLen < 3) {
            System.out.println(0);
        }
        if(R == 2022){
            System.out.println(2022);
        }
        if(rLen > 4){
            Set<Long> set = new HashSet<>();
            long ans = 0;
//            if(L <= 2022) ans += 2022;
            int rem = rLen - 4;
//            for (int j = 1; j <= Math.pow(10, rem) - 1; j++) {
//                String s = j + "";
//                for (int i = 0; i <= s.length(); i++) {
//                    //前面后面
//                    int l = i, r = s.length() - i;
//                    String lS = "", rS = "";
//                    if(l > 0){
//                        lS = s.substring(0, l);
//                    }
//                    if(r > 0){
//                        rS = s.substring(l);
//                    }
//                    String numStr = lS + 2022 + rS;
//                    int num = Integer.parseInt(numStr);
//                    if(num >= L && num <= R && !set.contains(num)){
//                        set.add(num);
//                        ans += num;
//                    }
//                }
//            }
            //后面长度
            for(int i = 0; i <= rem; i++){
                //前面长度
                for (int j = 0; j <= rem - i; j++) {
                    //前面数
                    for (int k = 0; k <= Math.pow(10, j) - 1; k++) {
                        //后面数
                        for (int l = 0; l <= Math.pow(10, i) - 1; l++) {
                            long tmp = (long)(2022 * Math.pow(10, j) + k + l * Math.pow(10, 4 + j));
                            if(tmp >= L && tmp <= R && !set.contains(tmp)){
                                ans += tmp;
                                set.add(tmp);
                            }
                        }
                    }
                }
            }
            System.out.println(ans);
        }
        sc.close();
    }
}

5-30

  1. 环境治理

    总结

    ​ 刷题时仔细审题先看题若十分钟内没有思路就直接看题解若看不懂就去bing上搜索题解这里有思路时先要根据时间复杂度决定算法重点是思维的训练

    1. 分析

      数据规模 数据规模: 1 <= n <= 1e2, 0 <= Dij <= 1e5

      时间复杂度O(n^3 * log(Dij * n)) == 1e10

      思路: 使用二分查找-floyd去寻找可行的天数的下限这里使用floyd前先要将原矩阵的灰度复制到tmp中然后根据天数对tmp做数据处理后再使用floyd求和这里check方法是检查该天数是否可行

      import java.util.Scanner;

public class Test2 {
    public static void main(String[] args) {
        new Test2().run();
    }

    /**
     * 稠密图最短路径floyd算法,二分查找最小天数
     * 思路: 数据规模: 1 <= n <= 1e2, 0 <= Dij <= 1e5
     * 时间复杂度: O(n^3 * log(Dij * n)) == 1e10
     */
    int N = 110;
    int[][] g = new int[N][N];
    int[][] b = new int[N][N];
    int[][] tmp = new int[N][N];
    int n, Q;
    void run() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        Q = sc.nextInt();
        //第0个代表灰尘度第一个代表下限
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                b[i][j] = sc.nextInt();
                //将下限复制到tmp上来
                tmp[i][j] = b[i][j];
            }
        }

        //若下限都不能满足则返回-1
        if(floyd() > Q){
            System.out.println(-1);
            return;
        }
        //二分查找
        int left = 0, right = (int) 1e7 + 10;
        while(left < right){
            int mid = left + right >> 1;
            if(!check(mid)){//选小了
                left = mid + 1;
            }else{//大于或等于
                right = mid;
            }
        }
        System.out.println(left);
        sc.close();
    }

    //更新最短路径
    long floyd(){
        long sum = 0;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    tmp[i][j] = Math.min(tmp[i][j], tmp[i][k] + tmp[k][j]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += tmp[i][j];
            }
        }
       // System.out.println(sum);
        return sum;
    }
    //看当前天数是否满足**
    boolean check(int day){
        //首先拷贝到tmp上
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i][j] = g[i][j];
            }
        }
        //已走过的周期,剩余的天数
        int t = day / n, d = day % n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i == j) continue;
                //这里是小于因为从0开始
                if(i < d){
                    //这里需要保底
                    tmp[i][j] = Math.max(b[i][j], tmp[i][j] - t - 1);//额外再多减一
                }else{
                    tmp[i][j] = Math.max(b[i][j], tmp[i][j] - t);
                }
                //无向图双向更新
                tmp[j][i] = tmp[i][j];
            }
        }
        //调用floyd看是否满足要求
//        System.out.println(floyd());
        return floyd() <= Q;
    }
}

  2. 替换字符

    1. 分析

      数据规模 1 <= s, m <= 1e5, 1 <= l <= r <= s, xi != yi

      时间复杂度: O(m * s) == 1e10

      **思路:**暴力算法超时最佳算法是线段树过于复杂未写出来

      import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Test1 {
    /**
     * 暴力
     * @param args
     */
    public static void main(String[] args) throws IOException {
        new Test1().run();
    }

    void run() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        char[] chars = in.readLine().toCharArray();
        int n = Integer.parseInt(in.readLine());;
        for (int i = 0; i < n; i++) {
            String[] lines = in.readLine().split(" ");
            int l = Integer.parseInt(lines[0]), r = Integer.parseInt(lines[1]);
            char c1 = lines[2].charAt(0), c2 = lines[3].charAt(0);
            for (int j = l; j <= r; j++) {
                if(chars[j - 1] == c1){
                    chars[j - 1] = c2;
                }
            }
        }
        System.out.println(new String(chars));
        in.close();
    }
}

05-31

  1. 小蓝做实验

      1. 分析:

        数据规模 1e7 <= x <= 1e8 对于99.99数据 1e3 <= x <= 1e12

        时间复杂度 埃氏筛 O(N * logN), 朴素算法O(N)

        思路: 分类讨论的思想我们将整个数据块分为两部分绝大部分是在1e7 ~ 1e8之间比较稳定因此可以用埃氏筛处理对于少部分情况我们用朴素算法来解决然后将两块的计数加起来就是目标结果

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

public class Test1 {
    /**
     * 思路:埃氏筛 + 素数判断 这里我们对小于等于1e8的都用埃氏筛进行处理大于1e8的则用朴素算法进行判断时间复杂度是log(N)
     * @param args
     */
    public static void main(String[] args) throws IOException {
        new Test1().run();
    }
    int N = (int) (1e8 + 10), n = (int) 1e8;
    boolean[] nums = new boolean[N];
    void run() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("E:\\Java\\lanqiao\\src\\demo05_31\\primes.txt")));
        for (int i = 2; i <= n; i++) {
            if(!nums[i]){
                if((long)i * i <= n){
                    for (long j = i * i; j <= n; j += i) {
                        nums[(int) j] = true;
                    }
                }
            }
        }
        long cnt = 0;
        while(true){
            String s = in.readLine();
            if(s == null) break;
            long num = Long.parseLong(s);
            if(num >= 2 && num <= n){
                if(!nums[(int) num]){
                    cnt++;
                }
            }else if(num > n && isPrime(num)){
                cnt++;
            }
        }
//        for (int i = 2; i <= 100; i++) {
//            System.out.print(nums[i] + " ");
//        }
        System.out.println(cnt);
        in.close();
    }

    boolean isPrime(long num){
        for (long i = 2; i <= num / i; i++) {
            if(num % i == 0) return false;
        }
        return true;
    }
}

  2. 重合次数

    分析模拟题

    import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
       int h = 6, m = 13, s = 22;
        int cnt = 0;
        //这里只考虑分钟秒钟三者归一的要剔除
        while(true){
            if(h == 14 && m == 36 && s == 20){
                break;
            }
            //走动
            s++;
            if(s == 60){
                s = 0;
                m++;
                if(m == 60){
                    m = 0;
                    h++;
                }
            }
            //走动之后看是否满足要求
            if(s == m) cnt++;
        }
        //这里剔除三者重合的情况
        System.out.println(cnt - 8);
    }
}

  3. 取模

    分析

    数据规模 1 <= T <= 1e5, 1 <= n <= 1e9, 2 <= m <= 1e9
    时间复杂度 O(N * T)

    思路我们使用StreamTokenizer能很方便的获取整数小数外层执行t次初始化flag内层执行m次每次对j取模看set中是否含有该模若有就标记为true跳出循环若没有将当前模加入到set中打印输出后清除set中元素

    import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashSet;
import java.util.Set;

public class Test3 implements Runnable{
    public static void main(String[] args) {
        new Test3().run();
    }
    StreamTokenizer tokenizer = new StreamTokenizer(new InputStreamReader(System.in));
    //输入流-将字符串转换为整型,可以在一行
    int nextInt(){
        try {
            tokenizer.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) tokenizer.nval;
    }
    public void run(){
        //set集合存储余数
        Set<Integer> set = new HashSet<>();
        int t = nextInt();
        boolean flag;
        //t行
        for (int i = 0; i < t; i++) {
            //标记为false
            flag = false;
            //获取n和m
            int n = nextInt(), m = nextInt();
            //x, y的范围是1~m
            for (int j = 1; j <= m; j++) {
                //若含有相同余数
                if(set.contains(n % j)){
                    //标记跳出
                    flag = true;
                    break;
                }
                //否则 添加当前余数
                set.add(n % j);
            }
            //根据标记输出
            if(flag){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
            //结束后清楚set便于下一次操作
            set.clear();
        }
    }
}

  4. 分析

    数据规模 1 <= n <= 1e6
    时间复杂度 O(n * 1e5)

    思路暴力枚举:我们先求出当前n的对应二进制的中1的位数然后从2倍枚举到1e5倍看对应二进制的位数是否比当前位小若更新则更新min,最后打印min

    
import java.util.Scanner;

public class Test4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = Integer.toBinaryString(n);
        int min = s.replace("0", "").length();
        for (int i = 2; i <= 100000; i++) {
            String ns = Integer.toBinaryString(i * n).replace("0", "");
            min = Math.min(min, ns.length());
        }
        System.out.println(min);

    }
}

06-01

  1. 六六大顺

    数据规模 1 <= n <= 1e7

    时间复杂度 O(n ^ 2 )

    思路 直接枚举肯定不可能数据太大了这里需要来根据规律来生成目标数在生成的同时用String保存同时用BigInteger累加求值

    
import java.io.IOException;

import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Test2 {
	public static void main(String[] args) {
//		long ans = 0;
//		for(int i = 1; i <= 10; i++) {
//			long tmp = 0;
//			for(int j = 0; j < i; j++) {
//				tmp = tmp * 10 + 6;
//			}
//			
//			ans += tmp * tmp;
//			System.out.println(tmp * tmp + "      " + ans);
//		}
//		System.out.println(ans);
		new Test2().run();
	}
	
	PrintWriter out = new PrintWriter(System.out);
	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		
		String s = "36";
		BigInteger bigInteger = new BigInteger(s);
		int left = 1, right = 3, len = 4;
		for(int i = 2; i <= n; i++) {
			char[] chars = new char[len];
			for(int j = 0; j < len; j++) {
				if(j == left) {
					chars[j] = '3';
				}
				else if(j == right) {
					chars[j] = '6';
				}else if(j < left) {
					chars[j] = '4';
				}else {
					chars[j] = '5';
				}
			}
			BigInteger add = new BigInteger(new String(chars));
			bigInteger = bigInteger.add(add);
			s = new String(chars);
			len += 2;
			left++;
			right += 2;
		}
		
		out.println(bigInteger.toString());
		out.flush();
		out.close();
		sc.close();
	}
}

06-03

  1. 大胖子走迷宫

    数据规模 1 <= n <= 300, 1 <= k <= 1000

    时间复杂度 O(n ^ 2 )

    思路 BFS搜索这里要注意可以在相同位置停下来因此在朝四个方向搜索完后要把原位置再次加入队列中当时间t = k,以及t = 2k时add需要变因此我们在编写check函数时不能写死这里要加上add的值从而实现动态的查询

    import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Test1 {

	public static void main(String[] args) {
		new Test1().run();	
	}
	int N = 310, K = 1010;
	char[][] g = new char[N][N];
	boolean[][] vis = new boolean[N][N];
	int add = 2, n, k, t;
	int[] dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};
	void run() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		t = 0;
		for(int i = 0; i < n; i++) {
			g[i] = sc.next().toCharArray();
		}
		bfs();
		sc.close();
	}
	
	void bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {2, 2});
		vis[2][2] = true;
		while(!queue.isEmpty()) {
			int size = queue.size();
			for(int j = 0; j < size; j++) {
				int[] cur = queue.poll();
				int x = cur[0], y = cur[1];
				//截至条件
				if(x == n - 3 && y == n - 3) {
					System.out.println(t);
					return;
				}
				for(int i = 0; i < 4; i++) {
					int nx = x + dx[i], ny = y + dy[i];
					if(nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny] && check(nx, ny)) {
						vis[nx][ny] = true;
						queue.offer(new int[] {nx, ny});
					}
				}
				//不走
				queue.offer(cur);
			}
			t++;
			if(k == t) add = 1;
			if(2 * k == t) add = 0;
		}
	}
	
	boolean check(int x, int y) {
		if(x - add < 0 || y - add < 0 || x + add >= n || y + add >= n) return false;
		for(int i = x - add; i  <= x + add; i++) {
			for(int j = y - add; j <= y + add; j++) {
				if(g[i][j] == '*') return false;
			}
		}
		return true;
	}

}

  2. 九宫重排

    数据规模 n = 9

    时间复杂度 O(n ^ 2 )

    思路 BFS九宫格的每一个状态作为单独的字符串加入set中。开始时将start加入队列中以当前状态转换成其它状态若是新的状态就将该状态加入set中并将该字符串加入队列中进行下一轮搜索

    import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class Test2 {
	public static void main(String[] args) {
		new Test2().run();
	}
	String start, end;
	int count = 0;
	int[] dir = {-3, 3, -1, 1};
	void run() {
		Scanner sc = new Scanner(System.in);
		start = sc.next();
		end = sc.next();
		bfs();
		
	}
	
	void bfs() {
		Queue<String> queue = new LinkedList<>();
		Set<String> set = new HashSet<>();
		queue.offer(start);
		set.add(start);
		while(!queue.isEmpty()) {
			int size = queue.size();
			while(size-- > 0) {
				String cur = queue.poll();
				//目标条件
				if(cur.equals(end)) {
					System.out.println(count);
					return;
				}
				//空位
				int idx = cur.indexOf(".");
				for(int i = 0; i < 4; i++) {
					int nidx = idx + dir[i];
					if(nidx >= 0 && nidx < 9) {
						//若在同一行或同一列就交换位置
						if(nidx % 3 == idx % 3 || nidx / 3 == idx / 3) {
							char[] curChars = cur.toCharArray();
							curChars[idx] = curChars[nidx];
							curChars[nidx] = '.';
							String s = new String(curChars);
							if(!set.contains(s)) {
								set.add(s);
								queue.offer(s);
							}
						}
					}
				}
			}
			count++;
		}
		System.out.println(-1);
	}
}

  3. 迷宫

    数据规模 n, m <= 2000

    时间复杂度 O(n ^ 4 )

    思路 BFS

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Test3 {
	public static void main(String[] args) {
		new Test3().run();
	}
	int[] dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};
	StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	int nextInt() {
		try {
			streamTokenizer.nextToken();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return (int)streamTokenizer.nval;
	}
	int N = 2010, M = 2010, INF = (int)1e7;
	int n, m;
	List<List<int[]>> g = new ArrayList<>();
	boolean[][] vis = new boolean[N][N];
	int[][] arr = new int[N][N];
	void run() {
		n = nextInt();
		m = nextInt();
		for(int i = 0; i < n * n; i++) {
			g.add(new ArrayList<>());
		}
		for(int i = 0; i < m; i++) {
			int x1 = nextInt() - 1, y1 = nextInt() - 1, x2 = nextInt() - 1, y2 = nextInt() - 1;
			//无向图双向连接
			g.get(getIdx(x1, y1)).add(getPair(x2, y2));
			g.get(getIdx(x2, y2)).add(getPair(x1, y1));
		}
		for(int i = 0; i < n; i++) {
			Arrays.fill(arr[i], INF);
		}
		bfs();
		int sum = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				sum += arr[i][j];
			}
		}
		System.out.printf("%.2f", (double)sum / (n * n));
	}
	
	int getIdx(int x, int y) {
		return y * n + x;
	}
	
	int[] getPair(int x, int y) {
		return new int[] {x, y};
	}
	
	void bfs() {
		Queue<int[]> queue = new LinkedList<>();
		//终点
		queue.offer(getPair(n - 1, n - 1));
		vis[n - 1][n - 1] = true;
		arr[n - 1][n - 1] = 0;
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			int x = cur[0], y = cur[1];
			for(int[] c : g.get(getIdx(x, y))) {
				int nx = c[0], ny = c[1];
                //未访问或者路径更大就更新当前路径并对当前位置进行标记
				if(!vis[ny][nx] || arr[ny][nx] > arr[y][x] + 1) {
					arr[ny][nx] = arr[y][x] + 1;
					vis[ny][nx] = true;
					queue.offer(getPair(nx, ny));
				}
			}
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    //未访问或者路径更大就更新当前路径并对当前位置进行标记
					if(!vis[ny][nx] || arr[ny][nx] > arr[y][x] + 1) {
						arr[ny][nx] = arr[y][x] + 1;
						vis[ny][nx] = true;
						queue.add(getPair(nx, ny));
					}
				}
			}
		}
	}
}

06-04

  1. 出差

    数据规模 1 <= N <= 1000, 1 <= M <= 10000

    时间复杂度 O(N * logN)

    思路 floyd-dijkstra-bf-spfa

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class Test3 {
	public static void main(String[] args) {
		new Test3().run();
	}
	int N = 1010, M = 10010;
	StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	int nextInt() {
		try {
			streamTokenizer.nextToken();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return (int) streamTokenizer.nval;
	}
	int n, m;
	int[] times = new int[N];
	int[] dis = new int[N];
	boolean[] vis = new boolean[N];
	int INF = (int) 1e7;
	Map<Integer, List<int[]>> g = new HashMap<>();
	List<Edge> edges = new ArrayList<>();
	void run() {
		n = nextInt();
		m = nextInt();
		for(int i = 1; i <= n; i++) {
			times[i] = nextInt();
		}
		//无向图
		for(int i = 0; i < m; i++) {
			int u = nextInt(), v = nextInt(), w = nextInt();
			edges.add(new Edge(u, v, w));
			if(g.get(u) == null) g.put(u, new ArrayList<>());
			if(g.get(v) == null) g.put(v, new ArrayList<>());
			g.get(u).add(getPair(v, w));
			g.get(v).add(getPair(u, w));
		}
		bf();;
		System.out.println(dis[n] - times[n]);
		
	}
	//点
	void dijkstra() {
		PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[1] - o2[1];
			}
		});
		Arrays.fill(dis, INF);
		dis[1] = 0;
		priorityQueue.offer(getPair(1, 0));
		while(!priorityQueue.isEmpty()) {
			int[] cur = priorityQueue.poll();
			int u = cur[0];
			if(vis[u]) continue;
			vis[u] = true;
			for(int[] edge : g.get(u)) {
				int v = edge[0], w = edge[1];
				if(dis[v] > dis[u] + w + times[v]) {
					dis[v] = dis[u] + w + times[v];
					priorityQueue.offer(getPair(v, dis[v]));
				}
			}
			
		}
	}
	//边
	void spfa() {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(1);
		Arrays.fill(dis, INF);
		dis[1] = 0;
		vis[1] = true;
		while(!queue.isEmpty()) {
			int u = queue.poll();
			vis[u] = false;
			for(int[] edge : g.get(u)) {
				int v = edge[0], w = edge[1];
				if(dis[v] > dis[u] + w + times[v]) {
					dis[v] = dis[u] + w + times[v];
					if(!vis[v]) {
						vis[v] = true;
						queue.offer(v);
					}
				}
			}
		}
	}
	
	void bf() {
		Arrays.fill(dis, INF);
		dis[1] = 0;
		for(int i = 0; i < n - 1; i++) {
			for(Edge edge : edges) {
				int u = edge.u, v = edge.v, w= edge.w;
				//双向松弛
				if(dis[v] > dis[u] + w + times[v]) {
					dis[v] = dis[u] + w + times[v];
				}
				if(dis[u] > dis[v] + w + times[u]) {
					dis[u] = dis[v] + w + times[u];
				}
			}
		}
	}
	
	
	
	int[] getPair(int v, int w) {
		return new int[] {v, w};
	}
	
	class Edge{
		int u, v, w;

		public Edge(int u, int v, int w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		
	}
}

  2. 背包与魔法

    数据规模 1 <= N <= 2000, 1 <= M, K <= 10000

    时间复杂度 O(M * N)

    思路 0-1背包动态规划

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Test4 {

	public static void main(String[] args) {
		new Test4().run();
	}
	StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	
	int nextInt() {
		try {
			streamTokenizer.nextToken();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return (int)streamTokenizer.nval;
	}
	int N = 2010, M = 10010, K = 10010;
	int[][] dp = new int[M][2];
	int[] w = new int[N];
	int[] v = new int[N];
	/**
	 * 0-1背包选和不选
	 */
	void run() {
		int n = nextInt(), m = nextInt(), k = nextInt();
		for(int i = 1; i <= n; i++) {
			w[i] = nextInt();
			v[i] = nextInt();
		}
		for(int i = 1; i <= n; i++) {
			for(int j = m; j >= w[i]; j--) {
                //选和不选两条线
				dp[j][0] = Math.max(dp[j][0], dp[j - w[i]][0] + v[i]);
				dp[j][1] = Math.max(dp[j][1], dp[j - w[i]][1] + v[i]);
                //可以加上可再考虑
				if(j >= k + w[i]) {
					dp[j][1] = Math.max(dp[j][1], dp[j - w[i] - k][0] + 2 * v[i]);
				}
			}
		}
		//目标
		System.out.println(Math.max(dp[m][0], dp[m][1]));
	}

}

06-05

  1. 修路

    数据规模 1 <= n, m <= 2000

    时间复杂度 O(m * n)

    **思路**状态的转移-联想到动态规划

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Test1 {

	public static void main(String[] args) {
		new Test1().run();
	}
	StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	int nextInt(){
		try {
			streamTokenizer.nextToken();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return (int) streamTokenizer.nval;
	}
	int N = 2010, M = 2010, INF = 0x3f3f3f3f;
	//四个参数对应三维第一次参数是修A第二个参数修B第三个参数在哪条路上
	double[][][] dp = new double[N][M][2];
	int[] a = new int[N], b = new int[M];
	int n, m, d;
	void run() {
		n = nextInt();
		m = nextInt(); 
		d = nextInt();
		for(int i = 1; i <= n; i++) {
			a[i] = nextInt();
		}
		for(int i = 1; i <= m; i++) {
			b[i] = nextInt();
		}
		Arrays.sort(a, 1, n + 1);
		Arrays.sort(b, 1, m + 1);
		//边界条件
		//若一直不修B在修A
		for(int i = 1; i <= n; i++) {
			dp[i][0][0] = a[i];
			dp[i][0][1] = INF;
		}
		//若一直不修A那么B也不能修因为只能从A转移到B
		for(int i = 1; i <= m; i++) {
			dp[0][i][1] = dp[0][i][0] = INF;
		}
		//状态转移
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				//若停在A则可以由A的上一个状态转移过来或是由B转移过来(这里减去a[i - 1]是因为a[i]就包括0~i的距离了要减去重复的距离)
				dp[i][j][0] = Math.min(dp[i - 1][j][0] + a[i] - a[i - 1], dp[i - 1][j][1] + f(d, a[i] - b[j]));
				//若停在B则可以由B的上一个状态转移过来或是由A转移过来
				dp[i][j][1] = Math.min(dp[i][j - 1][1] + b[j] - b[j - 1], dp[i][j - 1][0] + f(d, a[i] - b[j]));
			}
		}
		System.out.printf("%.2f", Math.min(dp[n][m][0], dp[n][m][1]));
		
	}
	
	double f(double a, double b) {
		return Math.abs(Math.sqrt(a * a + b * b));
	}

}

  2. 斐波那契数组

    数据规模 1 <= n <= 30 1 <= ai <= 1e6

    时间复杂度 O(n * ai)

    **思路**枚举

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Test2 {
	public static void main(String[] args) {
		new Test2().run();

	}
	int N = (int) (1e6 + 10), n;
	int[] nums = new int[40];
	StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	int nextInt() {
		try {
			streamTokenizer.nextToken();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return (int) streamTokenizer.nval;
	}
	void run() {
		int ans = N, len;
		n = nextInt();
		len = n;
        //最长不超过30
		if(n > 30) n = 30;
		for(int i = 0; i < n; i++) {
			nums[i] = nextInt();
		}
		//枚举开头
		for(int i = 1; i < N; i++) {
			int a = i, b = i, c, count = 0;
			if(nums[0] == a) count++;
			if(nums[1] == b) count++;
			for(int j = 2; j < 30; j++) {
				c = a + b;
				if(c >= N) break;//剪枝
				if(c == nums[j]) count++;
				//为下一轮做准备
				a = b;
				b = c;
			}
			ans = Math.min(ans, len - count);
		}
		System.out.println(ans);
	}

}

  3. 机房

    数据规模 1 <= n m <= 100000

    时间复杂度 O(n * logn * m)

    **思路**对于每一组数据使用一次迪杰斯特拉算法

    import java.util.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Test4 {
	int N = 100010, INF = 0x3f3f3f3f;
	int[] dis = new int[N];
	boolean[] vis = new boolean[N];
	int[] w = new int[N];
	int n, m;
	Map<Integer, List<Integer>> g = new HashMap<>();
	PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {

		@Override
		public int compare(int[] o1, int[] o2) {
			// TODO Auto-generated method stub
			return o1[1] - o2[1];
		}
	});
	public static void main(String[] args) {
		new Test4().run();
	}
	StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	int nextInt() {
		try {
			streamTokenizer.nextToken();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return (int) streamTokenizer.nval;
	}
	void run() {
		n = nextInt();
		m = nextInt();
		for(int i = 0; i < n - 1; i++) {
			int u = nextInt(), v = nextInt();
			w[u]++;
			w[v]++;
			if(g.get(u) == null) g.put(u, new ArrayList<>());
			if(g.get(v) == null) g.put(v, new ArrayList<>());
			g.get(u).add(v);
			g.get(v).add(u);
		}
		for(int i = 0; i < m; i++) {
			int u = nextInt(), v = nextInt();
			System.out.println(dijkstra(u, v));
			
		}
	}
	
	int dijkstra(int start, int end) {
		Arrays.fill(dis, INF);
		Arrays.fill(vis, false);
		dis[start] = w[start];
		priorityQueue.offer(getPair(start, w[start]));
		while(!priorityQueue.isEmpty()) {
			int[] cur = priorityQueue.poll();
			int u = cur[0];
			if(vis[u]) continue;
			vis[u] = true;
			for(int v : g.get(u)) {
				if(dis[v] > dis[u] + w[v]) {
					dis[v] = dis[u] + w[v];
					priorityQueue.offer(getPair(v, dis[v]));
				}
			}
		}
		return dis[end];
	}
	
	int[] getPair(int u, int w) {
		return new int[] {u, w};
	}
}

06-06

  1. 搬砖

    数据规模 1 <= n <= 1000 1 <= w, v <= 20000

    时间复杂度 O(n * w)

    **思路**动态规划

    package demo06_06;

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

public class Test1 {
	public static void main(String[] args) {
		new Test1().run();
	}
	int W = 20010, N = 1010, n;
	int[] dp = new int[W];
	int[][] arr = new int[N][2];
	int sum = 0;
	void run() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i = 1; i <= n; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
			sum += arr[i][0];
		}
		sc.close();
        //这里将数组的行看成一个整体按照列的值对行进行排序
		Arrays.sort(arr, 1, n + 1, new Comparator<int[]>() {
			//规律: vi - wj > vj - wi -> vi + wi > vj + wj
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[0] + o1[1] - o2[0] - o2[1];
			}
		});
		int ans = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = sum; j >= arr[i][0]; j--) {
				//状态转移条件
				if(j - arr[i][0] <= arr[i][1]) {
					//由上一个状态转移而来
					dp[j] = Math.max(dp[j], dp[j - arr[i][0]] + arr[i][1]);
				}
				ans = Math.max(ans, dp[j]);
			}
		}
		System.out.println(ans);
	}
}

    总结可以根据数组中值的对多维数组进行排序根据列的值对行进行排序这里的做法和对类排序一样

06-07

  1. 小球称重

    数据规模 1 <= n <= 1e9 1 <= m <= 1e5, 0 <= cnt <= 1e6

    时间复杂度 O(cnt * m)

    **思路**计数-我们对所有的球进行计数操作若两边不平衡则将质量小的那一边球计数器进行+1操作最后我们枚举map看最大值是否为0。若为0则说明两边都是平衡的其它未出现在map中的球都是有嫌疑的。若max大于0则只需要考虑map中等于max的项对它们进行计数并返回即可

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Test1 {
	/**
	 * 我们对所有的球进行计数操作若两边不平衡则将质量小的那一边球计数器进行+1操作最后我们枚举map看最大值是否为0若为0则说明两边都是平衡的其它未出现在map中的球都是有嫌疑的
	 * 若max大于0则只需要考虑map中大于0的项对它们进行计数并返回即可
	 * @param args
	 */
	public static void main(String[] args) {
		new Test1().run();
	}
	int N = (int) 1e6, n, m;
	Map<Integer, Integer> map = new HashMap<>();
	void run() {
		n = nextInt();
		m = nextInt();
		while(m-- > 0) {
			int k = nextInt();
			int[] a = new int[k], b = new int[k];
			for(int i = 0; i < k; i++) a[i] = nextInt();
			for(int i = 0; i < k; i++) b[i] = nextInt();
			char c = nextChar();
			//判断
			if(c == '>') for(int i = 0; i < k; i++) map.merge(b[i], 1, Integer :: sum);
			else if(c == '<') for(int i = 0; i < k; i++) map.merge(a[i], 1, Integer :: sum);
			else {
				for(int i = 0; i < k; i++) {
					map.put(a[i], 0);
					map.put(b[i], 0);
				}
			}
		}
		//用最大值进行判断
		int max = 0;
		for(int x : map.values()) max = Math.max(max, x);
		//判断
		if(max == 0) {
			System.out.println(n - map.size());
			return;
		}
		//其它情况
		int cnt = 0;
		for(int x : map.values()) if(x == max) cnt++;
		System.out.println(cnt);
	}
	//快读部分-既有字符又有数字
	BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer stringTokenizer;
	String next() {
		while(stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
			try {
				stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		return stringTokenizer.nextToken();
	}
	
	int nextInt() {
		return Integer.parseInt(next());
	}
	
	char nextChar() {
		return next().charAt(0);
	}

}

    map.merge函数说明相当于put操作用合并之后的新值取代原来的值

  2. 齿轮

    数据规模 1 <= nri, m <= 2e5

    时间复杂度 O(m * n)

    **思路**成立条件若只有一个齿轮则x =1时成立。若有多个齿轮且x为1时也成立其它情况是存在两个齿轮使得满足k倍的半径关系

    具体做法我们用数组对相同的齿轮进行计数下标代表半径值代表次数对于每个x我们从1开始枚举到i * x < n,若arr[i]和arr[x * i]都大于0即都存在这里分两种情况1.多个相同且x为1满足2.i != x * i也满足

    输出时我们根据flag的值以及n是否为1以及x是否为1决定输出TRUE还是FALSE

    
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Test2 {
	public static void main(String[] args) {
		new Test2().run();
	}
	StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	int nextInt() {
		try {
			streamTokenizer.nextToken();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return (int) streamTokenizer.nval;
	}
	int N = (int) (2e5 + 10), n, m;
	int[] arr = new int[N];
	void run() {
		PrintWriter out = new PrintWriter(System.out);
		n = nextInt();
		m = nextInt();
		//对不同轮子进行计数
		for(int i = 0; i < n; i++) {
			int x = nextInt();
			arr[x]++;
		}
		while(m-- > 0) {
			int x = nextInt();
			boolean flag = false;
			for(int i = 1; i <= n / x; i++) {
				//若存在可以匹配的
				if(arr[i] > 0 && arr[i * x] > 0) {
					//两种情况不相等和多组相等的
					if(i != i * x || i == i * x && arr[i] > 1) {
						flag = true;
					}
				}
			}
			//这里有个特殊情况只有一个轮子且为x为1
			if(flag || n == 1 && x == 1) out.println("YES");
			else out.println("NO");
		}
		out.flush();
		out.close();
		
	}

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

上一篇：idea 如何设置 javaagent

下一篇：显示屏是什么，显示屏是什么意思

“蓝桥杯总结” 的相关文章

红袖添香,绝代妖娆,Ruby语言基础入门教程之Ruby3基础语法,第一次亲密接触EP011年前 (2023-02-02)
C++|变量1年前 (2023-02-02)
【MySQL】MySQL8安装1年前 (2023-02-02)
基于WEB的网上购物系统的设计与实现（附：源码 论文 sql文件）1年前 (2023-02-02)
System1年前 (2023-02-02)
【Linux】缓冲区/磁盘inode/动静态库制作1年前 (2023-02-02)
day12-实现Spring底层机制-021年前 (2023-02-02)
Java IO流 - 字节流的使用详细介绍_java字节流的使用1年前 (2023-02-02)
《安富莱嵌入式周报》第301期：ThreadX老大离开微软推出PX5 RTOS第5代系统，支持回流焊的自焊接PCB板设计，单色屏实现多级灰度播放视频效果1年前 (2023-02-02)
Yolov7训练自己的数据集（超详细教程）1年前 (2023-02-02)

阿里云国际版