9.9

[Ryanlyt]

快速排序（不稳定）nlogn

核心思想：分治

1. 确定分界点
2. 调整范围⭐ 可以暴力 i，j双指针
3. 递归处理左右两段

swap(q[i], q[j])

快排模板（注意边界问题的存在，背一种能解决所有边界问题的模板）

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

[Ryanlyt]

归并排序（稳定）nlogn

核心思想：分治

1. 确定分界点：mid = （l+r）/ 2
2. 递归排序left, right
3. 归并——合二为一⭐

sort(q, q+n)

快排、归并排和sort库函数时间差不多

归并排序模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

[Ryanlyt]

整数二分

二分的本质并不是单调性，找一个性质，左半边满足，右半边不满足。时时刻刻保证答案落在区间里面

整数二分模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

[Ryanlyt]

前缀和

S[i] = a[1] + a[2] + ... a[i] = S[i - 1] + a[i] a[l] + ... + a[r] = S[r] - S[l - 1] 作用：迅速求数组里某一段的和 把S[0]置成0，前缀和从S[1]开始

差分（和前缀和互为逆运算）

给区间[l, r]中的每个数加上c（称为插入操作）：B[l] += c, B[r + 1] -= c 作用：用O(1)的时间给原数组某一段连续的空间加上同一个值 b[i]（不用构造）：把a[i]假定初始全为0，之后进行了[i,i]+a[i]的操作（n次插入操作（n为数组大小）） 总结：差分只有一个操作

void insert(int l, int r, int c){
        b[i] += c;
        b[r + 1] -= c;
}

在C++中，int类型的默认值为0。这意味着在不进行初始化的情况下，int类型的变量将被赋予默认值0。

[Ryanlyt]

关于io

数据规模≥1e6时用scanf读取，否则用cin快些

[Ryanlyt]

双指针算法

双指针算法模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

核心思想：

for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
                O(n^2)

将以上的朴素算法优化到O(n)

最简单的双指针算法题目：

将输入字符串，如：abc askdn alskdn 按空格分开，并分行输出

最长的不包含重复数字的连续子序列长度

input：1 2 2 3 5 output：3 双指针问题一般来说可以从暴力（朴素）的方法想

//朴素做法：O(n^2)
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < i; j++)
    {
        if(check(j, i))
        {
            res = max(res, i - j + 1);
        }
    }
}

//双指针算法：O(n) 
for(int i = 0, j = 0; i < n; i++){
    while(j <= i && check(j,i)) j++;
    res = max(res, i - j + 1);
} 

其中的check()可以写为如下（也可在原先的for里直接写）

bool check(int j, int i){
    while(j < i){
        if(a[j] == a[i]){
            return true;
        }else{
            j++;
        }
    }
        return false;
}

总结：先写一个暴力的方法，看i和j有没有什么单调关系（如上题，j和i都是往右边走，不会出现一个往右走一个往左走），用这种单调关系利用模板把枚举的状态数量从O(n^2)变成O(n)

[Ryanlyt]

gets()和getline()用法区别

• gets(str)

参数必须是char型数组，不能是string型。

• getline(cin,str)

geline在缓冲区中读取指定个数的字符或者读到某个停止符后结束读取，将读取到的字符输入到字符数组或string类中，并且自动添加'\0'。

strlen(str)