【蓝桥杯每日一题】3.16

发布于:2025-03-17 ⋅ 阅读:(12) ⋅ 点赞:(0)

Alt

🏝️专栏: 【蓝桥杯备篇】
🌅主页: f狐o狸x


目录

3.9 高精度算法

一、高精度加法

        题目链接:

        题目描述:

        解题思路:

        解题代码:

二、高精度减法

        题目链接:

        题目描述:

        解题思路:

        解题代码:

三、高精度乘法

        题目链接:

        题目描述:

        解题思路:

        解题代码:

四、高精度除法

        题目链接:

        题目描述:

        解题思路:

        解题代码:

3.10 枚举

一、铺地毯

        题目链接:

        题目描述:

        解题思路:

        解题代码:

二、回文日期

        题目链接:

        题目描述:

        解题思路:

        解题代码:

三、扫雷

        题目链接:

        题目描述:

        解题思路:

        解题代码:


        刷题就像打游戏,蓝桥杯是终极大BOSS,每天的真题都是小怪——虽然爆率低,但装备(知识)掉不停!

3.9 高精度算法

        今天来点有意思的,模拟小学的加减乘除

一、高精度加法

        题目链接:

        P1601 A+B Problem(高精)

        题目描述:

        解题思路:

        这题我们可以看到a,b这两个数的值是非常大的(已经超过了long long)因此我们需要自己写一个加法的代码,我们可以用一个数组把数字的每一位存起来,在想小学数学那样一位一位的计算就可以了

        解题代码:

#include <iostream>

using namespace std;

const int N = 1010;

int a[N], b[N], c[N];
int la, lb, lc;

void add(int c[], int a[], int b[])
{
	for (int i = 0; i < lc; i++)
	{
		c[i] += a[i] + b[i];
		c[i + 1] = c[i] / 10;
		c[i] %= 10;
	}
	if (c[lc]) lc++;
}


int main()
{
	string x, y; cin >> x >> y;
	// 将数据存入数组
	la = x.size();
	lb = y.size();
	lc = max(la, lb);
	for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';
	for (int i = lb - 1; i >= 0; i--) b[lb - 1 - i] = y[i] - '0';
	add(c, a, b);// c = a + b

	for (int i = lc - 1; i >= 0; i--) cout << c[i];

	return 0;
}

二、高精度减法

        题目链接:

        P2142 高精度减法

        题目描述:

        解题思路:

        这题和上面的高精度加法类似,都是不能简单的用一个long long 的变量就能搞定的,因此还是需要我们模拟一下小学时候学的减法,列竖式来一个一个算

        解题代码:


#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N], c[N];
int la, lb, lc;

bool bigger(string x, string y)
{
	if (x.size() != y.size())
	{
		return y.size() > x.size();
	}
	return y > x;
}

void sub(int c[], int a[], int b[])
{
	for (int i = 0; i < lc; i++)
	{
		c[i] += a[i] - b[i];
		if (c[i] < 0)
		{
			c[i + 1]--;
			c[i] += 10;
		}
	}
	while (1 != lc && c[lc - 1] == 0) lc--;
}

int main()
{
	string x, y; cin >> x >> y;
	if (bigger(x, y))
	{
		swap(x, y);
		cout << '-';
	}
	la = x.size(); lb = y.size(); lc = max(la, lb);
	for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';
	for (int i = lb - 1; i >= 0; i--) b[lb - 1 - i] = y[i] - '0';

	sub(c, a, b); // c = a - b;
	for (int i = lc - 1; i >= 0; i--) cout << c[i];
	return 0;
}

三、高精度乘法

        题目链接:

        P1303 A*B Problem

        题目描述:

        解题思路:

        同上,模拟小学列竖式乘法即可

        才怪,我骗你的,这里为了代码更加简洁,我们可以先处理进位,最后在处理,如下图:

        解题代码:

#include <iostream>

using namespace std;

const int N = 2010;

int a[N], b[N], c[N];
int la, lb, lc;

void mul(int c[], int a[], int b[])
{
	for (int i = 0; i < la; i++)
	{
		for (int j = 0; j < lb; j++)
		{
			c[i + j] += a[i] * b[j]; // 无进位乘法
		}
	}
	// 处理进位
	for (int i = 0; i < lc; i++)
	{
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}
	while (lc != 1 && c[lc - 1] == 0) lc--;
}

int main()
{
	string x, y; cin >> x >> y;
	la = x.size(); lb = y.size(); lc = la + lb;

	for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';
	for (int i = lb - 1; i >= 0; i--) b[lb - 1 - i] = y[i] - '0';

	mul(c, a, b);// c = a * b;

	for (int i = lc - 1; i >= 0; i--) cout << c[i];

	return 0;
}

四、高精度除法

        题目链接:

        P1480 A/B Problem

        题目描述:

        解题思路:

        模拟小学除法即可

        解题代码:

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 5010;

int a[N], c[N];
LL b;
int la, lc;

void div(int c[], int a[], LL b)
{
	LL t = 0;
	for (int i = lc - 1; i >= 0; i--)
	{
		t = t * 10 + a[i];
		c[i] = t / b;
		t = t % b;
	}
	while (lc != 1 && c[lc - 1] == 0) lc--;
}

int main()
{
	string x; cin >> x >> b;
	la = x.size(); lc = la;
	for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';

	div(c, a, b); // c = a / b

	for (int i = lc - 1; i >= 0; i--) cout << c[i];

	return 0;
}

3.10 枚举

        枚举,顾名思义就是意义列举,来吧来吧直接上题目

一、铺地毯

        题目链接:

        P1003 [NOIP 2011 提高组] 铺地毯

        题目描述:

        解题思路:

        因为题目给的数量不大,因此我们可以暴力枚举,把所有情况全部意义罗列出来,在判断是否符合题目要求,符合直接返回即可(因为这个题是我们需要我们找到最后一个符合要求的地毯,因此我们可以之后从后往前遍历来优化代码)

        解题代码:


#include <iostream>

using namespace std;

const int N = 1e4 + 10;

int a[N], b[N], g[N], k[N];

int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> b[i] >> g[i] >> k[i];
	}
	int x, y; cin >> x >> y;
	int flag = 0;
	for (int i = n; i >= 0; i--)
	{
		if (a[i] <= x && b[i] <= y &&
			a[i] + g[i] >= x && b[i] + k[i] >= y)
		{
			cout << i << endl;
			flag++;
			break;
		}
	}
	if (!flag) cout << -1 << endl;

	return 0;
}

二、回文日期

        题目链接:

        P2010 [NOIP 2016 普及组] 回文日期

        题目描述:

        解题思路:

        这里可以我们可以直接暴力枚举从date1 一直枚举到 date2,然后再一一判断该日期是否是回文日期,再用一个cnt变量计数就行了。

        但是这样的算法会不会太过于浪费呢?这里有另外一个方法:将data1里的year1 枚举到year2,再判断日期是否合法即可。

        但是这样依然不是最优解,方法二还需要枚举9999次,这里我们还有法三:将所有日期枚举出来,在判断回文的年份是否在题目要求的年份里面

        解题代码:

        这里煮波偷个懒,只写第第三种方法,前两种方法大家可以自己去试试

#include <iostream>

using namespace std;

typedef long long LL;

int days[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };

int main()
{
	int date1, date2; cin >> date1 >> date2;
	int cnt = 0;
	for (int m = 1; m < 13; m++)
	{
		for (int d = 1; d <= days[m]; d++)
		{
			if (date1 <= (((d % 10) * 1000 + (d / 10) * 100 + (m % 10)*10 + m / 10) * 10000 + m * 100 + d) &&
				date2 >= (((d % 10) * 1000 + (d / 10) * 100 + (m % 10) * 10 + m / 10) * 10000 + m * 100 + d))
			{
				cnt++;
			}
		}
	}
	cout << cnt << endl;

	return 0;
}

三、扫雷

        题目链接:

        P2327 [SCOI2005] 扫雷

        题目描述:

        解题思路:

        这个题也是可以枚举的,我们可以根据第一排是否1有雷推出下一排有没有雷(是否有雷用0 1表示)那么下一排有没有雷就=上一排的地雷+当前排的地雷 - 当前排的数字

        解题代码:

#include <iostream>

using namespace std;

const int N = 1e4 + 10;

int n;

int a[N], b[N];

int cheak1()
{
	a[1] = 0;
	for (int i = 2; i <= n + 1; i++)
	{
		a[i] = b[i - 1] - a[i - 1] - a[i - 2];
		if (a[i] > 1 || a[i] < 0)
			return 0;
	}
	if (a[n + 1])return 0;
	return 1;
}

int cheak2()
{
	a[1] = 1;
	for (int i = 2; i <= n + 1; i++)
	{
		a[i] = b[i - 1] - a[i - 1] - a[i - 2];
		if (a[i] > 1 || a[i] < 0)
			return 0;
	}
	if (a[n + 1])return 0;
	return 1;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
	}
	int ret = 0;
	ret += cheak1();
	ret += cheak2();
	cout << ret << endl;

	return 0;
}

ok,本期就到这里吧,过两天在更新下一期 拜拜~

每日三省吾身:

  • 暴力能过吗?

  • 贪心能贪吗?

  • 要不…开摆?🤔


网站公告

今日签到

点亮在社区的每一天
去签到