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

第 20 场 小白入门赛

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

1. 四个亲戚【算法赛】

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

在黛玉后加上

'kind'

就好，注意单引号也要加上即可

#include<iostream>usingnamespace std;intmain(){
  cout <<"Daiyu'kind'";return0;}

2. 黛玉泡茶【算法赛】

有意思的就来了

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

AI分析

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

1. 输入解析：首先，读取茶杯的数量 ( N )、茶壶的容量 ( M ) 和需要斟满的茶杯数量 ( K ) 以及每个茶杯的容量。
2. 排序：为了最小化茶壶的取水次数，我们应优先选择容量最大的茶杯。这样可以在每次取水时，尽量填满茶杯的同时减少取水次数。
3. 计算需要的水量：取出容量最大的 K 个茶杯，计算这些茶杯的总容量。然后根据茶壶的容量来计算需要的取水次数。
4. 输出结果：最后输出最少需要的取水次数。

具体实现

以下是Python的实现代码：

defmin_water_pours(N, M, K, capacities):# Step 1: Sort the capacities in descending order
    capacities.sort(reverse=True)# Step 2: Take the largest K capacities
    required_capacities = capacities[:K]# Step 3: Calculate total tea needed
    total_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次。

结果二

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

defmin_water_pours(N, M, K, capacities):# Step 1: Sort the capacities in descending order
    capacities.sort()# Step 2: Take the largest K capacities
    required_capacities = capacities[:K]# Step 3: Calculate total tea needed
    total_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 代码：

defmin_steps(t, test_cases):
    results =[]for i inrange(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 _ inrange(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 代码：

defmax_brightness(N, Q, operations):# 差分数组，用于记录变化
    delta =[0]*(N +1)for operation in operations:
        t, x, y = operation
        if t ==1:# 对前 x 块增加 y
            delta[0]+= y
            if x < N:
                delta[x]-= y
        elif t ==2:# 对后 x 块减少 y
            delta[N - x]+= y
            if N > N - x +1:
                delta[N]-= y

    # 计算最终的属性值并寻找最大亮度值
    max_brightness =0
    current_value =0for i inrange(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 _ inrange(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 代码：

defmod_comb(n, k, MOD):if k > n:return0# 计算 n! / (k! * (n-k)!) % MOD
    numerator =1
    denominator =1for i inrange(k):
        numerator =(numerator *(n - i))% MOD
        denominator =(denominator *(i +1))% MOD
    # 使用 Fermat's Little Theorem to find the modular inversereturn numerator *pow(denominator, MOD -2, MOD)% MOD

defcalculate_solutions(t, cases):
    MOD =10**9+7
    results =[]# C(9, 2) = 36
    comb_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)% MOD
            results.append(result)return results

# 输入处理
t =int(input())
cases =[int(input())for _ inrange(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 代码：

defmax_allocatable_land(n, m, k, S, T):# 构建可分配土地矩阵
    allocatable =[[0]* m for _ inrange(n)]for i inrange(n):for j inrange(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 _ inrange(n +1)]for i inrange(1, n +1):for j inrange(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 inrange(k, n +1):for j inrange(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铜牌）

本比赛的奖励

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

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