保定学院寒假第一次训练赛题解 感谢各位参加这次比赛
目录
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 tCount = new HashMap();
for (char c : t.toCharArray()) {
tCount.put(c, tCount.getOrDefault(c, 0) + 1);
}
int requiredCount = tCount.size();
int formedCount = 0;
Map 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 - 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();
}
}