【算法2-1】前缀和与差分

https://www.luogu.com.cn/training/200#problems

P2671 [NOIP2015 普及组] 求和
https://www.luogu.com.cn/problem/P2671
枚举x，z复杂度为n²，会超时。
图片说明
用一下分组思想，把每个颜色分为一组，再在每个颜色中按奇偶分组，所以一共有2m组
设一个分组里有k个数，
图片说明

这个代码比较清楚。
https://www.luogu.com.cn/blog/BlueHedgehog/p2671-qiu-hu-ti-xie

P1115 最大子段和
直接用前缀和会超时。

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    LL ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            ans = max(ans, s[i] - s[j - 1]);
        }
    }
    cout << ans << endl;

看题解，这题要用到dp或者可以说是前缀和+贪心。AC
图片说明 

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = max(a[i], s[i - 1] + a[i]);
        ans = max(ans, s[i]);
    }
    cout << ans << endl;

P3397 地毯
差分矩阵

P3406 海底高铁
利用一维差分统计。
P1719 最大加权矩形
最大子矩阵，注意求出前缀和矩阵后还要算出其中小矩阵的值一起比较。

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
        cin >> a[i][j];
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    }
}
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
        for(int k = 1; k <= i; k++){
            for(int l = 1; l <= j; l++){
                ans = max(ans, s[i][j] - s[i][l - 1] - s[k - 1][j] + s[k - 1][l - 1]);
            }
        }
    }
}

P2004 领地选择
P5638 【CSGRound2】光骓者的荣耀
这两题都要注意边界。

【算法2-2】线性复杂度优化 / 离散化

P2032 扫描
滑动窗口，用单调队列解决。也就是acwing的算法基础课的单调队列模板题。
https://www.acwing.com/video/250/
P1440 求m区间内的最小值
和上面一样，但是这里窗口不包含本身，所以有点修改。
P1886 滑动窗口 /【模板】单调队列
和acwing的那道一模一样。

P1638 逛画展
类似滑动窗口的贪心。
考虑暴力。枚举右端点，贪心找到一个最优的左端点，判断区间长度是否更优，更新答案。下面是参考题解。
https://www.luogu.com.cn/blog/acxblogs/solution-p1638

P2882 [USACO07MAR]Face The Right Way G
利用差分。

P1147 连续自然数和
直接暴力居然可以》。。可能情况比较少，每次break减少计算量。

for(int i = 1; i <= n / 2; i++){
    int sum = 0;
    int j;
    for(j = i; j <= n; j++){
        sum += j;
        if(sum >= n) break; 
    }
    if(sum == n) cout << i << " " << j << endl;
}

还有其他巧妙方法
https://www.luogu.com.cn/problem/solution/P1147

P4086 [USACO17DEC]My Cow Ate My Homework S
这个题我想到了用前缀和，然后想找出每个区间的最小数，可以直接减去，但是没想出来方法...只想到了从前往后扫，这样找到的最小值可能会被砍掉。然后我就复制数组二分找最小值，部分TLE。
查看题解，发现从后往前扫可以找到i-n区间的最小值，有效减少时间复杂度。
具体的看我的提交记录。

P3124 [USACO15OPEN]Trapped in the Haybales S
看懂了代码，但是自己写没有想到这种思路。

【算法2-3】分治

归并排序

P1908 逆序对
归并排序的简单应用。
P1966 [NOIP2013 提高组] 火柴排队
归并排序的应用。但是这里需要想到它是归并排序。有数学定理，顺序乘积大于等于逆序乘积。
那么我们要找的就是两个数列 l1, l2 中每一个数是否按我们所说的原则一一对应，比如说一个数列第1大的数对应另一个数列第1大的数，第2大的数对应另一个第2大的数，以此类推……
所以可以在归并排序过程中求出
https://www.luogu.com.cn/problem/solution/P1966

快速幂

P1226 【模板】快速幂||取余运算

P2345 [USACO04OPEN]MooFest G
P1257 平面上的最接近点对
这两个题很神奇的暴力就AC了。。。或许可以看看题解它用到的算法是什么。

P3197 [HNOI2008]越狱
图片说明
快速幂

P1045 [NOIP2003 普及组] 麦森数
快速幂和高精度
图片说明 

#include <bits/stdc++.h>

using namespace std;
void mul(int a[], int b[]){
    int c[100000] = {0};
    c[0] = a[0] + b[0];
    if(c[0] > 500) c[0] = 500;
    for(int i = 0; i < b[0]; i++){
        for(int q = 0; q < a[0]; q++){
            c[i + q + 1] = a[q + 1] * b[i + 1] + c[i + q + 1];
            if(c[i + q + 1] >= 10){
                c[i + q + 2] = c[i + q + 2] + c[i + q + 1] / 10;
                c[i + q + 1] = c[i + q + 1] % 10;
            }
        }
    }
    for(int i = 0; i <= c[0]; i++) a[i] = c[i];
}

int main(){
    int a[5000] = {0}, b, c[50000] = {0};
    a[0] = a[1] = c[0] = 1;
    c[1] = 2;
    cin >> b;
    printf("%d\n", (int)(log10(2) * b + 1));

    if(b & 1) mul(a,c);
    b = b >> 1;
    while(b){
        mul(c, c);
        if(b & 1) mul(a, c);
        b = b >> 1;
    }
    a[1]--;
    int q = 500;
    for(int i = 0; i < 10; i++){
        for(int j = 0;j < 50; j++){
            cout << a[q];
            q--;
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

【算法2-4】倍增

RMQ求区间内极值/ST表

P2880 [USACO07JAN]Balanced Lineup G
也可以用线段树，题解里面有多种方法
https://www.luogu.com.cn/problem/solution/P2880

P1613 跑路
图片说明

【算法2-5】搜索剪枝策略

折半搜索

P4799 [CEOI2015 Day2]世界冰球锦标赛
https://www.luogu.com.cn/problem/solution/P4799
图片说明