ZW_Blog

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

题目描述 题目大意&链接给定两个正整数，计算它们的差。 输入输出样例：输入： 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++] =...

题目描述 题目大意&链接给定一个长度为n的乱序数列，用快速选择算法求出数列从小到大排序后的第 k 个数。 输入输出样例：输入: 5 32 4 1 5 3 输出： 3 详情：ac_786第k个数 解题思路这题是在快排算法上的pro版，需要你在每排序完一次，都需要与 k 做个判断：数列的哪边继续递归排序。 定义 <= x 的一边元素数量为s1： int s1 = j - l + 1; 当 k <= s1 时，递归排序数列的左边；否则递归排序数列的右边 if(k <= s1) return quick_sort(l, j, k);else return quick_sort(j+1, r, k-s1); l == r 时，即代表找到第 k 个排序后的元素 int quick_sort(int l, int r, int k){ if(l == r) return q[l]; ... int s1 = j - l + 1; if(k <= s1) return quick_sort(l,...

题目描述 题目大意&链接给定一个长度为n的乱序数列，用快速排序将数列排成有序数列。 输入输出样例：输入: 53 1 2 4 5 输出： 1 2 3 4 5 详情：ac_785快速排序 解题思路快速排序主要就是分治思想，将数列以枢轴x为标准，划分为两个区间（i<=x 和 j>=x），划分好后重新选取枢轴x依次递归处理其左右区间。 枢轴选取： 共有四种选取方式：左端点q[l]，右端点q[r]，中间索引q[l + r >> 1] 和 随机索引（这里我一般取中间索引作枢轴） int x = q[l + r >> 1], i = l - 1, j = r + 1; 调整区间： 定义i和j两个指针，i指向<=x的区间，j指向>=x的区间 int x = q[l + r >> 1], i = l - 1, j = r + 1; 递归处理左右区间 quick_sort(q, l, j);quick_sort(q, j+1...