[ 蓝桥 ·算法双周赛 ] 第 19 场 小白入门赛

🔥博客介绍`： EvLast

🎥系列专栏： <<数据结构与算法>> << 算法入门>> << C++项目>>

🎥 当前专栏: << 算法入门>>

专题 : 帮助小白快速入门算法竞赛
👍👍👍👍👍👍👍👍👍👍👍👍
☆*: .｡. o(≧▽≦)o .｡.:*☆

❤️感谢大家点赞👍收藏⭐评论✍️

算法竞赛：第 19 场 小白入门赛

今日学习打卡

• 蓝桥 ·算法双周赛 题解

---

题解内容：

1. 上交文物

题目考点: 语法

解题思路

解题思路: 根据语言直接输出 注意向下取整

代码

#include <bits/stdc++.h>
using ll = long long;void solve(int T) {std::cout << 5000 / 3 << "\n";
}int main()
{std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);int T; //std::cin >> T;T = 1;for (int i = 1; i <= T; i++) solve(T);return 0;
}

---

2. 打开石门

题目考点: 字符串 模拟

解题思路

根据方法可知解题需要选定一个机关字符 并 合并相同的机关字符 由此我们则需遍历字符串 用 n 记录机关字符为 L 的值, 用 m 记录 机关字符为Q 的值, 并筛选出最小的即可

代码

#include <bits/stdc++.h>
using ll = long long;void solve(int T) {//输入数据std::string s; std::cin >> s;//存储变量值 n,m 分别记录L, Q的机关字符的值ll n = (ll)s.size() , m = n , ans = n;// 对应循环遍历for(int j = 0; j < (int)s.size() - 1; j++) {//如果有相同者合并if(s[j] == 'L' && s[j + 1] == 'L') {n--;}if(s[j] == 'Q' && s[j + 1] == 'Q') {m--;}}// 筛选出最小值ans = std::min(n, m); std::cout << ans << "\n";
}int main()
{std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);int T = 1; //std::cin >> T;for (int i = 1; i <= T; i++) solve(i);return 0;
}

---

3. 青铜门上的涂鸦

题目考点: 字符串 模拟

解题思路

此题要点即 判断出四种情况, 然后根据情况, 进行记录值 注意 : QQ因为题目要求不同的数量,将QQ替换成QQ也是一个创作数量

代码

#include <bits/stdc++.h>
using ll = long long;void solve(int T) {std::string s;std::cin>> s;s = "L" + s;int ans = 0;for(int i = 2; i < (int)s.size(); i++) {if(s[i] == 'L') ans++;else if(s[i - 1] == s[i - 2] && s[i - 1] == 'L') ans++;}if(s.find("QQ") != std::string::npos) ans++;std::cout << ans << "\n";
}int main()
{std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);int T = 1; //std::cin >> T;for (int i = 1; i <= T; i++) solve(i);return 0;
}

纯暴力 30% 代码

#include <bits/stdc++.h>
using ll = long long;void solve(int T) {std::string s; std::cin >> s;int ans = 0; std::unordered_map<std::string, int> mp;for(int j = 0; j < (int)s.size() - 1; j++) {std::string t(s);t[j] = 'Q';t[j + 1] = 'Q';mp[t]++;}std::cout << mp.size() << "\n";
}int main()
{std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);int T; //std::cin >> T;T = 1;for (int i = 1; i <= T; i++) solve(i);return 0;
}

---

4. 敲打骷髅兵

题目考点: 模拟 数学

解题思路

这题比上一题更简单, 敲打一个骷髅并骷髅兵的数量会成倍增加, 指数级增加直到 血条 n 为 0为止, 因为向下取整所以当 n == 1时候即最后一次 。

代码

#include <bits/stdc++.h>
using ll = long long;void solve(int T) {int n,cnt=0;std::cin>>n;while(n) n/=2,cnt++;std::cout << (long long) std::pow(2,cnt) - 1 << "\n";
}int main()
{std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);int T; std::cin >> T;for (int i = 1; i <= T; i++) solve(i);return 0;
}

---

5. 净化王胖子

题目考点: 模拟 数学

解题思路

根据题目要求从最暴力的方式入手建立起模型, 使用差分的方法

代码

#include <bits/stdc++.h>
using ll = long long;int a[200005], b[200005];void solve(int T) {int n, k, x, sum = 0, t;std::cin >> n>>k;for (int i=1; i<=n; i++) std::cin>>x, a[x] = i;for (int i=1; i<=n-1; i++) b[std::min(a[i],a[i+1])]++, b[std::max(a[i],a[i+1])]--;for (int i=1; i<=n-1; i++)t = b[i], b[i] += sum, sum += t;std::sort(b+1, b+1+n-1, std::greater<int>());sum = 0;for (int i=1; i<=n-1; i++) {sum += b[i];if (sum >= k) {std::cout<<i<<'\n';return ;}}std::cout<<-1<<'\n';
}int main()
{std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);int T = 1; //std::cin >> T;for (int i = 1; i <= T; i++) solve(i);return 0;
}

---

6. 云顶天宫

题目考点: 思维 动态规划

解题思路

此题根据题解可知需要使用组合数学与dp

参考代码

#include <iostream>
using namespace std;
const int M = 998244353;
const int N = 1005;
// 线性求逆元 求阶乘逆元
long long f[N], inv[N], finv[N];void init(int n) {f[0] = f[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1;for (int i=2; i<=n; i++) {f[i] = f[i-1] * i % M;inv[i] = (M - M/i) * inv[M%i] % M;finv[i] = finv[i-1] * inv[i] % M;}
}
// 求组合数逆元
long long C(int n, int m) {if (m > n)return 0;if (m == 0 || m == n)return 1;return f[n] * finv[m]%M * finv[n-m]%M;
}long long pow(long long a, int k) {if (k == 0)return 1;if (k%2)return pow(a*a%M, k/2)*a%M;elsereturn pow(a*a%M, k/2);
}int main() {int n,m;cin>>n>>m;init(n);long long ans = 0;for (int i=1; i<=(n+1)/2; i++)ans += C(n+1-i, i)*pow(m-1, n-i)%M;cout<<ans%M<<'\n';return 0;
}/*
C(n,1)*(m-1)^(n-1) +
C(n-1,2)*(m-1)^(n-2) + 
...
C(n+1-(n+1)/2,(n+1)/2)*(m-1)^(n-(n+1)/2)4*(4**3)+3*(4**2)*/

---

个人总结：

感觉这次比赛给我带来很大帮助, 通过本场竞赛复习的字符串的相关操作, 模拟的基础思维, 第三题确实给我带来很多惊喜, 从暴力超内存,到思维上的提升帮助巨大,后面补题的过程在知识上也给我带来提高, 本次双周赛对我来说起到了一个查缺补漏的作用,在我参加算法竞赛的道路，这无疑是一次难得的良机。

---

补题单 : 第 19 场 小白入门赛

• 上交文物
• 打开石门
• 青铜门上的涂鸦
• 敲打骷髅兵
• 净化王胖子
• 云顶天宫