第 28 场 蓝桥月赛

分享一下我的做题思路和感受，赛时成绩如下。

月赛链接如下：第 28 场 蓝桥月赛 - 蓝桥云课 

1. 发射火箭 

问题描述

在“银河系最奇葩航天局”，实习生小明被派去发射一枚超级火箭。控制室里有个花里胡哨的仪表盘，上面有红、黄、蓝、绿四个按钮。局长叉着腰，得意洋洋地说：“小蓝，发射火箭超级简单！按红按钮 123 次，黄按钮 456 次，蓝按钮 789 次，顺序随便，火箭就能嗖嗖飞上天！”

小明一听，摩拳擦掌，心想：“这不就是体力活嘛？我小时候玩跳舞机都没这么带劲！”可就在他准备大干一场时，同事小刚一脸坏笑地凑过来：“小明，别急！局长忘了告诉你，黄按钮昨天被他按坏了哈哈。不过别慌，咱们还有个绿按钮，它可厉害了！按一次绿按钮，等于同时按了一次黄按钮和一次蓝按钮！”

现在，请你帮小明分析，要想成功发射火箭，他最少需要按多少次按钮？

 解题思路：按456次绿色按钮等价于456次黄色按钮, 456次蓝色按钮, 还需要(789-456)次蓝色按钮和123次红色按钮，最后结果为912

#include <iostream>
using namespace std;
int main()
{cout<<912<<endl;return 0;
}

2.燃油交换 

问题描述

小蓝是一名宇宙飞船的航行舰长，正执行从星球 X 飞往星球 Y 的任务。根据预计的行程时间，他需要在 N 天内完成这次航行。飞船的动力来源于两种燃油：A 和 B。然而，每一天的路况不同，导致燃油的消耗量也有所变化。

对于每一天 i，使用燃油 A 的消耗量为 Ai​，而使用燃油 B 的消耗量则为 Bi​。小蓝可以在旅程开始前随意选择一种燃油，并且在航行的某一天进行一次燃油替换。

现在，小蓝希望计算出在这趟旅程中，飞船最少需要消耗多少燃油。

注意：替换操作最多只能进行一次。

输入说明

第一行包含一个整数 N(1≤N≤105)，表示航行的天数。

第二行包含 N 个整数A1​,A2​,…,AN​(1≤Ai​≤109)，表示使用燃油 A 的每日消耗量。

第三行包含 N 个整数 B1​,B2​,…,BN​(1≤Bi​≤109)，表示使用燃油 B 的每日消耗量。

输出格式

输出一个整数，表示飞船在这趟旅程中最少需要消耗的燃油量。

解题思路：枚举分割点, 一种情况是数组A的前i个和数组B后N-i个进行组合, 另一种情况是数组B的前i个和数组A的后N-i个进行组合, 然后两者取最小值即可 

#include <bits/stdc++.h>
using namespace std;
int main() {int N;cin >> N;vector<long long> A(N + 1), B(N + 1);vector<long long> prefixA(N + 1, 0), prefixB(N + 1, 0);for (int i = 1; i <= N; i++) {cin >> A[i];}for (int i = 1; i <= N; i++) {cin >> B[i];}for (int i = 1; i <= N; i++) {prefixA[i] = prefixA[i - 1] + A[i];prefixB[i] = prefixB[i - 1] + B[i];}long long totalNumA = prefixA[N];long long totalNumB = prefixB[N];long long ans = LLONG_MAX;for (int i = 0; i <= N; i++) {ans = min(ans, prefixA[i] + (totalNumB - prefixB[i]));ans = min(ans, prefixB[i] + (totalNumA - prefixA[i]));}cout << ans;return 0;
}

3. 训练反应力 

问题描述

小蓝正在努力成为一名航空员，这需要他锻炼出足够的反应力。

他来到一台用来训练反应力的机器前，训练的规则如下：小蓝可以选择在 NN 个时间节点进行攻击。在某个时间节点 X 攻击机器后，机器将在 X+D 节点反击小蓝。此时，小蓝需要躲避，如果被机器击中，任务将失败。

小蓝无法在同一时间节点同时进行攻击和躲避。他想知道，在确保任务成功的前提下，自己最多能攻击机器多少次。

输入格式

第一行包含两个整数 N ,D(1,≤N≤105,1≤D≤109)，分别表示时间节点的数量和机器反击的延迟。

第二行包含 N个整数 Ai​(1≤A1​<A2​<A3​<⋯<AN​≤109)，表示时间节点的具体值。

输出格式

输出一个整数，表示小蓝在确保任务成功的前提下，最多能攻击机器的次数。

 

解题思路： 按顺序模拟题意, 当遍历到当前值i的时候, 你就将i+D进行标记，这个点是躲闪攻击

#include <bits/stdc++.h>
using namespace std;int main() {int N;long long D;cin >> N >> D;vector<long long> A(N);      unordered_map<int,int> mp;for (int i = 0; i < N; ++i) {cin >> A[i];mp[A[i]]=1;}int ans=0;for(int i=0;i<N;i++){if(mp[A[i]]){ans++;mp[A[i]+D]=0;}}cout<<ans<<endl;return 0;
}

4.最佳航线 

问题描述

航天工程师小蓝正在为月球探测器设计最佳航线。地球到月球的航程被分为 N 个阶段，地球位于第 1 阶段，月球位于第 N 阶段。在第 i 个阶段（1≤i<N），探测器可以进行一次“空间跳跃”，跳跃到 i+1,i+2,…,Ai​ 中的任意一个阶段。

为了节省燃料，小蓝希望用最少的跳跃次数抵达月球。现在，请你帮助小蓝计算出探测器从地球（阶段 1）到月球（阶段 N）所需的最少跳跃次数。

输入格式

第一行包含一个整数 N（2≤N≤10^5），表示航程的阶段数。

第二行包含 N−1 个整数 A1​,A2​,…,AN−1​（i<Ai​≤N），其中 Ai​ 表示在第 i个阶段，探测器最多可以跳跃到的阶段。

输出格式

输出一个整数，表示探测器从地球到月球所需的最少跳跃次数。

解题思路：按顺序进行贪心, 在当前位置可以跳到[i+1,Ai]的任意位置, 这个区间在当前位置都是可以跳到的, 为了保证跳跃次数最少, 我们在遍历区间的同时去维护一个最大值c

#include <bits/stdc++.h>
using namespace std;
int main() {int N;cin >> N;vector<int> A(N + 1);for (int i = 1; i < N; ++i) {cin >> A[i];}int a = 0;int b = 1;int c = 1;for (int i = 1; i < N; ++i) {c = max(c, A[i]);if (i == b) {++a;b = c;if (b >= N) break;}}cout <<a<<endl;return 0;
}

5. 航天梦

 

问题描述

小蓝从小梦想成为宇航员，但因体质原因未能实现梦想。他转而钻研编程，最终成为航天总局的程序员，负责为火箭设计轨道计算程序。近期，他接到一项关键任务：火箭在飞行过程中记录了 N 个实验数据，反映不同阶段的轨道参数。为了优化火箭控制系统，小蓝需要计算这些数据两两异或（XOR）值的乘积。

具体来说，给定一个长度为 N 的整数数组 A，其中 Ai 表示第 i 个实验数据的数值。你需要计算所有可能的两两数据组合的异或值乘积，即：∏1≤i<j≤N(Ai⊕Aj)1≤i<j≤N∏​(Ai​⊕Aj​)

由于答案可能很大，请你将答案对 10^9+7 取模后输出。

输入说明

第一行包含一个整数 N（2≤N≤10^5），表示实验数据的数量。

第二行包含 N 个整数 A1​,A2​,…,AN​(1≤Ai​≤3×10^3），表示每个实验数据的数值。

输出格式

输出一个整数表示答案，答案需要对 10^9+7 取模后输出。

解题思路：求两两数异或和的乘积,  根据XOR的性质, 相同两数的XOR为0. Ai的取值范围是[1,3x10^3], 所以当N的数量超过3000的时候, XOR和就为0了, 所以实际数据范围是10^6左右, 

所以直接O(n^2)即可

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int MAX = 3000;
int main() {int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; i++) {cin >> A[i];}vector<int> fq(MAX + 1, 0);for (int x : A) {if (fq[x]++ > 1) {cout << 0;return 0;}}vector<int> b;for (int x = 1; x <= MAX; x++) {if (fq[x]) b.push_back(x);}long long res = 1;int M = b.size();for (int i = 0; i < M; i++) {for (int j = i + 1; j < M; j++) {int tmp= (b[i] ^ b[j]);res = res * tmp % MOD;}}cout << res <<endl;return 0;
}

 6.吃零食训练 

问题描述

小蓝是一名航天工程师，同时也是一名狂热的算法竞赛爱好者。最近，他正在为即将到来的星际航天竞赛做准备。为了更好地模拟太空中的复杂环境，小蓝设计了一套独特的训练方案。他准备了三种不同类型的太空零食：能量棒、压缩饼干和蛋白质胶囊，分别用 0、1 和 2 来表示。其中，能量棒有 A 个，压缩饼干有 B 个，蛋白质胶囊有 C 个。每次训练，小蓝会从剩余的零食中选择两种吃掉，并根据吃掉的零食类型计算训练得分。如果吃掉的两种零食分别是 x 和 y，那么本次训练的得分就是 (x+y)mod3。小蓝需要不断地进行训练，直到剩余的零食数量小于等于 1。

由于太空任务的特殊性，小蓝必须尽可能地提高训练效率，以适应各种突发情况。因此，他希望在训练过程中获得的总得分尽可能高。

现在，请你帮助小蓝计算，在最优的训练策略下，他能够获得的最高总得分是多少？

输入格式

第一行包含一个整数 T（1≤T≤10^5），表示测试用例的数量。

接下来 T 行，每行包含三个整数 A、B 和 C（1≤A,B,C≤10^9），分别表示能量棒、压缩饼干和蛋白质胶囊的数量。整数之间用空格分隔。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示小蓝在最优训练策略下能够获得的最高总得分。

解题思路：优先配对A和C, 一次2分,  其次配对B和B ,一次得 2 分, 再就是配对A和B，一次得1分，最后就是配对C和C，一次得1分

#include <bits/stdc++.h>
using namespace std;
int main(){int T;cin >> T;while(T--){long long A,B,C;cin >> A >> B >> C;long long a = min(A, C);A -= a; C -= a;long long b = B / 2;B -= b * 2;long long score = 2 * (a + b);long long d = min(A, B);A -= d; B -= d;long long c = C / 2;C -= c * 2;score += d + c;cout << score << endl;}return 0;
}

题目整体上没那么难,  希望我的讲解对你有用。

最后，感谢大家的点赞和关注，你们的支持是我创作的动力！