51工具盒子一、简介 {#一-简介}
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 < types; i++) {
int ingredient = sc.nextInt();
List<Integer> dishesFlags = ingNums.getOrDefault(ingredient, new ArrayList<>());
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 <= problemNum; i++) {
score[i] = scanner.nextInt();
cost[i] = scanner.nextInt();
probability[i] = scanner.nextDouble() / 100.0;
}
double[][] dp = new double[assets + 1][1 << problemNum];
double ans = 0;
for (int asset = 1; asset <= assets; asset++) {
for (int status = 0; status < (1 << problemNum); status++) {
for (int order = 0; order < problemNum; order++) {
// order从0开始循环，记录的值从1开始有效，所以取相关值是需要加1
int curOrder = order + 1;
// (status >> order) & 1 表示status的第order位值为1；同时花费不能超过当前可用资产
if (((status >> order) & 1) == 1 && cost[curOrder] <= asset) {
dp[asset][status] = Math.max(dp[asset][status],
// 当前最大期望的风 = 通过概率 * 通过情况下最大期望得分 + 不通过概率 * 不通过下最大期望得分
probability[curOrder] * (dp[asset - cost[curOrder]][status ^ (1 << 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---}
思考 {#思考------}
略
代码 {#代码------}
略
