【蓝桥杯】第十三届C++B组省赛

⭐️个人主页：@小羊 ⭐️所属专栏：蓝桥杯 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

---

试题A：九进制转十进制

这题我们直接手算最快，当然写代码也用不了多少时间。

#include <bits/stdc++.h>
using namespace std;int main()
{int n = 2022;int ret = 0, m = 1;while (n){ret += (n % 10) * m;m *= 9;n /= 10;}cout << ret << endl;return 0;
}

任意进制转10进制：

#include <bits/stdc++.h>
using namespace std;int func(int x, int y)
{int ret = 0, i = 0;while (x){ret += (x % 10) * pow(y, i); x /= 10;i++;}return ret;
}int main()
{int n, m;cin >> n >> m;cout << func(n, m) << endl;return 0;
}

如2022的9进制：

---

试题B：顺子日期

根据我们对日期的了解，要有顺子出现则只可能有 012、123 这两种，而且年份2022也不用考虑，所以我们可以遍历2022年每一天的日期然后删选统计。

#include <bits/stdc++.h>
using namespace std;bool check(int mouth, int day)
{string s;if (mouth < 10) s += '0';s += to_string(mouth);if (day < 10) s += '0';s += to_string(day);return (s.find("012") != string::npos) || (s.find("123") != string::npos);
}int main()
{int count = 0;int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};for (int i = 1; i <= 12; i++)for (int j = 1; j <= day[i]; j++)if (check(i, j)) count++;cout << count << endl;return 0;
}

---

试题C：刷题统计

• 注意题中给定的数据范围，很明显要开 long long；
• 一天一天枚举只能通过部分样例，需要做一个小优化，很容易的能想到先计算出需要的整的周数，然后再枚举剩下的天数。

#include <bits/stdc++.h>
using namespace std;using ll = long long;int main()
{ll a, b, n, num, week, day;cin >> a >> b >> n;num = 5 * a + 2 * b; // 一周做num道题 week = n / num; // 整的周数day = n - (week * num); // 还需要做多少题int count = 0;for (int i = 1; i <= 7 && day > 0; i++){count++;if (i <= 5) day -= a;else day -= b;} cout << week * 7 + count << endl;return 0;
}

---

试题D：修剪灌木

• 这道题需要多思考，多画图，就能找到其中的关键所在；
• 爱丽丝向左或向右经过第 i 棵树，到左端点或右端点后折返回来的这几天， 是第 i 棵树能长到最大高度的时机；
• 可以看作是爱丽丝没走一步第 i 棵树就长高 1cm，那就转而变为求爱丽丝下次经过第 i 棵树最大需要走多少步。

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;for (int i = 1; i <= n; i++)cout << 2 * max(n - i, i - 1) << endl;return 0;
}

---

试题E：X 进制减法

---

试题F：统计子矩阵

我们枚举所有子矩阵的上角和右下角，就能统计出所有子矩阵的和。但是四层循环会超出时间限制，只能拿到70%的分数。

#include <bits/stdc++.h>
using namespace std;using ll = long long;
int arr[510][510];
int dp[510][510];int main()
{int n, m, ret = 0;ll k;cin >> n >> m >> k;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> arr[i][j];dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];}}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){for (int x = i; x <= n; x++){for (int y = j; y <= m; y++){if ((dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1]) <= k) ret++;}}} }cout << ret << endl;return 0;	
}

可以用滑动窗口做优化，先固定一个上边界 i，再固定一个下边界 j，然后让 r 指针右移，当四条边界围成的矩阵和大于 k 时让 l 指针右移，当刚好子矩阵之和不超过 k 时，此时 l 和 r 之间的所有子矩阵之和都不超过 k。

注意遍历过程中的数据范围，不要造成重复遍历。

#include <bits/stdc++.h>
using namespace std;using ll = long long;
ll dp[510][510];
ll n, m, k;int main()
{ll ret = 0;cin >> n >> m >> k;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){int tmp;cin >> tmp;dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + tmp;}}for (int i = 1; i <= n; i++){for (int j = i; j <= n; j++){for (int l = 1, r = 1; r <= m; r++){while (l <= r && dp[j][r] - dp[j][l - 1] - dp[i - 1][r] + dp[i - 1][l - 1] > k) l++;if (l <= r) ret += r - l + 1;}}}cout << ret << endl;return 0;
}

---

试题G：积木画

我们以第 i 个位置向前推理：

可以发现，对于第 i 个位置只有一种拼法；对于第 i-1 个位置也只有一种拼法（不能竖着拼，这样就和前面重复了）；对于第 i-2 个位置就有两种拼法；同样的对于第 i-3、i-4 等等都是两种拼法。

那我们就可以写出状态转移方程：dp[i] = dp[i-1] + dp[i-2] + 2 * dp[i-3] + 2 * dp[i-4] + ... + 2 * dp[1]。
然后我们可以用高中常用的方法变化上面的式子得到 dp[i-1] = dp[i-2] + dp[i-3] + 2 * dp[i-4] + ... + 2 * dp[1]，两式相减得：dp[i] = 2 * dp[i-1] + dp[i-3]。

#include <bits/stdc++.h>
using namespace std;const int N = 1e7 + 1;
using ll = long long;
ll dp[N], mod = 1e9 + 7;int main()
{int n;cin >> n;dp[1] = 1;dp[2] = 2;dp[3] = 5;for (int i = 4; i <= n; i++)dp[i] = ((2 * dp[i - 1]) % mod + dp[i - 3]) % mod;cout << dp[n] << endl;return 0;
}

---

试题H：扫雷

---

试题I：李白打酒加强版

• 一般求合法的个数、顺序、排列、方案等且范围不是很大，大概率是用动态规划做。

本题的关键所在是：最后一次遇到花，且酒恰好喝完。

动态规划的两大要素：状态和转移。
状态：题中共有三个状态：店、花、酒。所以设 dp[i][j][k] 表示经过i家店，j朵花，壶里还有k斗酒的方案数。
转移：假设李白的壶中此时有k斗酒，则此时的状态 dp[i][j][k] 可以由 dp[i-1][j][k/2] （上一次遇到的是店，但是需要注意此时的k必须是偶数，因为此时的k是由上一次遇到店翻倍而来）和 dp[i][j-1][k+1] （上一次遇到的是花）转移而来。

最后返回 dp[n][m-1][1]，因为要保证最后一次遇到的是花，且酒恰好还剩一斗。

#include <bits/stdc++.h>
using namespace std;const int mod = 1e9 + 7;
// dp[i][j][k]表示经过i家店，j朵花，壶里还有k斗酒的方案总数 
int dp[110][110][110];int main()
{int n, m;cin >> n >> m;dp[0][0][2] = 1;for (int i = 0; i <= n; i++){for (int j = 0; j <= m; j++){for (int k = 0; k < m; k++){if (k % 2 == 0 && i > 0){dp[i][j][k] += (dp[i - 1][j][k / 2]) % mod; }if (j > 0){dp[i][j][k] += (dp[i][j - 1][k + 1]) % mod;}}}}cout << dp[n][m - 1][1] << endl;return 0;}

---

试题J：砍竹子

本题的关键是：如果当前的竹子高度在变化的过程中，某次高度在前面的竹子高度变化过程中出现过，那么这棵竹子就不用再砍了，因为可以和前面的竹子一起砍。对于后面的竹子也是一样，只要高度降低到在前面竹子高度变化中有出现，就点到为止，然后把当前竹子的所有变化记录下来，开始砍下一棵竹子。

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 1;
using ll = long long;
ll n, ret, sz;
ll arr[N], f[100];int main()
{cin >> n;for (int i = 0; i < n; i++) cin >> arr[i];while (arr[0] > 1){ret++;f[sz++] = arr[0];arr[0] = floor(sqrt(floor(arr[0] / 2.0) + 1));}for (int i = 1; i < n; i++){ll t = arr[i];while (t > 1){int flag = 0;for (int i = 0; i < sz; i++){if (f[i] == t) {flag = 1;break;}}if (flag == 1) break;ret++;t = floor(sqrt(floor(t / 2.0) + 1));}sz = 0;while (arr[i] > 1){f[sz++] = arr[i];arr[i] = floor(sqrt(floor(arr[i] / 2.0) + 1));}}cout << ret << endl;return 0;
}

---

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~