【每日一题】【算法双周赛】【第 20 场 小白入门赛评价/分享】赛后另类AI写题分析分享

蓝桥云课 第 20 场 小白入门赛
首先看看 ：做题界面(如下图)和牛客很像

1. 四个亲戚【算法赛】

太简单的签到题就自己做了

在黛玉后加上'kind'就好，注意单引号也要加上即可

#include <iostream>
using namespace std;
int main()
{cout << "Daiyu'kind'";return 0;
}

2. 黛玉泡茶【算法赛】

有意思的就来了

本题用 AI 跑了一遍得到了以下结果

AI分析

这个问题可以用贪心算法来解决。我们需要尽量利用茶壶的容量去填满至少 K 个茶杯。为了实现这一点，我们可以按以下步骤进行：

1. 输入解析：首先，读取茶杯的数量 ( N )、茶壶的容量 ( M ) 和需要斟满的茶杯数量 ( K ) 以及每个茶杯的容量。

2. 排序：为了最小化茶壶的取水次数，我们应优先选择容量最大的茶杯。这样可以在每次取水时，尽量填满茶杯的同时减少取水次数。

3. 计算需要的水量：取出容量最大的 K 个茶杯，计算这些茶杯的总容量。然后根据茶壶的容量来计算需要的取水次数。

4. 输出结果：最后输出最少需要的取水次数。

具体实现

以下是Python的实现代码：

def min_water_pours(N, M, K, capacities):# Step 1: Sort the capacities in descending ordercapacities.sort(reverse=True)# Step 2: Take the largest K capacitiesrequired_capacities = capacities[:K]# Step 3: Calculate total tea neededtotal_tea_needed = sum(required_capacities)# Step 4: Calculate the minimum number of times to fill the teapot# If M is the capacity of the teapot, the number of fills required is:pours = (total_tea_needed + M - 1) // M  # This is equivalent to ceil(total_tea_needed / M)return pours# Sample Input
N, M, K = map(int, input().split())
capacities = list(map(int, input().split()))# Get the result and print it
result = min_water_pours(N, M, K, capacities)
print(result)

代码解析

1. 输入处理：通过 map 函数读取 N, M, K 和每个茶杯的容量。
2. 排序：使用 sort(reverse=True) 对容量进行降序排列，以确保我们先考虑最大容量的茶杯。
3. 计算所需总茶量：取出最大的 K 个茶杯的容量并求和。
4. 取水次数计算：利用整除和加法判断取水次数，(total_tea_needed + M - 1) // M 这个表达式是为了实现向上取整。

复杂度分析

• 时间复杂度：排序操作的复杂度为 ( O(N \log N) )，其余操作的复杂度为 ( O(N) )，所以整体的时间复杂度是 ( O(N \log N) )。
• 空间复杂度：只使用了常数空间来存储变量，除了输入容量数组外，空间复杂度为 ( O(N) )。

示例运行

对于样例输入：

2 3 1
5 7

程序会输出：

2

这表示黛玉最少需要用茶壶取水的次数为2次。

结果二

交上去然后显示答案错了
但稍微变动有一下就对了

def min_water_pours(N, M, K, capacities):# Step 1: Sort the capacities in descending ordercapacities.sort()# Step 2: Take the largest K capacitiesrequired_capacities = capacities[:K]# Step 3: Calculate total tea neededtotal_tea_needed = sum(required_capacities)# Step 4: Calculate the minimum number of times to fill the teapot# If M is the capacity of the teapot, the number of fills required is:pours = (total_tea_needed + M - 1) // M  # This is equivalent to ceil(total_tea_needed / M)return pours# Sample Input
N, M, K = map(int, input().split())
capacities = list(map(int, input().split()))# Get the result and print it
result = min_water_pours(N, M, K, capacities)
print(result)

3. 宝玉请安【算法赛】

依葫芦画瓢，AI结果

AI分析

为了帮助贾宝玉计算最少需要走多少步完成两次请安，我们可以采用以下步骤来解决这个问题：

问题分析

贾宝玉的位置和目标位置分别是：

• ( x_1 )：贾宝玉的初始位置（大观园正门）
• ( x_2 )：蘅芜苑的位置
• ( x_3 )：潇湘馆的位置

贾宝玉需要访问蘅芜苑和潇湘馆这两个位置。由于他可以选择先去蘅芜苑再去潇湘馆，或者先去潇湘馆再去蘅芜苑，因此我们需要计算这两种顺序的步数，并选择较小的结果。

路径计算

1. 从贾宝玉出发到蘅芜苑再到潇湘馆:

   • 步数 = ( |x_1 - x_2| + |x_2 - x_3| )

2. 从贾宝玉出发到潇湘馆再到蘅芜苑:

   • 步数 = ( |x_1 - x_3| + |x_3 - x_2| )

最终的最小步数为这两种路径步数中的较小者。

代码实现

接下来，我们将实现上述逻辑的 Python 代码：

def min_steps(t, test_cases):results = []for i in range(t):x1, x2, x3 = test_cases[i]# 计算两种路径的步数route1 = abs(x1 - x2) + abs(x2 - x3)route2 = abs(x1 - x3) + abs(x3 - x2)# 找到最小步数min_steps = min(route1, route2)results.append(min_steps)return results# 读取输入
t = int(input())
test_cases = [tuple(map(int, input().split())) for _ in range(t)]# 计算结果
results = min_steps(t, test_cases)# 输出结果
for result in results:print(result)

代码解析

1. 输入处理：首先读取测试用例的数量 ( t )，然后读取每个测试用例的三个位置 ( x_1 )，( x_2 )，( x_3 )。
2. 路径计算：
   • 对于每个测试用例，计算两种路径的步数。
   • 使用 abs 函数计算两个位置之间的距离。
   • 使用 min 函数找出两条路径中步数较小的那一条。
3. 输出结果：将计算结果输出。

示例运行

对于样例输入：

2
1 2 3
2 1 3

程序会输出：

2
3

复杂度分析

• 时间复杂度：每个测试用例的计算时间为 ( O(1) )，所以总时间复杂度为 ( O(t) )，其中 ( t ) 是测试用例的数量。
• 空间复杂度：只使用了常数空间来存储变量，因此空间复杂度为 ( O(1) )（不考虑输入输出的空间）。

通过这个实现，我们可以高效地为贾宝玉计算最少的步数，确保他顺利完成请安的任务。

结果： 交上去

好直接过了

后面的题AI一开始就过不去了(可能是用到的AI的问题)

4. 贾母祝寿【算法赛】

AI分析

为了解决这个问题，我们需要对 N 块玉石进行一系列的操作，并最终找出它们的最大亮度值。每块玉石的亮度值由其属性值的绝对值决定。由于 N 的最大值可以达到 (10^9)，我们不能直接为每块玉石分配空间或进行直接操作，因此需要采用一种优化的方法来处理这些操作。

问题分析

1. 操作类型：

   • 操作 1 (1 x y)：将前 x 块玉石的属性值增加 y。
   • 操作 2 (2 x y)：将后 x 块玉石的属性值减少 y。

2. 亮度值：每块玉石的亮度值是其属性值的绝对值。我们的目标是找出所有玉石中的最大亮度值。

3. 优化思路：

   • 我们不能直接操作 N 个玉石，但我们可以使用 前缀和 的思想来记录每次操作的影响。
   • 我们可以使用一个差分数组 delta 来记录操作的影响，具体步骤如下：
     • 对于增加操作，我们在 delta[0] 上加 y，在 delta[x] 上减 y（如果 x < N）。
     • 对于减少操作，我们在 delta[N - x] 上加 y，在 delta[N] 上减 y（以便于计算后续的值）。
   • 最后，我们计算每块玉石的实际属性值，并维护最大的绝对值。

实现步骤

1. 初始化一个差分数组 delta，其大小为 N + 1。
2. 读取每个操作并更新 delta 数组。
3. 遍历 delta 数组，计算最终的属性值，并找出最大亮度值。

代码实现

以下是解决该问题的 Python 代码：

def max_brightness(N, Q, operations):# 差分数组，用于记录变化delta = [0] * (N + 1)for operation in operations:t, x, y = operationif t == 1:# 对前 x 块增加 ydelta[0] += yif x < N:delta[x] -= yelif t == 2:# 对后 x 块减少 ydelta[N - x] += yif N > N - x + 1:delta[N] -= y# 计算最终的属性值并寻找最大亮度值max_brightness = 0current_value = 0for i in range(N):current_value += delta[i]max_brightness = max(max_brightness, abs(current_value))return max_brightness# 输入处理
N, Q = map(int, input().split())
operations = [tuple(map(int, input().split())) for _ in range(Q)]# 计算结果并输出
result = max_brightness(N, Q, operations)
print(result)

代码说明

• 差分数组 delta：
  • 我们用 delta 数组记录每个操作的影响，而不是直接操作每块玉石的属性值。
• 属性值计算：
  • 我们通过遍历 delta 数组，利用累积和的方式来计算每块玉石的最终属性值，并同时更新最大亮度值。

时间复杂度

• 每次操作时间复杂度为 ( O(1) )，总的操作时间复杂度为 ( O(Q) )。
• 计算最终属性值的时间复杂度为 ( O(N) )，但在实际实现中，由于我们仅需要关注最大亮度值，实际上可以在 ( O(Q) ) 时间内处理完成。

这种方法有效地处理了大规模数据，同时保持了高效性。

结果

调教了AI两次都没AC，放弃了

5. 清洁客房【算法赛】

AI分析

为了计算符合条件的客房清洁方案数量，我们需要理解题目中的约束条件和计算逻辑。根据题意，方案需要满足以下几点：

1. 清洁等级：使用的清洁等级必须是三种不同的等级，且必须包括至少等级 1 的清洁。
2. 客房数量：给定 n 间客房的数量，清洁等级需要分配到这些客房中。

解决思路

1. 确定条件

• 首先，若 n < 3，则无法分配三种不同的清洁等级，因此方案数为 0。
• 对于 n >= 3 的情况，三个等级可以取值在 0 到 9 之间，但必须确保有等级 1。

2. 组合数计算

• 我们可以选择三种不同的等级，其中 1 是必选的。我们可以选择其他两个等级 x 和 y（其中 x 和 y 可以是 0 到 9 之间的任意值，但不能与 1 相同）。

  • 可选等级为 0, 2, 3, 4, 5, 6, 7, 8, 9，这总共是 9 种选择。

• 从这 9 种中选择 2 种，组合数为 ( C(9, 2) )。

3. 排列数计算

• 一旦选择了 1 和另外两个等级（比如 x 和 y），我们需要计算将这些等级分配到 n 间客房的不同方式。

• 这个分配问题转化为 非负整数解 的问题，我们可以使用 “星与条” 方法进行计算：

  • 设 k1 是等级 1 的数量，k2 是等级 x 的数量，k3 是等级 y 的数量，则 k1 + k2 + k3 = n，且 k1 >= 1（至少一间客房使用等级 1）。

  • 通过将 k1 减去 1，变换为：k1' + k2 + k3 = n - 1，其中 k1' = k1 - 1，且 k1' >= 0。

• 使用组合数公式，解的数量为：
  [
  C(n-1 + 2, 2) = C(n + 1, 2)
  ]

4. 综合计算

• 对于每种选择的 x 和 y，方案总数为：
  [
  C(9, 2) \times C(n + 1, 2)
  ]

5. 计算的具体步骤

1. 计算组合数 ( C(9, 2) = 36 )。
2. 对于每个测试用例，计算 ( C(n + 1, 2) )。
3. 输出结果的模 ( 10^9 + 7 )。

实现代码

以下是实现上述逻辑的 Python 代码：

def mod_comb(n, k, MOD):if k > n:return 0# 计算 n! / (k! * (n-k)!) % MODnumerator = 1denominator = 1for i in range(k):numerator = (numerator * (n - i)) % MODdenominator = (denominator * (i + 1)) % MOD# 使用 Fermat's Little Theorem to find the modular inversereturn numerator * pow(denominator, MOD - 2, MOD) % MODdef calculate_solutions(t, cases):MOD = 10**9 + 7results = []# C(9, 2) = 36comb_9_2 = 36for n in cases:if n < 3:results.append(0)else:comb_n_1_2 = mod_comb(n + 1, 2, MOD)result = (comb_9_2 * comb_n_1_2) % MODresults.append(result)return results# 输入处理
t = int(input())
cases = [int(input()) for _ in range(t)]# 计算并输出结果
results = calculate_solutions(t, cases)
for res in results:print(res)

说明

• 函数 mod_comb 用于计算组合数，并通过费马小定理计算逆元来处理模运算。
• 函数 calculate_solutions 计算每个测试用例的结果。
• 处理输入输出，符合题目要求。

结果

没过

6. 宝玉与黛玉的考验【算法赛】

AI分析

为了找到最大可分配的土地数量，我们需要分析给定的输入，找出在任意 k × k 方格中可分配的土地的数量。一个土地 (i, j) 被称为可分配的当且仅当它满足以下条件：

• 该土地仅被宝玉或黛玉其中一人所喜爱，即：
  • ( S[i] = 1 ) 且 ( T[j] = 0 ) 或
  • ( S[i] = 0 ) 且 ( T[j] = 1 )

步骤

1. 解析输入：读取 n、m、k、字符串 S 和 T。
2. 计算可分配土地的数量：
   • 构建一个 n × m 的矩阵，其中每个元素表示对应的土地是否可分配（1 为可分配，0 为不可分配）。
3. 使用前缀和：
   • 使用前缀和数组来高效地计算任意 k × k 方格内的可分配土地数量。
4. 滑动窗口计算：
   • 通过遍历可能的 k × k 方格的左上角，利用前缀和快速计算可分配的土地数量，更新最大值。

代码实现

以下是解决该问题的 Python 代码：

def max_allocatable_land(n, m, k, S, T):# 构建可分配土地矩阵allocatable = [[0] * m for _ in range(n)]for i in range(n):for j in range(m):# 计算可分配条件if (S[i] == '1' and T[j] == '0') or (S[i] == '0' and T[j] == '1'):allocatable[i][j] = 1# 计算前缀和prefix_sum = [[0] * (m + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, m + 1):prefix_sum[i][j] = (allocatable[i - 1][j - 1]+ prefix_sum[i - 1][j]+ prefix_sum[i][j - 1]- prefix_sum[i - 1][j - 1])# 找到最大的k x k方格内的可分配土地数量max_land = 0for i in range(k, n + 1):for j in range(k, m + 1):# 计算k x k 方格的总和total_allocatable = (prefix_sum[i][j]- prefix_sum[i - k][j]- prefix_sum[i][j - k]+ prefix_sum[i - k][j - k])max_land = max(max_land, total_allocatable)return max_land# 输入处理
n, m, k = map(int, input().split())
S = input().strip()
T = input().strip()# 计算结果并输出
result = max_allocatable_land(n, m, k, S, T)
print(result)

代码说明

1. 可分配矩阵构建：首先根据 S 和 T 的定义构建一个 allocatable 矩阵，该矩阵表示每一块土地是否可分配。
2. 前缀和数组：构建前缀和数组 prefix_sum，使得我们可以在常数时间内计算任何 k × k 方格内的可分配土地数量。
3. 滑动窗口：遍历所有可能的 k × k 方格，使用前缀和计算每个方格内的可分配土地数量，并维护最大值。

时间复杂度

• 构建 allocatable 矩阵的时间复杂度为 ( O(n \times m) )。
• 构建前缀和的时间复杂度为 ( O(n \times m) )。
• 计算所有 k × k 方格的总和的时间复杂度为 ( O((n - k + 1) \times (m - k + 1)) )。

总的时间复杂度为 ( O(n \times m) )，适合 ( n, m \leq 200,000 ) 的范围。

结果

超过内存限制

整体评价

AI能写说明前面的简单题比较经典，并且适合新手来练手
后面AI给的就是错的，也说明了题目设计严谨，测试样例全面或者有设坑，需要自行破解，也能体现比赛的严谨性。

后面看了一下出题人
二、本场比赛信息
出题人：执梗（CSDN 粉丝6W+，蓝桥杯 C++、Java、Python 三组别国一，CCPC铜牌，省赛银牌）。
验题人：1.小羊肖恩（北京大学在读，保研本校，力扣全球排名第 6，竞赛分 3496，第十五届蓝桥杯 Python 研究生组全国冠军）；2.阿坤老师（蓝桥杯国一，Codeforces 橙名）；3.吴林苗（蓝桥杯国一，codeforces紫名，icpc铜牌）

本比赛的奖励

蓝桥云课在每个区段都设置了奖励，实力大佬甚至能有更好的奖励，如果你喜欢的话可以来试试

更多计算机相关的蓝桥云课比赛