ZW_Blog

题目描述 题目大意&链接给定两个正整数，计算高精度整数乘以低精度整数。 输入输出样例：输入： 23 输出： 6 详情：ac_793高精度乘法 解题思路高精度乘法需要注意2点。 计算机处理乘法是将被乘数的每一位乘以乘数，然后赋值给进位 t ，t%10 作结果的数值位，t/10作进位： int t = 0; //进位for(int i = 0; i < A.size() || t; i++){ if(i < A.size()) t += A[i] * b; c.push_back(t % 10); t /= 10;} 去除结果的前导0： while(c.size() > 1 && c.back() == 0) c.pop_back(); //去除结果的前导0 完整代码#include<iostream>#include<vector>using namespace std;vector<int> mul(vector<int>...

题目描述 题目大意&链接给定两个正整数，计算高精度整数除以低精度整数。 输入输出样例：输入： 72 输出： 31 详情：ac_794高精度除法 解题思路高精度除法需要注意3点。 除法和加减乘法不同，它可以正序存储，但为统一模板，这里也采用逆序将其存储，因此div函数的循环条件需要更改： for(int i = A.size() - 1; i >= 0; i--){ ...} 余数 r 要模拟除法运算，r/b 作商的数值位；r %= b 作下一位的余数： for(int i = A.size() - 1; i >= 0; i--){ r = r * 10 + A[i]; c.push_back(r / b); r %= b;} 由于是逆序存储且逆序输出，则答案需要反转一下并去除结果的前导0： reverse(c.begin(), c.end());while(c.size() > 1 && c.back() == 0)...

总结英语背了一个小时单词

题目描述 题目大意&链接给定两个正整数，计算它们的差。 输入输出样例：输入： 3211 输出： 21 详情：ac_792高精度减法 解题思路高精度减法需要注意3点。 由于是两个正整数相减，结果可能为负数，因此需判断两个正整数大小： //判断A >= Bbool cmp(vector<int> A, vector<int> B){ if(A.size() != B.size()) return A.size() > B.size(); for(int i = A.size() - 1; i >= 0; i--) if(A[i] != B[i]) return A[i] > B[i]; return true;} 定义 t 记录相减时是否借位，若借位，则下轮置 t=1；否则置 t=0： int t = 0; //借位for(int i = 0; i < A.size(); i++){ t = A[i] - t; ...

题目描述 题目大意&链接给定两个正整数，计算它们的和。 输入输出样例：输入： 1223 输出： 35 详情：ac_791高精度加法 解题思路高精度加法需要注意2点。 用户输入的两个整数数值可能比较大，需要用字符串 string 进行读取，然后再存到 vector 容器中： string a, b;vector<int> A, B;cin>>a>>b;//注意要逆序存储到 vector 容器中for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); 定义 t 记录相加时是否进位，将 t%10 作为结果的数值位，t/=10作为进位： vector<int> c;int t = 0; //进位for(int i = 0; i < A.size()...

题目描述 题目大意&链接给定一个浮点数 n ，求它的三次方根（结果保留6位小数）。 输入输出样例：输入： 1000.00 输出： 10.000000 详情：ac_790数的三次方根 解题思路这题就是简单的二分，有两个地方需要注意。 小数的精度 eps 需要在给定的精度上 +2 来确保结果的准确性： const double eps = 1e-8; 确定 left 和 right 的初值，当 n >= 0 时，right 至少 >=1；当 n < 0 时，left 至少 <= -1： // 根据n的正负设置初始区间if (n >= 0) { left = 0, right = max(1.0, n); // 处理n < 1的正数} else { left = min(n, -1.0), right = 0; // 处理n > -1的负数} 完整代码#include<iostream>using namespace...

题目描述 题目大意&链接给定一个长度为 n 的整数数列以及 q 个查询，对于每个查询，返回元素 k 的起始和终止位置，若 k 不存在返回-1 -1）。 输入输出样例：输入： 6 31 2 2 3 3 4345 输出： 3 45 5-1 -1 详情：ac_789数的范围 解题思路需要用到两次二分分别查询元素 k 的起始和终止位置。 查询元素 k 的起始位置： int bsearch_1(int l, int r, int k){ //通过 mid = l + r >> 1 和 r = mid 确保向左收缩，找到左边界。 while(l < r) { int mid = l + r >> 1; if(q[mid] >= k) r = mid; else l = mid + 1; } if(q[l] != k) return -1; else return l;} 查询元素 k 的终止位置： int...

题目描述 题目大意&链接给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。（逆序对：i < j 但 q[i] > q[j]，<i, j> 构成一个逆序对） 输入输出样例：输入: 62 3 4 5 6 1 输出： 5 详情：ac_788逆序对的数量 解题思路利用到归并排序的分治思想，递归排序的自顶向下过程中，统计3种情况的逆序对数量。 统计红色区间的逆序对数量： LL res = merge_sort(l, mid) + merge_sort(mid + 1, r); 统计蓝色区间的逆序对数量： LL res = merge_sort(l, mid) + merge_sort(mid + 1, r); 统计mid两边的逆序对数量： //归并过程并计数逆序对int k = 0, i = l, j = mid + 1;while(i <= mid && j <= r){ if(q[i] <= q[j]) tmp[k++] = q[i++]; else { ...

总结今天英语背了一个小时单词

题目描述 题目大意&链接给定一个长度为n的乱序数列，用归并排序将数列排成有序数列。 输入输出样例：输入: 53 1 2 4 5 输出： 1 2 3 4 5 详情：ac_787归并排序 解题思路归并排序也是采用分治思想，最开始数列每个元素单独作为一个子序列，然后相邻子序列两两归并，最后归并成一个子序列。 确定分界点mid： int mid = l + r >> 1; 递归排序mid的左右子区间： merge_sort(q, l, mid), merge_sort(q, mid + 1, r); 递归到mid左右区间只有一个元素后开始归并： //k为temp数组的索引，i取左边子序列的左端点，j取右边子序列的左端点int k = 0, i = l, j = mid + 1;while(i <= mid && j <= r){ if(q[i] <= q[j]) temp[k++] = q[i++]; else temp[k++] =...