蓝桥杯算法训练合集十四 1.P08052.P07053.同余方程4.P08015.ascii应用

目录

1.P0805

2.P0705

3.同余方程

4.P0801

5.ascii应用

---

1.P0805

问题描述

当两个比较大的整数相乘时，可能会出现数据溢出的情形。为避免溢出，可以采用字符串的方法来实现两个大数之间的乘法。具体来说，首先以字符串的形式输入两个整数，每个整数的长度不会超过10位，然后把它们相乘的结果存储在另一个字符串当中（长度不会超过20位），最后把这个字符串打印出来。例如，假设用户输入为：62773417和12345678，则输出结果为：774980393241726.
编写函数 void Multiply(char* s1, char* s2, char* result); 实现大数乘法（只考虑正整数），其中result = s1 * s2.
编写main函数测试该函数的正确性.

样例输入

62773417 12345678

样例输出

774980393241726

示例代码

#include<iostream>
#include<sstream>
using namespace std;
string s1, s2;
int len1, len2, a[11] = { 0 }, b[11] = { 0 }, c[21] = { 0 };
int main() {cin >> s1;cin >> s2;len1 = s1.length();len2 = s2.length();for (int i = 1; i <= len1; i++) {//存储数字a[len1 + 1 - i] = int(s1[i - 1]) - 48;}for (int i = 1; i <= len2; i++) {b[len2 + 1 - i] = int(s2[i - 1]) - 48;}for (int i = 1; i <= len1; i++) {//按照位与位相乘for (int j = 1; j <= len2; j++) {c[i + j - 1] += (a[i] * b[j]);if (c[i + j - 1] >= 10) {//如果有进位c[i + j] += (c[i + j - 1] / 10);c[i + j - 1] %= 10;}}}int flag = 1;for (int i = 20; i >= 1; i--) {if (c[i] == 0) {if (flag == 1) {continue;}else {cout << c[i];}}else {flag = 0;cout << c[i];}}return 0;
}

2.P0705

问题描述

输入两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。交集、并集和余集的计算都要求写成一个单独的函数。
输入第一行为一个整数n，表示集合A中的元素个数。
第二行有n个按从小到大的顺序输入且互不相同的整数，表示集合A中的元素
第三行为一个整数m，表示集合B中的元素个数。
第四行有m个按从小到大的顺序输入且互不相同的整数，表示集合B中的元素
集合中的所有元素均为int范围内的整数，n、m<=1000。
输出第一行按从小到大的顺序输出A、B交集中的所有元素。
第二行按从小到大的顺序输出A、B并集中的所有元素。
第三行按从小到大的顺序输出B在A中的余集中的所有元素。

样例输入

5
1 2 3 4 5
5
2 4 6 8 10

样例输出

2 4
1 2 3 4 5 6 8 10
1 3 5

示例代码

#include<iostream>
#include<algorithm>
using namespace std;
int a[1000], b[1000], c[1000], d[1000], e[1000];
int main() {int n, m;cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];d[i] = a[i];}cin >> m;for (int i = 0; i < m; i++) {cin >> b[i];}//求交集int cnt1 = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (a[i] == b[j]) {c[cnt1++] = a[i];cout << a[i]<<" ";break;}}}cout << endl;//求并集int cnt2 = n;for (int i = 0; i < m; i++) {int flag = 0;for (int j = 0; j < n; j++) {if (b[i] == a[j]) {flag = 1;break;}}if (flag == 0) {d[cnt2++] = b[i];}}sort(d, d + cnt2);for (int i = 0; i < cnt2; i++) {cout << d[i] << " ";}cout << endl;//求差集 A-交集Cfor (int i = 0; i < n; i++) {int flag = 1;for (int j = 0; j < cnt1; j++) {if (a[i] == c[j]) {flag = 0;break;}}if (flag == 1) {cout << a[i] << " ";}}return 0;
}

3.同余方程

问题描述

求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。

输入格式

输入只有一行，包含两个正整数a, b，用一个空格隔开。

输出格式

输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。

样例输入

3 10

样例输出

7

数据规模和约定

对于40%的数据，2 ≤b≤ 1,000；
对于60%的数据，2 ≤b≤ 50,000,000；
对于100%的数据，2 ≤a, b≤ 2,000,000,000。

示例代码

#include <iostream>
using namespace std;
typedef long long ll;
//辗转相除法
void exgcd(ll a, ll b, ll& x, ll& y) {if(b == 0) {x = 1; y = 0;}else {exgcd(b, a%b, y, x); y -= (a/b)*x;}
}
int main() {ll a, b, x, y;cin >> a >> b;exgcd(a, b, x, y);cout << (x + b) % b; //避免出现 x<0 的情况return 0;
}

4.P0801

问题描述

编写一个数组求和函数void Add(int n, int* a1, int* a2, int* result); 其中n<100是数组长度，a1是第一个数组，a2是第二个数组，result是a1和a2的和。假设a1={2, 4, 5, 8}, a2={1, 0, 4, 6}，则result={3, 4, 9, 14};
编写main函数测试该函数的正确性。依次输入n, a1, a2, 输出result。

示例输入

4
2 4 5 8
1 0 4 6

示例输出

3 4 9 14

示例代码

#include<iostream>
using namespace std;int main() {int n,a[100],b[100];cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}for (int i = 0; i < n; i++) {cout << a[i] + b[i] << " ";}return 0;
}

5.ascii应用

问题描述 

输入ascii码n（65≤n≤90,97≤n≤122），输出对应的字母及其在字母表中的位置并判断大小写。

输入格式

输入的数据只有一行，其中包括一个数字n，表示一个ascii码。

输出格式

输出一行，分别是ascii码n所对应的字符，并判断大小写，及其在字母表中的位置。

样例输入1

65

样例输出1

A d1

样例输入2

97

样例输出

a x1

数据规模和约定

65≤n≤90,97≤n≤122。

示例代码

#include<iostream>
using namespace std;int main() {int n;cin >> n;if (n >= 65 && n <= 90) {cout << char(n) << " d" << n - 64;}else {cout << char(n) << " x" << n - 96;}return 0;
}