当前位置：首页 > news >正文

蓝桥杯-洛谷刷题-day4（C++）

news 2025/7/7 1:57:57

1.高精度乘法

i.P1303 A*B Problem高精度乘法

2.P4924 [1007] 魔法少女小Scarlet

i.题目

ii.代码

3.二维数组

i.二维数组的建立

ii.备份

iii.二维数组的转动

4.指令的及时处理

1.高精度乘法

即，将每一位变为数组中的一位，并在数组中以倒序排列，

如12，就被化为b[1] = 2, b[2] = 1。

乘法就是用两个数组里的每一位（暂称为x）与另外一个数组的所有数相乘之后，错位相加（错几位相加，取决于x 对应的数组下标，下标为2，说明这个x 是十位上的数，需要错一位）

i.P1303 A*B Problem高精度乘法

#include <iostream>  
#include <string>using namespace std;void testlan()
{string a1, b1;//a, b储存两个要相乘的数，c储存结果int a[10001] = { 0 }, b[10001] = { 0 }, c[10001] = { 0 }, lena, lenb;//先用字符串接收，便于获取数字长度，更好的掌控数组的有效长度cin >> a1 >> b1;//得到两个数字的长度lena = a1.length(); lenb = b1.length();//将这两个数字的每一位存储在数组中；倒序，是为了便于之后按个位开始进行计算，抛弃a[0]，方便后续的运算for (int i = 1; i <= lena; i++)a[i] = a1[lena - i] - '0';for (int i = 1; i <= lenb; i++)b[i] = b1[lenb - i] - '0';//每一位都要和另一个数的所有位相乘，正好是一个嵌套循环//乘法中，乘完之后，是一个错位相加，用外循环稳定的递增，正好可以模拟，乘完之后的逐层错位for (int i = 1; i <= lena; i++)for (int j = 1; j <= lenb; j++){c[i + j - 1] += a[i] * b[j]; //cout << c[i + j - 1] << endl;}//计算结果的长度一定小于原来两个数的长度之和int len = lena + lenb;//之后，对c中，每一位超过10的，进行递进处理for (int i = 1; i < len; i++){if (c[i] > 9){c[i + 1] += c[i] / 10;c[i] %= 10;}}//读位：从这个最长位置往前读位，直到读到有效数字，即可得到c的长度while (c[len] == 0 && len > 1)len--;for (int i = len; i >= 1; i--)cout << c[i];/*读位+输出的优化，引入一个判别标识，将读位与输出结合bool flag = 0;while(len > 1){if(c[len] != 0)flag = 1;if(flag)cout << c[len];len--;}//当读位读到第一个非零数之后，将标识设置为真，意味着读到了，这个数的最高位，最高位的数不可能为0，之后无论读到的数是否为零都会输出*/}int main()
{testlan();return 0;
}

拓：高精度阶乘求和，就是高精乘法的特殊形式，每一次都用一个数，来乘以另外一个结果的所有位的数，从低到高，1！+2！。。。，循环中，用一个数组b[]存储阶乘结果（i的阶乘），另一个数组a[]进行加和（i的阶乘加上之前的阶乘和a[]）。

2.P4924 [1007] 魔法少女小Scarlet

i.题目

ii.代码

#include <iostream>  
#include <string>
using namespace std;int temp[500][500], square[500][500];//顺时针转换
void turn(int x, int y, int r)
{//首先，将原矩阵copy一份，方便后续的移动赋值，起到temp的作用for (int i = x - r; i <= x + r; i++){for (int j = y - r; j <= y + r; j++) temp[i][j] = square[i][j];}//顺时针则从最左下角开始（其实，从哪个角都可以），每次移动只看这一列的移动，因为循环是按行遍历，在转动的时候，列会变成行，用行遍历，按列赋值//这里要对应行的从左到右，所以并不是哪个角都便利int x1 = x + r, y1 = y - r;for (int i = x - r; i <= x + r; i++){for (int j = y - r; j <= y + r; j++){square[i][j] = temp[x1][y1];//从下往上，转动之后就是从左到右x1--;}//之后，循环的遍历进入下一行，我们自己标记的列，也要进入下一列（同时回到最下面一行）x1 = x + r, y1++;}
}
//逆时针转换（与顺时针的转动道理不能说是一摸一样吧，只能说是完全相同）
void turn_(int x, int y, int r)
{for (int i = x - r; i <= x + r; i++){for (int j = y - r; j <= y + r; j++) temp[i][j] = square[i][j];}int x1 = x - r, y1 = y + r;for (int i = x - r; i <= x + r; i++){for (int j = y - r; j <= y + r; j++){square[i][j] = temp[x1][y1];x1++;}x1 = x - r, y1--;}
}void testlan()
{//用t 暂存需要存入的数，之后只需递增即可存入下一位int n, m, t = 1;cin >> n >> m;//建立原始矩阵for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){square[i][j] = t;t++;}}验证输出//for (int i = 1; i <= n; i++)//{//	for (int j = 1; j <= n; j++)//	{//		cout << square[i][j] << ' ';//	}//	cout << endl;//}//cout << "--------------" << endl;//输入指令，同时进行转动处理（因为指令之间顺序不能颠倒且再加一个数组用来储存过于多此一举）int x, y, r, z;for (int i = 1; i <= m; i++){cin >> x >> y >> r >> z;if (z == 0) turn(x, y, r);else if (z == 1) turn_(x, y, r);}//输出for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cout << square[i][j] << ' ';}cout << endl;}
}int main()
{testlan();return 0;
}

之后，总结一下，，这个题目给我带来的新知识。

3.二维数组

i.二维数组的建立

通过一个嵌套循环，按先从左到右后从上到下的顺序建立二维数组。

for (int i = x - r; i <= x + r; i++)
{for (int j = y - r; j <= y + r; j++) {//进行赋值之类的操作}
}

ii.备份

对于数组内部分位置的数据，进行一定的位置变动，可以使用temp[][]对原数组进行备份暂存，之后，再进行值的移动（其思路与两变量值的交换同理，temp = a; a = b; b = temp ）。

iii.二维数组的转动

需要进行备份，因为有大量的数据在位置上出现移动。

每次转动只看一列，列转动后就会变为行，可以设置两个指针，指示行列下标，指针在temp中遍历列，将值赋值给行遍历原数组中。

//顺时针转换
void turn(int x, int y, int r)
{//首先，将原矩阵copy一份，方便后续的移动赋值，起到temp的作用for (int i = x - r; i <= x + r; i++){for (int j = y - r; j <= y + r; j++) temp[i][j] = square[i][j];}//顺时针则从最左下角开始（其实，从哪个角都可以），每次移动只看这一列的移动，因为循环是按行遍历，在转动的时候，列会变成行，用行遍历，按列赋值//这里要对应行的从左到右，所以并不是哪个角都便利int x1 = x + r, y1 = y - r;for (int i = x - r; i <= x + r; i++){for (int j = y - r; j <= y + r; j++){square[i][j] = temp[x1][y1];//从下往上，转动之后就是从左到右x1--;}//之后，循环的遍历进入下一行，我们自己标记的列，也要进入下一列（同时回到最下面一行）x1 = x + r, y1++;}
}