【蓝桥杯每日一题】3.16

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 + bfor (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 / bfor (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，本期就到这里吧，过两天在更新下一期拜拜~

每日三省吾身：

暴力能过吗？
贪心能贪吗？
要不…开摆？🤔