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

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

目录

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

一.2020省赛试题H

题目链接:数字三角形 – 蓝桥云课 (lanqiao.cn)

题目要求:

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外,向左下走的次数与向右下走的次数相差不能超过 1。

解题思路:

经典 dp 问题。解题思路比较常规,但是需要注意的是,题目给出了一个附加条件,就是“向左下走的次数与向右下走的次数相差不能超过 1。”为了方便处理,我们将上图数字三角形改成直角三角形,如下:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

·100ptsO(n3) 解法一

·100ptsO(n2) 解法二

代码:

import java.util.*;
public class Main {
    private static int[][] a = new int[110][110];
    private static int[][] dp = new int[110][110];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j] = cin.nextInt();
            }
        }
        for(int i = 0 ; i <= n ; i ++) for(int j = 0 ; j <= n ; j ++) dp[i][j] = -100000000;
        dp[1][1] = a[1][1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
            }
        }
        if (((n - 1) & 1) != 0) {
            System.out.println(Math.max(dp[n][1 + (n - 1) / 2], dp[n][1 + (n - 1) / 2 + 1]));
        } else {
            System.out.println(dp[n][1 + (n - 1) / 2]);
        }
    }
}

二.2020省赛试题I

题目链接:子串分值和 – 蓝桥云课 (lanqiao.cn)

题目要求:见上述图片

解题思路:

代码:

import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner cin = new Scanner(System.in);
    String s = cin.nextLine();
    int[] suf = new int[s.length() + 1];
    int[] last = new int[30];
      long ans = 0;
    Arrays.fill(last , s.length());
    for(int i = s.length() - 1 ; i >= 0 ; i --){
      int x = s.charAt(i) - 'a';
      suf[i] = last[x];
      last[x] = i;
    }
    for(int i = 0 ; i < s.length() ; i ++){
      ans += (long)1 * (i + 1) * (suf[i] - i);
    }
    System.out.println(ans);
  }
}

三.2020省赛试题J

题目链接:暂无

题目要求:见上述图片

解题思路:

代码:

import java.io.*;
import java.util.*;
class InputReader{
    private final static int BUF_SZ = 65536;
    BufferedReader in;
    StringTokenizer tokenizer;
    public InputReader(InputStream in) {
        super();
        this.in = new BufferedReader(new InputStreamReader(in),BUF_SZ);
        tokenizer = new StringTokenizer("");
    }
    private String next() {
        while (!tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
}

public class Main {
    private static int m;
    private static int x;
    private static int ans;
    private static int[] sum = new int[5];
    private static int[] dp = new int[310];
    private static Vector<Vector<Integer>> vec1 = new Vector<Vector<Integer>>();
    private static Vector<Vector<Integer>> vec2 = new Vector<Vector<Integer>>();
    private static Vector<Vector<Integer>> vec3 = new Vector<Vector<Integer>>();
    private static Vector<Vector<Integer>> vec4 = new Vector<Vector<Integer>>();
    private static Vector<Vector<Integer>> vec = null;
    private static int calc() {
        int V = 0;
        for (int l = 4; l >= 1; l--) {
            V += sum[l];
            vec = null;
            if(l == 1) vec = vec1;
            else if(l == 2) vec = vec2;
            else if(l == 3) vec = vec3;
            else if(l == 4) vec = vec4;
            for (Vector<Integer> i : vec) {
                for (int k = V; k >= 0; k--) {
                    for (int j = 0; j < i.size(); j++) {
                        int w = j + 1;
                        int v = i.get(j);
                        if (k - w >= 0) {
                            dp[k] = Math.max(dp[k], dp[k - w] + v);
                        }
                        else break;
                    }
                }
            }
        }
        for (int i = 0; i <= V; i++) {
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        InputReader cin = new InputReader(System.in);
        for (int i = 1; i <= 6; i++) {
            int n = cin.nextInt();
            for (int j = 1; j <= n; j++) {
                x = cin.nextInt();
                sum[x]++;
            }
        }
        m = cin.nextInt();
        for (int i = 1; i <= m; i++) {
            int l = cin.nextInt(), p = cin.nextInt();
            Vector<Integer> b = new Vector<Integer>();
            for (int j = 1; j <= p; j++) {
                x = cin.nextInt();
                b.add(x);
            }
            if(l == 1) vec1.add(b);
            else if(l == 2) vec2.add(b);
            else if(l == 3) vec3.add(b);
            else if(l == 4) vec4.add(b);
        }
        System.out.println(calc());
    }
}