每日省赛真题解析·第九天
每日省赛真题解析·第九天

每日省赛真题解析·第九天

目录

  • 2019省赛试题H
  • 2019省赛试题I
  • 2019省赛试题J

一.2019省赛真题H

题目链接:人物相关性分析 – 蓝桥云课 (lanqiao.cn)

题目要求:见上面图片

解题思路:

代码:

import java.util.Scanner;

public class Main {
    public static int get(String s, int i) {
        if (s.substring(i, Math.min(s.length(), i + 5)).equals("Alice")) {
            if (i - 1 >= 0 && Character.isLetter(s.charAt(i - 1)) || i + 5 < s.length() && Character.isLetter(s.charAt(i + 5)))
                return -1;
            return 0;
        } else if (s.substring(i, Math.min(s.length(), i + 3)).equals("Bob")) {
            if (i - 1 >= 0 && Character.isLetter(s.charAt(i - 1)) || i + 3 < s.length() && Character.isLetter(s.charAt(i + 3)))
                return -1;
            return 1;
        } else return -1;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        in.nextLine();
        String s = in.nextLine();

        long cnt = 0;
        long[] c = new long[2];
        for (int l = 0, r = 0; r < s.length(); r++) {
            int x = get(s, r);
            if (x == -1) continue;
            c[x]++;
            while (l < r) {
                int y = get(s, l);
                if (y == -1) {
                    l++;
                    continue;
                }
                if (r - l - (s.charAt(l) == 'A' ? 5 : 3) <= k) break;
                c[y]--;
                l++;
            }
            cnt += c[x ^ 1];
        }

        System.out.println(cnt);
    }
}

二.2019省赛试题I

题目链接:后缀表达式 – 蓝桥云课 (lanqiao.cn)

题目要求:

给定 N 个加号、M 个减号以及 N + M + 1 个整数 A1​,A2​,⋅⋅⋅,A(N+M+1​),小明想知道在所有由这 NN个加号、MM个减号以及 N + M +1 个整数凑出的合法的后缀表达式中,结果最大的是哪一个?

请你输出这个最大的结果。

例如使用 1 2 3 + -,则 “2 3 + 1 -” 这个后缀表达式结果是 4,是最大的。

解题思路:

代码:

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int n = Input.nextInt(), m = Input.nextInt();
        int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
        long sum = 0, asum = 0;
        for (int i = 0; i < n + m + 1; i++) {
            int x = Input.nextInt();
            sum += x;
            asum += Math.abs(x);
            mn = Math.min(mn, x);
            mx = Math.max(mx, x);
        }
        if (m == 0) Input.out.println(sum);
        else Input.out.println(asum - Math.abs(mn) - Math.abs(mx) + mx - mn);
        Input.out.flush();
    }

    static class Input {
        static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        static PrintWriter out = new PrintWriter((new OutputStreamWriter(System.out)));
        static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

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

        static double nextDouble() throws IOException {
            streamTokenizer.nextToken();
            return streamTokenizer.nval;
        }

        static String nextLine() throws IOException {
            return bufferedReader.readLine();
        }

        static char next() throws IOException {
            return (char) bufferedReader.read();
        }
    }
}

三.2019省赛试题J

题目链接:灵能传输 – 蓝桥云课 (lanqiao.cn)

题目要求:见上面图片

解题思路:

代码:

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

public class Main {
    public static void main(String[] args) throws IOException {
        int N = (int)(3e5 + 10);
        long[] s = new long[N];
        long[] a = new long[N];
        boolean[] v = new boolean[N];

        int t = Input.nextInt();
        while (t --> 0) {
            int n = Input.nextInt();
            s[0] = 0;
            for (int i = 0; i < n; i++)
                s[i + 1] = s[i] + Input.nextInt();

            long s0 = s[0], sn = s[n];
            if (s0 > sn) {
                s0 ^= sn;
                sn ^= s0;
                s0 ^= sn;
            }
            Arrays.sort(s, 0, n + 1);
            for (int i = 0; i <= n; i++) if (s[i] == s0) {
                s0 = i;
                break;
            }
            for (int i = n; i >= 0; i--) if (s[i] == sn) {
                sn = i;
                break;
            }

            int l = 0, r = n;
            for (int i = 0; i <= n; i++) v[i] = false;
            for (int i = (int)s0; i >= 0; i -= 2) {
                a[l++] = s[i];
                v[i] = true;
            }
            for (int i = (int)sn; i <= n; i += 2) {
                a[r--] = s[i];
                v[i] = true;
            }
            for (int i = 0; i <= n; i++)
                if (!v[i]) a[l++] = s[i];

            long ans = 0;
            for (int i = 1; i <= n; i++)
                ans = Math.max(ans, Math.abs(a[i] - a[i - 1]));
            Input.out.println(ans);
            Input.out.flush();
        }
    }

    static class Input {
        static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        static PrintWriter out = new PrintWriter((new OutputStreamWriter(System.out)));
        static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

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

        static double nextDouble() throws IOException {
            streamTokenizer.nextToken();
            return streamTokenizer.nval;
        }

        static String nextLine() throws IOException {
            return bufferedReader.readLine();
        }

        static char next() throws IOException {
            return (char) bufferedReader.read();
        }
    }
}