目录
刷题就像打游戏，蓝桥杯是终极大BOSS，每天的真题都是小怪——虽然爆率低，但装备（知识）掉不停！
3.9 高精度算法
今天来点有意思的，模拟小学的加减乘除
一、高精度加法
题目链接：
题目描述：
解题思路：
这题我们可以看到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;
}二、高精度减法
题目链接：
题目描述：
解题思路：
这题和上面的高精度加法类似，都是不能简单的用一个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;
}三、高精度乘法
题目链接：
题目描述：
解题思路：
同上，模拟小学列竖式乘法即可
才怪，我骗你的，这里为了代码更加简洁，我们可以先处理进位，最后在处理，如下图：
解题代码：
#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;
}四、高精度除法
题目链接：
题目描述：
解题思路：
模拟小学除法即可
解题代码：
#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 枚举
枚举，顾名思义就是意义列举，来吧来吧直接上题目
一、铺地毯
题目链接：
题目描述：
解题思路：
因为题目给的数量不大，因此我们可以暴力枚举，把所有情况全部意义罗列出来，在判断是否符合题目要求，符合直接返回即可（因为这个题是我们需要我们找到最后一个符合要求的地毯，因此我们可以之后从后往前遍历来优化代码）
解题代码：
#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;
}二、回文日期
题目链接：
题目描述：
解题思路：
这里可以我们可以直接暴力枚举从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;
}三、扫雷
题目链接：
题目描述：
解题思路：
这个题也是可以枚举的，我们可以根据第一排是否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，本期就到这里吧，过两天在更新下一期 拜拜~
每日三省吾身：
暴力能过吗？
贪心能贪吗？
要不…开摆？🤔