保定学院寒假第一次训练赛题解
目录
BDU20250123
题干
思路
参考代码
大数相加
题干
思路
参考代码
贪吃的王公
题干
思路
参考代码
最小覆盖子串
题干
思路
参考代码
用辗转相除法求二元一次不定方程
题干
思路
参考代码
正负之门
题干
思路
参考代码
BDU20250123
题干
输出BDU20250123
思路
简单的输入输出
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
System.out.println("BDU20250123");
}
}大数相加
题干
给定两个非常大的非负整数 num1 和 num2，它们的位数可能超过标准整数类型的范围（如 int 或 long）。请你编写一个程序，计算这两个大整数的和，并输出结果。
思路
典型的大整数加法，题干已经说明了，Java可以使用BigInteger进行实现（BigInteger 是 Java 提供的一个类，用于处理任意精度的整数。这对于需要处理非常大的整数的情况非常有用）
参考代码
import java.util.*;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String num1 = sc.nextLine();
BigInteger num3 = new BigInteger(num1);
String num2 = sc.nextLine();
BigInteger num4 = new BigInteger(num2);
BigInteger sum = num3.add(num4);
System.out.println(sum);
}
}
贪吃的王公
题干
这是一个特别的夜晚，你准备去吃一顿大餐。你来到路边一个叫“贪吃的王公”的印度菜馆，那里供应据说是世界上最美味的咖喱饭。菜单是这样的:
咖喱饭：140元
冰激凌：70元
饮料：30元
小费：总价格的20%
你想尽可能地多吃几碗饭，但是要注意：
1. 咖喱非常辣，对于你吃的每1碗咖喱饭，你都要配半份冰激凌来消化。
2. 冰激凌非常甜，每吃1份冰激凌，要喝2杯冰水。
你想尽可能地多吃几碗咖喱饭，用你现在手里的钱，你最多可以吃多少碗咖喱饭？
思路
初始化咖喱份数，初始值为 1。
初始化当前总花费，初始值为 0。
如果 money 小于 288，则直接输出 0，因为即使购买一份咖喱也无法满足最低花费要求。（总花费 total = 140 + 70 + 30 = 240 ，小费 total * 0.2 = 240 * 0.2 = 48 ）
循环计算总花费：
使用 while (true) 循环不断尝试增加咖喱的数量，直到总花费超过 money。
在每次循环中，重新初始化 total 为 0。
根据 curry 的奇偶性来计算不同情况下的总花费：
如果 curry 是偶数：
计算冰淇淋数量 iceCream = curry / 2.0。
总花费 total 包括咖喱成本、冰淇淋成本和额外费用。
如果 curry 是奇数：
计算冰淇淋数量 iceCream1 = curry / 2.0，并向上取整得到实际冰淇淋数量 iceCream = (int) Math.ceil(iceCream1)。
总花费 total 包括咖喱成本、冰淇淋成本和额外费用。
添加税费 total += total * 0.2。
如果总花费 total 超过 money，则退出循环。
否则，增加 curry 的数量。
因为最后是超出之后才结束循环的，所以curry量需要-1.输出最后能购买的最大咖喱份数 curry - 1。
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int money = scanner.nextInt();
int curry = 1;
double total = 0;
if (money < 288) {
System.out.println(0);
} else {
while (true) {
total = 0;
if (curry % 2 == 0) {
double iceCream = curry / 2.0;
total += curry * 140 + iceCream * 70 + iceCream * 2 * 30;
}
if (curry % 2 == 1) {
double iceCream1 = curry / 2.0;
int iceCream = (int) Math.ceil(iceCream1);
total += curry * 140 + iceCream * 70 + iceCream1 * 2 * 30;
}
total += total * 0.2;
if (total > money) {
break;
}
curry++;
}
System.out.println(curry - 1);
}
scanner.close();
}
}
最小覆盖子串
题干
给定两个字符串 s 和 t，请你找出 s 中包含 t 中所有字符的最小子串。如果不存在这样的子串，则返回空字符串 ""。如果存在多个满足条件的子串，返回其中任意一个即可。
思路
典型的滑动窗口+字符串组合。
初始化：
使用两个指针 left 和 right 来表示当前窗口的左右边界。
使用一个哈希表 tCount 来记录字符串 t 中每个字符的出现次数。
使用另一个哈希表 windowCount 来记录当前窗口中每个字符的出现次数。
使用变量 requiredCount 来记录 t 中不同字符的数量。
使用变量 formedCount 来记录当前窗口中已经形成的字符数量。
使用变量 minLength 来记录最小窗口长度，并初始化为无穷大。
使用变量 start 来记录最小窗口的起始位置
扩展窗口：
移动右指针，将 s[right] 加入窗口，并更新当前窗口中每个字符的出现次数。
如果 s[right] 是 t 中的字符，并且 windowCount[s[right]] 等于 tCount[s[right]]，则增加当前窗口中已经形成的字符数量的计数量。
收缩窗口：
当 formedCount 等于 requiredCount 时，说明当前窗口包含了 t 中所有字符。
尝试收缩左指针 left，以寻找更小的窗口：
更新 minLength 和 start，如果当前窗口长度小于 minLength。
移除 s[left]，并更新 windowCount。
如果移除的字符 s[left] 是 t 中的字符，并且 windowCount[s[left]] 小于 tCount[s[left]]，则减少 formedCount。
增加左指针 left。
继续扩展窗口：
重复上述过程，直到右指针 right 达到字符串 s 的末尾。
返回结果：
如果 minLength 仍然是无穷大，说明没有找到符合条件的子串，返回空字符串。
否则，返回从 start 开始长度为 minLength 的子串。
参考代码
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0) {
return "";
}
Map<Character, Integer> tCount = new HashMap<>();
for (char c : t.toCharArray()) {
tCount.put(c, tCount.getOrDefault(c, 0) + 1);
}
int requiredCount = tCount.size();
int formedCount = 0;
Map<Character, Integer> windowCount = new HashMap<>();
int left = 0, right = 0;
int minLength = Integer.MAX_VALUE;
int start = 0;
while (right < s.length()) {
char rightChar = s.charAt(right);
windowCount.put(rightChar, windowCount.getOrDefault(rightChar, 0) + 1);
if (tCount.containsKey(rightChar) &&
windowCount.get(rightChar).equals(tCount.get(rightChar))) {
formedCount++;
}
while (left <= right && formedCount == requiredCount) {
char leftChar = s.charAt(left);
if (minLength > right - left + 1) {
minLength = right - left + 1;
start = left;
}
windowCount.put(leftChar, windowCount.get(leftChar) - 1);
if (tCount.containsKey(leftChar) &&
windowCount.get(leftChar) < tCount.get(leftChar)) {
formedCount--;
}
left++;
}
right++;
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
String t = scanner.nextLine();
Main solution = new Main();
String result = solution.minWindow(s, t);
if (result.isEmpty()) {
System.out.println("\"\"");
} else {
System.out.println(result);
}
scanner.close();
}
}
用辗转相除法求二元一次不定方程
题干
思路
读取输入：
从用户输入中读取三个长整型数 a, b, 和 c。
扩展欧几里得算法：
使用扩展欧几里得算法找到 ax + by = gcd(a, b) 的特解 (x, y)。
扩展欧几里得算法不仅计算最大公约数（GCD），还提供了一种方法来找到满足上述方程的一组特解。
检查是否有解：
根据数论中的性质，方程 ax + by = c 有整数解当且仅当 c 是 gcd(a, b) 的倍数。
如果 c % gcd(a, b) != 0，则方程无解，直接输出 "no" 并结束程序。
计算最终解：
计算乘数 g = c / gcd(a, b)。
最终解为 (x * g, y * g)。
输出结果：
输出计算得到的解 (x * g, y * g)。
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入
long a = scanner.nextLong();
long b = scanner.nextLong();
long c = scanner.nextLong();
// 声明变量来存储特解
long[] xy = new long[2];
long k = exGCDA(a, b, xy);
// 检查是否有解
if (c % k != 0) {
System.out.println("no");
return;
}
// 计算乘数
long g = c / k;
// 输出结果
System.out.println(xy[0] * g + " " + xy[1] * g);
scanner.close();
}
// 扩展欧几里得算法，返回 gcd(a, b) 并计算特解 (x, y)
private static long exGCDA(long a, long b, long[] xy) {
if (b == 0) {
xy[0] = 1; // x = 1
xy[1] = 0; // y = 0
return a;
}
long[] xy1 = new long[2];
long gcda = exGCDA(b, a % b, xy1);
xy[0] = xy1[1]; // x = y1
xy[1] = xy1[0] - (a / b) * xy1[1]; // y = x1 - (a / b) * y1
return gcda;
}
}正负之门
题干
在一个遥远的数学王国里，有一个被称为“正负之门”的神秘竞技场。这个竞技场由一位智慧而公正的裁判--一算术大师主持。算术大师手中掌握着无数非负整数，他将这些数字排列成一个数组 nums，并设定了一个特定的目标值 target 。 竞技场的参赛者们是王国中最聪明的算术家，他们被赋予了一项艰巨的任务:通过对数组 nums 中的每个数字前添加'+'或'-'，然后串联起所有整数，构造出一个表达式，使得这个表达式的运算结果恰好等于目标值 target。 算术大师规定，每个参赛者都可以尝试任意次数的组合，但每次组合都必须是全新的，即不允许重复计算已经尝试过的组合。参赛者们需要在限定时间内，找出所有可能满足条件的表达式，并统计它们的数量。
思路
背包+DP
理解问题:
我们可以将其转化为一个子集划分问题。
我们需要将数组 nums 分成两部分：一部分加正号，另一部分加负号。
设这两部分的和分别为 P 和 Q，则有：P+Q=sum(nums),P-Q=target.解方程得：P=(sum(nums)+target)/2.因此，问题转化为找到数组 nums 中的一个子集，其和为 P。
特殊情况处理：
如果 sum(nums) + target 是奇数，则无法找到这样的子集，直接返回 0。
如果 P 小于 0，则也无法找到这样的子集，直接返回 0。
动态规划初始化：
使用一个二维数组 cache 来记录中间结果，避免重复计算。
cache[i][j] 表示使用前 i 个数字凑出和为 j 的方法数。
递归函数 dfs：
定义一个递归函数 dfs，用于计算使用前 t 个数字凑出和为 c 的方法数。
如果 t < 0，检查当前和 c 是否为 0，如果是则返回 1，否则返回 0。
如果 cache[t][c] 已经计算过，则直接返回该值。
如果当前数字 nums[t] 大于 c，则不能选择这个数字，继续递归计算不选择的情况。
否则，递归计算选择和不选择当前数字的情况，并将结果存储在 cache[t][c] 中。
主函数：
读取输入的数组 nums 和目标 target。
计算 sum(nums) 和 P。
调用 findTargetSumWays 方法，返回结果。
参考代码
import java.util.Arrays;
import java.util.Scanner;
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
target = sum - target;
if (target < 0 || target % 2 != 0) {
return 0;
}
target /= 2;
int[][] cache = new int[nums.length][target + 1];
for (int[] row : cache) {
Arrays.fill(row, -1);
}
return dfs(nums, nums.length - 1, target, cache);
}
private int dfs(int[] nums, int t, int c, int[][] cache) {
if (t < 0) return c == 0 ? 1 : 0;
if (cache[t][c] != -1) return cache[t][c];
if (nums[t] > c) return cache[t][c] = dfs(nums, t - 1, c, cache);
else return cache[t][c] = dfs(nums, t - 1, c, cache) + dfs(nums, t - 1,
c - nums[t], cache);
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
int target = scanner.nextInt();
Solution solution = new Solution();
int result = solution.findTargetSumWays(nums, target);
System.out.println(result);
scanner.close();
}
}