数据结构是大一下的课程，总体学的还好，就当复习一下，以及看看有没有什么其他内容。

链表与邻接表

数组模拟单链表

使用两个数组e[N]和nxt[N]，使用下标关联起来。其他操作与正常链表一样。

数组模拟双链表

使用三个数组e[N]、l[N]和r[N]。

初始化：

r[0] = 1;
l[1] = 0;

阅读全文

本节主要学习双指针、位运算、离散化、区间合并等知识。

双指针算法

常见类型：指向两个不同序列 或者 指向同一个系列的不同位置。

通用模版

for(i = 0, j =0; i < n; i++){
    while(j<i && check(i,j)) j++;
    //每道题目的具体逻辑
}

阅读全文

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

高精度

基本思想

常考类型：

• $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. 持续移动左右指针并交换元素，直到两个指针相遇，此时结束

阅读全文

基本工具

编译器选项

-std=c++11

文件读入

#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif

快速读入

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

阅读全文