当前位置: 首页 > article >正文

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

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

动图描述

目录

    • 试题A:九进制转十进制
    • 试题B:顺子日期
    • 试题C:刷题统计
    • 试题D:修剪灌木
    • 试题E:X 进制减法
    • 试题F:统计子矩阵
    • 试题G:积木画
    • 试题H:扫雷
    • 试题I:李白打酒加强版
    • 试题J:砍竹子


试题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:顺子日期

请添加图片描述

根据我们对日期的了解,要有顺子出现则只可能有 012123 这两种,而且年份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;
}

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

头像

http://www.kler.cn/a/588004.html

相关文章:

  • 通义Qwen实战(1): 环境安装及微调实战
  • 用pyqt做个日期输入控件,实现公农历转换及干支纪时功能
  • Implementing SAP BPC Embedded - 2nd Edition
  • 暨南大学MEM复试资料
  • 奇安信面试题
  • 蓝桥杯 阶乘约数
  • 字符串 数字 相互转化
  • IMX6ULL_Pro开发板的串口应用程序实例(利用TTY子系统去使用串口)
  • 蓝桥与力扣刷题(蓝桥 字符统计)
  • linux (centos) 的 nodejs 安装全局包后使用命令无效
  • UE5 RVT 制作场景交互 - 遮罩
  • 安装配置Anaconda
  • es6初步学习
  • k8s serviceaccount在集群内指定apiserver时验证错误的问题
  • 计算机视觉中的MIP算法全解析
  • 使用VSCode开发STM32补充(Debug调试)
  • AI+视觉测试:如何提升前端测试质量?
  • 五大基础算法——模拟算法
  • MySQL -- 基本函数
  • 【Linux进程通信】————匿名管道命名管道