本节内容主要为高精度运算、前缀和与差分的主要思想和代码。

高精度

基本思想

常考类型：

• $A+B$ ，两个的位数大约在 $10^6$ 。
• $A-B$ ，两个的位数大约在 $10^6$ 。
• $A\times a$ ， $A$ 位数大约 $10^6$ ，$a<10^9$ 。
• $A \div b$ ， $A$ 位数大约 $10^6$ ，$b<10^9$ 。

如何存储

使用数组进行存储，每一个位置存一个数，个位数存到开头（数组0位置）。

如何运算

竖式加减乘除，每一位是 $(A_i+B_i+t) \% 10$ ，其中 $t$ 为上一位运算的进位。

阅读全文

本节内容为部分排序和查找算法，数据结构课讲过，不过当时期末时间紧，没去听课，虽然PPT看懂了，但是从没有自己完整敲过，现在原理也都忘了，学一遍发现确实有些地方容易写错。

快速排序

核心思路

主要思想：分治

1. 确定分界点：q[l]或者q[(l+r)/2]或者q[r]；
2. 调整范围：目标是左边的数都小于等于x，右边的数都大于等于x（分界点不一定是x）；
3. 递归处理左右两端

第2步实现

暴力算法

1. 开两个数组a[ ]和b[ ]；

2. 把q[ ]中从l到r遍历：

   • q[i]<=x 放入a;
   • q[i]>x 放入b;
3. 把a[ ]和b[ ]放入q[ ]中

常用思路

1. 设定两个指针，从左右两端开始：

   • 左指针从左向右寻找第一个大于等于基准的元素
   • 右指针从右向左寻找第一个小于等于基准的元素
2. 找到之后交换两个元素

3. 持续移动左右指针并交换元素，直到两个指针相遇，此时结束

阅读全文