【蓝桥杯】第十三届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;
}

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