360

2个小时：40道选择，2道编程

第一题¶

题目描述：¶

某个公司的共享单车单次骑行1元，但可购入VIP卡免去骑行费用，有以下几种VIP卡：

日卡a元，1天不收费；

月卡b元，30天不收费；

年卡c元， 365天不收费；

十年卡d元， 3650天不收费。

每天都允许购入任意张VIP卡，生效时间可累加。

小A在未来n天都需要骑共享单车，第i天需要骑行ri次，现在小 A 想知道，他最少以要花多少钱。

输入描述

第一行一正整数n(1≤n≤10^5) 。
第二行四个正整数a,b,c,d(1≤a,b,c,d≤10^7) ，表示四种卡的价格。
第三行n个正整数ri(1≤ri≤10^9)，表示每天骑行次数。

输出描述

输出一个整数 x，表示最小花费。

样例：输入：

10
2 40 400 3000
1 4 2 4 2 2 1 1 100 1

输出：

提示：

在第2,4,9天购买日卡，其余每天每次骑行单独付费，共花费16元。

解题思路¶

问题分析：

题目要求小A在未来n天内骑行，每天需要骑行ri次。可以购买四种VIP卡，每种卡的价格和对应的免收费天数不同，而且每天可以购买任意张VIP卡，生效时间可以累加。

关键点：

VIP卡的生效时间可以累加：这意味着可以在同一天购买多张相同或不同的VIP卡，累加生效时间。
目标是最小化总花费：需要在支付单次骑行费用和购买VIP卡之间做出选择，以达到最小的总花费。

解决思路：

由于VIP卡的生效时间可以累加，我们可以将这个问题转化为一个动态规划（DP）问题。

定义：

dp[i]：表示第 i 天到第 n 天的最小总花费。

我们从第 n 天开始倒推，考虑在第 i 天的几种选择：

选择1：支付当天的骑行费用
- 花费：\(dp[i] = dp[i+1] + ri * 1\)
- 选择2：购买1张日卡
- 花费：\(dp[i] = dp[i+1] + a\)
- 选择3：购买1张月卡
- 花费：\(dp[i] = dp[min(n+1, i+30)] + b\)
- 选择4：购买1张年卡
- 花费：\(dp[i] = dp[min(n+1, i+365)] + c\)
- 选择5：购买1张十年卡
- 花费：\(dp[i] = dp[min(n+1, i+3650)] + d\)

注意：

我们不考虑在同一天购买多张同类型的VIP卡，因为一般情况下，购买更长期的VIP卡会比多张短期VIP卡更划算。
由于VIP卡的价格与生效天数的关系，我们在计算时，可以认为购买更长期的VIP卡可能会带来更低的平均每天花费。

代码实现¶

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

public class SharedBikeMinCost {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取n
        int n = Integer.parseInt(br.readLine().trim());
        // 读取a, b, c, d
        String[] tokens = br.readLine().trim().split("\\s+");
        int a = Integer.parseInt(tokens[0]);
        int b = Integer.parseInt(tokens[1]);
        int c = Integer.parseInt(tokens[2]);
        int d = Integer.parseInt(tokens[3]);
        // 读取ri
        String[] riStr = br.readLine().trim().split("\\s+");
        int[] ri = new int[n + 2]; // 为了方便处理dp[n+1]
        for (int i = 1; i <= n; i++) {
            ri[i] = Integer.parseInt(riStr[i - 1]);
        }
        // 初始化dp数组
        long[] dp = new long[n + 2]; // dp[n+1] 默认为0
        for (int i = n; i >= 1; i--) {
            // 选项1：支付当天的骑行费用
            long costPayPerRide = dp[i + 1] + ri[i] * 1L;
            // 选项2：购买1张日卡
            long costDayCard = dp[i + 1] + a;
            // 选项3：购买1张月卡
            int nextMonthDay = Math.min(n + 1, i + 30);
            long costMonthCard = dp[nextMonthDay] + b;
            // 选项4：购买1张年卡
            int nextYearDay = Math.min(n + 1, i + 365);
            long costYearCard = dp[nextYearDay] + c;
            // 选项5：购买1张十年卡
            int nextTenYearDay = Math.min(n + 1, i + 3650);
            long costTenYearCard = dp[nextTenYearDay] + d;
            // 取最小值
            dp[i] = Math.min(Math.min(costPayPerRide, costDayCard),
                    Math.min(costMonthCard, Math.min(costYearCard, costTenYearCard)));
        }
        // 输出结果
        System.out.println(dp[1]);
    }
}

第二题¶

题目描述：给出一些仅包含正整数，加号，乘号和等号的方程，请判断这些方程能否通过插入至多一个数位（若原方程成立则可以不插）使得方程成立。

插入一个数位即将方程视为一个字符串，并将一个0到9之间的数插入中间，开头或末尾。

输入描述

第一行有一个正整数T(1<=T<=10)，代表方程的数量。
接下来T行，每行均有一个仅包含十进制正整数，加号和乘号的方程。每个方程中均只会包含一个等号。
保证输入的方程合法，即每个数均不含前导零，开头和末尾没有运算符，且没有两个相邻的运算符。
输入中方程两边计算结果的最大值不超过1000000000，且每个方程的长度不超过1000。

输出描述

对于每个方程，若其成立或可以通过往该方程中插入一个数位使得方程成立，则输出Yes，否则输出No。

样例：输入：

6
16=1+2*3
7*8*9=54
1+1=1+22
4*6=22+2
15+7=1+2
11+1=1+5

输出：

Yes
Yes
No
Yes
Yes
No

解题思路¶

直接判断原方程是否成立：
- 将方程左右两边分别解析并计算结果。
- 若左右两边结果相等，则输出 "Yes"。
- 尝试在方程中插入一个数字：
- 遍历方程中所有可能的插入位置（从位置 0 到位置 len(s)）。
- 对于每个位置，尝试插入数字 '0' 到 '9'。
- 对于每个插入后的新方程：
  - 检查方程的语法是否合法（是否有前导零、相邻运算符、运算符在开头或结尾、等号数量是否为 1 等）。
  - 若语法合法，解析并计算方程左右两边的值。
  - 若计算结果相等，输出 "Yes"。
- 若尝试所有可能的插入位置和数字后仍无法使方程成立，则输出 "No"。

代码实现¶

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

public class EquationValidator {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取 T
        int T = Integer.parseInt(br.readLine().trim());
        for (int t = 0; t < T; t++) {
            String equation = br.readLine().trim();
            if (validateEquation(equation)) {
                System.out.println("Yes");
            } else {
                boolean found = false;
                // 尝试在每个位置插入一个数字
                for (int i = 0; i <= equation.length(); i++) {
                    for (char ch = '0'; ch <= '9'; ch++) {
                        StringBuilder sb = new StringBuilder(equation);
                        sb.insert(i, ch);
                        String newEquation = sb.toString();
                        if (validateEquation(newEquation)) {
                            found = true;
                            break;
                        }
                    }
                    if (found) break;
                }
                System.out.println(found ? "Yes" : "No");
            }
        }
    }

    // 验证方程是否合法并计算结果
    private static boolean validateEquation(String equation) {
        ArrayList<String> tokens = new ArrayList<>();
        int equalSignCount = 0;
        int len = equation.length();
        int i = 0;
        char prevTokenType = ' '; // 'n'表示数字，'o'表示运算符
        while (i < len) {
            char ch = equation.charAt(i);
            if (Character.isDigit(ch)) {
                int start = i;
                while (i < len && Character.isDigit(equation.charAt(i))) {
                    i++;
                }
                String numberStr = equation.substring(start, i);
                // 检查前导零
                if (numberStr.length() > 1 && numberStr.startsWith("0")) {
                    return false;
                }
                tokens.add(numberStr);
                prevTokenType = 'n';
            } else if (ch == '+' || ch == '*' || ch == '=') {
                // 检查运算符在开头或结尾，或相邻运算符
                if (prevTokenType == 'o' || prevTokenType == ' ') {
                    return false;
                }
                if (ch == '=') {
                    equalSignCount++;
                    if (equalSignCount > 1) {
                        return false;
                    }
                }
                tokens.add(String.valueOf(ch));
                i++;
                prevTokenType = 'o';
            } else {
                // 非法字符
                return false;
            }
        }
        // 检查运算符是否在结尾
        if (prevTokenType == 'o') {
            return false;
        }
        if (equalSignCount != 1) {
            return false;
        }
        // 分割左右表达式
        int eqIndex = tokens.indexOf("=");
        if (eqIndex == -1) {
            return false;
        }
        ArrayList<String> leftTokens = new ArrayList<>(tokens.subList(0, eqIndex));
        ArrayList<String> rightTokens = new ArrayList<>(tokens.subList(eqIndex + 1, tokens.size()));
        try {
            long leftValue = evaluateExpression(leftTokens);
            long rightValue = evaluateExpression(rightTokens);
            return leftValue == rightValue;
        } catch (Exception e) {
            return false;
        }
    }

    // 计算表达式的值
    private static long evaluateExpression(ArrayList<String> tokens) throws Exception {
        ArrayList<String> postFix = toPostFix(tokens);
        return evaluatePostFix(postFix);
    }

    // 中缀表达式转后缀表达式（逆波兰表示法）
    private static ArrayList<String> toPostFix(ArrayList<String> tokens) throws Exception {
        ArrayList<String> output = new ArrayList<>();
        ArrayList<String> stack = new ArrayList<>();
        for (String token : tokens) {
            if (isNumber(token)) {
                output.add(token);
            } else if (token.equals("+") || token.equals("*")) {
                while (!stack.isEmpty() && precedence(stack.get(stack.size() - 1)) >= precedence(token)) {
                    output.add(stack.remove(stack.size() - 1));
                }
                stack.add(token);
            } else {
                throw new Exception("Invalid token");
            }
        }
        while (!stack.isEmpty()) {
            output.add(stack.remove(stack.size() - 1));
        }
        return output;
    }

    // 计算后缀表达式的值
    private static long evaluatePostFix(ArrayList<String> postFix) throws Exception {
        ArrayList<Long> stack = new ArrayList<>();
        for (String token : postFix) {
            if (isNumber(token)) {
                stack.add(Long.parseLong(token));
            } else if (token.equals("+") || token.equals("*")) {
                if (stack.size() < 2) {
                    throw new Exception("Invalid expression");
                }
                long b = stack.remove(stack.size() - 1);
                long a = stack.remove(stack.size() - 1);
                long result = token.equals("+") ? a + b : a * b;
                stack.add(result);
            } else {
                throw new Exception("Invalid token");
            }
        }
        if (stack.size() != 1) {
            throw new Exception("Invalid expression");
        }
        return stack.get(0);
    }

    // 判断是否为数字
    private static boolean isNumber(String token) {
        return Character.isDigit(token.charAt(0));
    }

    // 获取运算符优先级
    private static int precedence(String op) {
        if (op.equals("*")) return 2;
        if (op.equals("+")) return 1;
        return 0;
    }
}