51工具盒子

依楼听风雨
笑看云卷云舒,淡观潮起潮落

【Java】AtCoder Beginner Contest 402

一、简介 {#一-简介}

  Tokio Marine & Nichido Fire Insurance Programming Contest 2025

二、题目 {#二-题目}

A.CBC⭐ {#A-CBC-}

思考 {#思考}

  使用Character.isUpperCase(?)判断字符是否为大写,是则用于拼接新的字符串即可。也可以通过ASCII码进行判断,如:90>= Integer.valueOf(?) >= 65,大写字母65-90,小写字母97-122

代码 {#代码}

import java.util.Scanner;

/\*\*

`
`
* `@author nepakina
  */
  public class Main {
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  String input = sc.next();
  StringBuilder res = new StringBuilder();
  for (int i = 0; i < input.length(); i++) {
  if (Character.isUpperCase(input.charAt(i))) {
  res.append(input.charAt(i));
  }
  }
  System.out.println(res);
  sc.close();
  }
  }
  `

B.Restaurant Queue⭐ {#B-Restaurant-Queue-}

思考 {#思考-}

  题意为按两种方式进行排序,对没有序号的进行编号,编号的规则是按最早的序号再利用,使用队列进行先进先出处理即可。

代码 {#代码-}

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

/\*\*

`
`
* `@author nepakina
  */
  public class Main {
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int num = sc.nextInt();
  Queue<Integer> queue = new LinkedList<>();
  while (num > 0) {
  int type = sc.nextInt();
  if (type == 1) {
  int order = sc.nextInt();
  queue.add(order);
  } else {
  System.out.println(queue.poll());
  }
  num--;
  }
  sc.close();
  }
  }
  `

C.Dislike Foods⭐⭐ {#C-Dislike-Foods--}

思考 {#思考--}

  将食物按食材编号进行分类和标记,每天对可食用食物进行更新,同时判断更新后食物是否可食用。对于食物分类和标记,分类采用Map记录食材和食物的关系:ingNums<key = 食材编号, value = 食物编号>;标记采用int数组记录食物当前包含的不可食用食材种类数:dishesIngredientNums[食物编号] = 不可食用食材种类
  最后按新增可食用食材编号取出涉及的食物编号,再按食物编号对数组中记录的其所包含的不可使用食材种数进行-1处理,如果不可使用食材种数变为0,则表示该食物可食用,计数+1,计算不应重置,因为其本身具有叠加性质(可食用食材包含新解锁食材和旧解锁食材)。

代码 {#代码--}

import java.util.*;

/\*\*

`
`
* `
  `@author nepakina
  */
  public class Main {
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int types = sc.nextInt();
  int dishes = sc.nextInt();
  Map<Integer, List<Integer>> ingNums = new HashMap<>();
  int[] dishesIngredientNums = new int[dishes + 1];
  for (int i = 0; i < dishes; i++) {
  int ingredientNums = sc.nextInt();
  dishesIngredientNums[i + 1] = ingredientNums;
  for (int j = 0; j < ingredientNums; j++) {
  int no = sc.nextInt();
  List<Integer> dishesFlags = ingNums.getOrDefault(no, new ArrayList<>());
  dishesFlags.add(i + 1);
  ingNums.put(no, dishesFlags);
  }
  }
  `
  `

       int res = 0;
       for (int i = 0; i &lt; types; i++) {
           int ingredient = sc.nextInt();
           List&lt;Integer&gt; dishesFlags = ingNums.getOrDefault(ingredient, new ArrayList&lt;&gt;());
           for (Integer dishesId : dishesFlags) {
               dishesIngredientNums[dishesId]--;
               if (dishesIngredientNums[dishesId] == 0) {
                   res++;
               }
           }
           System.out.println(res);
       }
       sc.close();


  `
  `

  `}
  }
  `


D.Line Crossing⭐⭐ {#D-Line-Crossing--}

思考 {#思考---}

  求相交线组数,可拆分为从M条线中随机抽取两条的情况总数 - 各平行线情况组合总数
  如何判断两条线是否平行,可简化为记录坐标和,坐标和超过N的线与其平行线的关系为相等或相差N;故针对每条线,使用坐标和为下标(超过N的减去N再作为下标),出现次数为值进行记录(即互相平行的线条数)。
  如上所述,flag[坐标和] = 3则表示有3条线互相平行。总情况数 = ((long) m * (m - 1)) / 2(M条线随机组合),flag数组的各元素通过公式flag[i] * (flag[i] - 1) / 2(平行线之间随机组合,小于等于1时不存在组合)得出的结果总和为平行线总数。
  最后通过两值做差即为所求。(注意:由于数据计算结果超过了int,所以需要使用long存储计算结果。)

代码 {#代码---}

import java.util.*;

/\*\*

`
`
* `@author nepakina
  */
  public class Main {
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int m = sc.nextInt();
  long total = ((long) m * (m - 1)) / 2;
  int[] flags = new int[n + 1];
  for (int i = 0; i < m; i++) {
  int a1 = sc.nextInt();
  int a2 = sc.nextInt();
  if (a1 + a2 > n) {
  flags[a1 + a2 - n]++;
  } else {
  flags[a1 + a2]++;
  }
  }
  long res = 0;
  for (int i = 1; i < flags.length; i++) {
  // 这里理论上来说flag > 1时进行res的计算,但由于flag无论是0还是1,计算结果都是0,所以可以忽略
  int flag = flags[i] - 1;
  res += ((long) flag * (flag +1)) / 2;
  }
  System.out.println(total - res);
  sc.close();
  }
  }
  `

E.Payment Required {#E-Payment-Required}

思考 {#思考----}

  状压dp。

代码 {#代码----}

import java.util.*;

/\*\*

`
`
* `
  `@author nepakina
  */
  public class Main {
  public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  int problemNum = scanner.nextInt();
  int assets = scanner.nextInt();
  `
  `

       // 每题相应得分(score)、花费(cost)、答对概率(probability)
       int[] score = new int[problemNum + 1];
       int[] cost = new int[problemNum + 1];
       double[] probability = new double[problemNum + 1];

       for (int i = 1; i &lt;= problemNum; i++) {
           score[i] = scanner.nextInt();
           cost[i] = scanner.nextInt();
           probability[i] = scanner.nextDouble() / 100.0;
       }

       double[][] dp = new double[assets + 1][1 &lt;&lt; problemNum];

       double ans = 0;
       for (int asset = 1; asset &lt;= assets; asset++) {
           for (int status = 0; status &lt; (1 &lt;&lt; problemNum); status++) {
               for (int order = 0; order &lt; problemNum; order++) {
                   // order从0开始循环,记录的值从1开始有效,所以取相关值是需要加1
                   int curOrder = order + 1;
                   // (status &gt;&gt; order) &amp; 1 表示status的第order位值为1;同时花费不能超过当前可用资产
                   if (((status &gt;&gt; order) &amp; 1) == 1 &amp;&amp; cost[curOrder] &lt;= asset) {
                       dp[asset][status] = Math.max(dp[asset][status],
                               // 当前最大期望的风 = 通过概率 * 通过情况下最大期望得分 + 不通过概率 * 不通过下最大期望得分
                               probability[curOrder] * (dp[asset - cost[curOrder]][status ^ (1 &lt;&lt; order)] + score[curOrder])
                                       // 未通过是最大期望得分
                                       + (1 - probability[curOrder]) * dp[asset - cost[curOrder]][status]
                       );
                       ans = Math.max(ans, dp[asset][status]);
                   }
               }
           }
       }

       System.out.println(ans);
       scanner.close();


  `
  `

  `}
  }
  `


官方解答:E - Payment Required Editorial {#官方解答-E---Payment-Required-Editorial}
N, X = map(int, input().split())
S = [0] * N
C = [0] * N
P = [0] * N
for i in range(N):
    S[i], C[i], P[i] = map(int, input().split())
    P[i] /= 100
d = [[0.0 for _ in range(X + 1)] for _ in range(1 << N)]
for x in range(X + 1):
    for s in range(1 << N):
        for i in range(N):
            xx = x - C[i]
            ss = s | (1 << i)
            if xx < 0 or s == ss:
                continue
            val = P[i] * (d[ss][xx] + S[i]) + (1 - P[i]) * d[s][xx]
            d[s][x] = max(d[s][x], val)
print(d[0][X])

F.Path to Integer⭐⭐ {#F-Path-to-Integer--}

思考 {#思考-----}

  由于网格数较小,可以采用暴力枚举的方式,使用dps深度优先搜索进行处理。但又由于完全暴力的时间复杂度过高会导致超时,故可以通过折中的方式进行寻路搜索,这样刚好最坏情况的时间复杂度在可接受的范围。可以简单理解为一个数组从中间同时向两边遍历元素。

代码 {#代码-----}

官方解答:F - Path to Integer Editorial {#官方解答-F---Path-to-Integer-Editorial}

G.Sum of Prod of Mod of Linear⭐⭐⭐ {#G-Sum-of-Prod-of-Mod-of-Linear---}

思考 {#思考------}

  略

代码 {#代码------}

官方解答:G - Path to Integer Editorial {#官方解答-G---Path-to-Integer-Editorial}
赞(1)
未经允许不得转载:工具盒子 » 【Java】AtCoder Beginner Contest 402