• 牛客_小白月赛_61

    传送门

    A

    在这里插入图片描述
    如果不是特意防止溢出了，那么需要用long,否则会一直卡
    很普通的写法,超了就 +1, 最后补上一个 1就行
    (所以, 这题我wa了8次, 卡了半个小时,就是因为没开 long ! ! !)

    package com.csh.A;
/**
 * @author :Changersh
 * @date : 2022/11/18
 */

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

public class Main {
    public static void main(String[] args) {
        int n = sc.nextInt();
        int v = sc.nextInt();
        long ans = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            if (sum + t <= v) sum += t;
            else {
                ans++;
                sum = t;
            }
        }
        out.println(ans + 1);
        out.close();
    }
    static class FastScanner{
        // sc.xxx;
        // out.print();
        // out.flush();
        // out.close();
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(InputStream in) {
            br=new BufferedReader( new InputStreamReader(System.in));
            eat("");
        }
        public void eat(String s) {
            st=new StringTokenizer(s);
        }

        public String nextLine() {
            try {
                return br.readLine();
            }catch(IOException e) {
                return null;
            }
        }

        public boolean hasNext() {
            while(!st.hasMoreTokens()) {
                String s=nextLine();
                if(s==null)return false;
                eat(s);
            }

            return true;
        }

        public String next() {
            hasNext();
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static FastScanner sc=new FastScanner(System.in);
    static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    B

    在这里插入图片描述
    分类讨论, 我可能写繁了
    因为范围特别大, 几万位, 所以用 String 接收
    然后就是判断一下 小数位的大小, 关键是小数的第一个数字 = 5时, 要分类 :

    1. 真的是 = 5
    2. 50000000000000000000000000000001 还是大于 0.5 的
      我选择搞了一个标准的String是和小数位数相等的, 50000000000000000000000000
    // package com.csh.B;
/**
 * @author :Changersh
 * @date : 2022/11/18
 */

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

public class Main {
    public static void main(String[] args) {
        String s = sc.next(); String t = sc.next();
        int n = t.length();
        char[] c = new char[n];
        Arrays.fill(c, '0');
        c[0] = '5';
        int a, b;
        if (s.length() == 1) a = Integer.parseInt(s);
        else {
            a = Integer.parseInt(s.substring(s.length() - 2));
        }
        if (t.length() == 1) b = Integer.parseInt(t);
        else {
            String s1 = new String(c);
            if (t.compareTo(s1) > 0) b = 6;
            else if (t.compareTo(s1) == 0) b = 5;
            else b = 4;
        }

        if (b > 5) out.println("Happy birthday to MFGG");
        else if (b < 5 && b > 0) out.println("Happy birthday to YXGG");
        else if (b == 0) {
            out.println("PLMM");
        } else {
            if (a % 2 == 0) {
                if (b == 0) out.println("PLMM");
                else out.println("Happy birthday to YXGG");
            } else {
                out.println("Happy birthday to MFGG");
            }
        }
        out.close();
    }
    static class FastScanner{
        // sc.xxx;
        // out.print();
        // out.flush();
        // out.close();
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(InputStream in) {
            br=new BufferedReader( new InputStreamReader(System.in));
            eat("");
        }
        public void eat(String s) {
            st=new StringTokenizer(s);
        }

        public String nextLine() {
            try {
                return br.readLine();
            }catch(IOException e) {
                return null;
            }
        }

        public boolean hasNext() {
            while(!st.hasMoreTokens()) {
                String s=nextLine();
                if(s==null)return false;
                eat(s);
            }

            return true;
        }

        public String next() {
            hasNext();
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static FastScanner sc=new FastScanner(System.in);
    static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    C

    在这里插入图片描述
    在这里插入图片描述
    bfs, 判断有点麻烦,

    1. 先 bfs 得到plmm的所有能移动到的位置, 和距离原位置的距离 (plmm的移动距离有限)
    2. 小猫虽然嗅觉有限, 但是可以无限制移动, 再对小猫做 bfs, 没有限制
    3. 最后遍历, 找到 距离二者最近的点 (人可以到达, 小猫可以到达, 小猫可以闻到的) 的距离和
    4. 找不到返回 -1
    // package com.csh.C;
/**
 * @author :Changersh
 * @date : 2022/11/18
 */

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

public class Main {
    private static int N = 1005, n, m, r1, r2, x1, x2, y1, y2;
    private static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    private static char[][] g = new char[N][N];
    private static int[][] per = new int[N][N], cat = new int[N][N];
    public static void main(String[] args) {
        n = sc.nextInt(); m = sc.nextInt(); r1 = sc.nextInt(); r2 = sc.nextInt();
        for (int i = 0; i < n; i++) {
            g[i] = sc.next().toCharArray();
            Arrays.fill(per[i], -1);
            Arrays.fill(cat[i], -1);
        }
        int[] a = find('P');
        x1 = a[0]; y1 = a[1];
        int[] b = find('M');
        x2 = b[0]; y2 = b[1];
        bfs();
        // 确定好距离之后，判断是否能走到猫咪的嗅觉内，并且猫咪能到达的点
        int ans = 20021016;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m ;j++) {
                if ((Math.abs(i - x2) + Math.abs(j - y2)) <= r2 && per[i][j] != -1 && cat[i][j] != -1) {
                    ans = Math.min(per[i][j] + cat[i][j], ans);
                }
            }
        }
        out.println(ans == 20021016 ? -1 : ans);
        out.close();
    }
    private static void bfs() {
        // 人
        for (int[] i : per) Arrays.fill(i, -1); // 初始化距离
        per[x1][y1] = 0;
        LinkedList<int[]> q = new LinkedList<>();
        q.add(new int[]{x1, y1});
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0]; int b = t[1];
            for (int i = 0; i < 4; i++) {
                int x = dx[i] +a; int y = dy[i] + b;
                if ( x >= 0 && x < n && y >= 0 && y < m && ((Math.abs(x - x1) + Math.abs(y - y1)) <= r1) && per[x][y] == -1 && g[x][y] != '*') {
                    per[x][y] = per[a][b] + 1;
                    q.add(new int[]{x, y});
                }
            }
        }

        for (int[] i : cat) Arrays.fill(i, -1); // 初始化距离
        cat[x2][y2] = 0;
        LinkedList<int[]> p = new LinkedList<>();
        p.add(new int[]{x2, y2});
        while (!p.isEmpty()) {
            int[] t = p.poll();
            int a = t[0]; int b = t[1];
            for (int i = 0; i < 4; i++) {
                int x = dx[i] +a; int y = dy[i] + b;
                if ( x >= 0 && x < n && y >= 0 && y < m && cat[x][y] == -1 && g[x][y] != '*') {
                    cat[x][y] = cat[a][b] + 1;
                    p.add(new int[]{x, y});
                }
            }
        }
    }
    private static int[] find(char c) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == c) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    static class FastScanner{
        // sc.xxx;
        // out.print();
        // out.flush();
        // out.close();
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(InputStream in) {
            br=new BufferedReader( new InputStreamReader(System.in));
            eat("");
        }
        public void eat(String s) {
            st=new StringTokenizer(s);
        }

        public String nextLine() {
            try {
                return br.readLine();
            }catch(IOException e) {
                return null;
            }
        }

        public boolean hasNext() {
            while(!st.hasMoreTokens()) {
                String s=nextLine();
                if(s==null)return false;
                eat(s);
            }

            return true;
        }

        public String next() {
            hasNext();
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static FastScanner sc=new FastScanner(System.in);
    static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138

    E

    在这里插入图片描述
    因为有地方可能还是会溢出, 所以没过, 大概思路是对的
    n个数的所有排列的逆序对 = (n! / 2) * 不相等的数字的对数
    /2用乘法逆元来求
    不相等数字的对数:
    在这里插入图片描述

    // package com.csh.E;
/**
 * @author :Changersh
 * @date : 2022/11/20
 */

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

public class Main {
    private static final long mod = 1000000000 + 7;
    private static int N = 100005, n;
    private static int[] a = new int[N], cnt = new int[N];

    public static void main(String[] args) {
        n = sc.nextInt();
        long ans = 1; // n!
        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            a[i] = t;
            cnt[t]++;
            ans = ((ans % mod) * ((i + 1L) % mod)) % mod;
        }
//        out.println(ans);
        long t = 500000004;
//        out.println(t);
        ans = ((ans % mod) * (t % mod)) % mod; // n! / 2;
        long sum = ((n % mod * (n - 1) % mod) % mod / 2) % mod;
        for (int i = 0; i < 100002; i++) {
            if (cnt[i] > 1) {
                int a = cnt[i];
                sum = (sum - (a * (a - 1)) / 2) % mod;
            }
        }

        sum %= mod;
        out.println((ans * sum) % mod);
        out.close();
    }

    static class FastScanner {
        // sc.xxx;
        // out.print();
        // out.flush();
        // out.close();
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(System.in));
            eat("");
        }

        public void eat(String s) {
            st = new StringTokenizer(s);
        }

        public String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!st.hasMoreTokens()) {
                String s = nextLine();
                if (s == null) return false;
                eat(s);
            }

            return true;
        }

        public String next() {
            hasNext();
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static FastScanner sc = new FastScanner(System.in);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
  • 相关阅读:
    基于布谷鸟优化K均值的WSN分簇路由算法
    关于商业智能BI，今天只谈这五点
    六零导航页SQL注入漏洞复现（CVE-2023-45951）
    background
    【问题解决】Tensorflow中run究竟运行了哪些节点？
    数论合集
    【附源码】计算机毕业设计SSM网络考试系统设计
    vue——计算属性、侦听属性、组件、组件通信、ref属性、数据总线、动态组件、插槽
    浅学习泛型
    如何将多模态数据融入到BERT架构中-多模态BERT的两类预训练任务
  • 原文地址：https://blog.csdn.net/Changersh/article/details/127951358