说明
此文仅为作者的个人见解，原题链接：https://www.lanqiao.cn/oj-contest/newbie-28/
总结
- 这是蓝桥杯省赛前蓝桥官方的最后一次比赛所以很简单，基本都是一些语法问题。其中1--2题太过语法，所以就不展示了。要多熟练cpp种STL的运用。
3.蓝桥速算
题目描述
- 蓝桥杯大赛最近新增了一项娱乐比赛——口算大赛，目的是测试选手的口算能力。比赛规则如下：初始给定一个长度为 N 的数组 A，其中第 i 个数字为 Aᵢ。随后数组会被隐藏，并进行 Q 次值域变换操作。
每次操作给出两个数字 L,R (1 ≤ L ≤ R ≤ N)，表示对子数组 [L,R] 进行如下变换：
A[L] 增加 L
A[L+1] 减少 (L+1)
A[L+2] 增加 (L+2)
A[L+3] 减少 (L+3)
以此类推，直到 R
在所有操作完成后，选手需要快速计算出最终的数组之和，最快回答出正确答案的选手将会获得奖励。
- 输入：
第一行输入两个整数 N,Q (1 ≤ N,Q ≤ 10⁵) 表示数组长度和值域变换操作次数。第二行输入 N 个整数 A₁,A₂,A₃,⋯,A_N (1 ≤ Aᵢ ≤ 10⁵) 表示数组的初始值。接下来 Q 行，每行两个整数 L,R (1 ≤ L ≤ R ≤ N) 表示一次值域变换操作。 - 输出：
输出一个整数，表示值域变换操作完毕后数组之和。
示例
- 输入：
5 2
1 2 3 4 5
1 3
4 5 - 输出：
16
思路
- 前缀和。观察规律：i为奇数时，有L富余。相反i为偶数的时候L会全部抵消掉。其余的数字按照摆动数列求和规律求和即可。时间复杂度：O(n).
代码
void solve()
{
int n , q;
cin >> n >> q;
vector<int> a(n + 1);
int ans = 0;
for (int i = 1 ; i <= n ; i ++ ) cin >> a[i] , ans += a[i];
while (q -- )
{
int l , r;
cin >> l >> r;
int num = r - l + 1;
if (num & 1) ans += l + num / 2;
else ans -= num / 2;
}
cout << ans << endl;
}
4.浓缩咖啡液
题目描述
- 蓝桥杯备赛选手小蓝最近刷题刷到犯困，决定靠咖啡续命。他手上有 N 种浓缩咖啡液，浓度分别是 A₁%, A₂%, ..., A_N%，每种存货都是无限的。为了提神又不炸脑，小蓝需要按比例混合这些浓缩咖啡液，调出一杯浓度为 M% 的咖啡。
- 输入格式：
第一行包含一个整数 T（1 ≤ T ≤ 10³），表示测试数据的组数。接下来的每组数据包含两行：第一行包含两个整数 N 和 M（1 ≤ N,M ≤ 100），分别表示浓缩咖啡液的种类数和目标浓度第二行包含 N 个整数 A₁,A₂,...,A_N（1 ≤ A_i ≤ 100），表示每种浓缩咖啡液的浓度
- 输出格式：
对于每组测试数据，输出一行：如果可以调出浓度为 M% 的咖啡，输出 YES否则输出 NO
示例
- 输入：
2
1 90
20
2 60
50 70 - 输出：
NO
YES - 说明：
第一组测试数据：只有一种浓度为20%的咖啡液无法调出90%的咖啡（只能得到20%）输出NO
第二组测试数据：
有两种浓度：50%和70%
可以按1:1比例混合得到60%的咖啡
输出YES
思路
- 思维题。可调制的浓度范围一定是大于等于已有的最小的浓度而小于等于已有的最大的浓度。找到最大最小比较之后符合条件即可。时间复杂度：O(n).
代码
void solve()
{
int n , m;
cin >> n >> m;
int temp1 = -1 , temp2 = 0x3f3f3f3f;
for (int i = 1 ; i <= n ; i ++ )
{
int temp;
cin >> temp;
temp1 = max(temp1 , temp);
temp2 = min(temp2 , temp);
}
if (m < temp2 || m > temp1) cout << "NO" << endl;
else cout << "YES" << endl;
}
5.破译密码
题目描述
- 在近期举办的蓝桥杯竞赛中，诞生了一场激动人心的双人破译挑战。比赛的主办方准备了 N 块神秘的密码芯片，参赛队伍需要在这场智力竞赛中展示团队合作的默契与效率。每个队伍需选出一位破译者与一位传输者：破译者的任务是解锁芯片中隐藏的密码
传输者则负责将解密后的密码准确无误地发送至主办方的电脑
小蓝与小桥组队参赛：
小蓝被任命为破译者，专注于解密每一块密码芯片
小桥担任传输者，负责信息传输
- 输入格式：
第一行输入一个整数 N (1 ≤ N ≤ 1000) 表示芯片数量。第二行输入 N 个整数 A₁,A₂,A₃,⋯,A_N (1 ≤ A_i ≤ 10³) 表示小蓝破译每块芯片的时间。第三行输入 N 个整数 B₁,B₂,B₃,⋯,B_N (1 ≤ B_i ≤ 10³) 表示小桥传输每块芯片密码的时间。 - 输出格式：
输出一个整数表示完成所有密码芯片破译与传输所需的最短时间。
示例
- 输入：
4
1 3 5 7
6 5 1 4 - 输出：
17 - 说明：
两人可以按照 (1,2,4,3) 的芯片编号顺序进行破译传输：破译芯片1 (1单位时间)传输芯片1 (6单位时间) 同时破译芯片2 (3单位时间)传输芯片2 (5单位时间) 同时破译芯片4 (7单位时间)
传输芯片4 (4单位时间) 同时破译芯片3 (5单位时间)
传输芯片3 (1单位时间)
总时间为1 + max(6,3) + max(5,7) + max(4,5) + 1 = 17
思路
- Johnson算法思路，或者说是一种贪心思路。中心就是不要让b等或者说不要让b闲下来。排序使得a小而b长的优先做，保证b一直都有事情做。因为a必须先做，b才能做。时间复制度:O(nlogn)。
代码
void solve()
{
int n;
cin >> n;
vector<PII> a(n + 1);
for (int i = 1 ; i <= n ; i ++ ) cin >> a[i].first;
for (int i = 1 ; i <= n ; i ++ ) cin >> a[i].second;
sort(all(a) , [](const auto& e1 , const auto& e2){
if (e1.first <= e1.second && e2.first > e2.second)
return true;
if (e2.first <= e2.second && e1.first > e1.second)
return false;
if (e1.first <= e1.second)
return e1.first < e2.first;
else return e1.second > e2.second;
});
int ans = 0, t = 0;
for (int i = 1 ; i <= n ; i ++)
t += a[i].first, ans = max(ans, t) + a[i].second;
cout << ans << endl;
}
6.插入数字
题目描述
- 在备战蓝桥杯的过程中，小蓝对数字变换的技巧产生了浓厚的兴趣。给定一个正整数 N，可以通过以下操作生成新数字：在 N 的开头插入一个数字（0-9）在 N 的结尾插入一个数字（0-9）
在 N 的任意两个相邻数字之间插入一个数字（0-9）
注意：生成的新数字不能以 0 开头。
- 输入格式：
输入包含一个正整数 N（1 ≤ N ≤ 10¹⁸），即给定的正整数。 - 输出格式：
输出一个整数，表示通过插入操作能得到的不同数字的种类数。
示例
- 输入：9
- 输出：18
- 说明：
能得到的不同数字有：
19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99
思路
- 找规律(数据很水)。在长度为n的整数中插入一个数字，一共有n + 1 个空位，由排列组合的知识，一共有(n + 1) * 9种方法。时间复杂度O(1).
- 枚举+set去重。枚举每一个n + 1 个位置 依次加入0--9这几个数字(开头为不能加0) 存入set去重。
最后set的容量即为答案数量。时间复杂度O(n²).
代码
规律
void solve()
{
string s;
cin >> s;
int n = s.size();
cout << (n + 1) * 9 << endl;
}
正解
void solve()
{
string s;
cin >> s;
int n = s.size();
set<string> st;
for (int i = 0 ; i <= n ; i ++ )
{
for (char c = '0' ; c <= '9' ; c ++ )
{
if (i == 0 && c == '0') continue;
string str = s.substr(0 , i) + c + s.substr(i);
st.insert(str);
}
}
cout << st.size() << endl;
}
Comments NOTHING