算法基础笔记

根据时间复杂度选择算法

主体内容参考下面，

算法基础简介 - OI Wiki (oi-wiki.org)

AcWing《算法基础课》第2章 数据结构 - AcWing

AcWing 算法基础课笔记 3.搜索与图论（持续更新）_acwing搜索课件-CSDN博客

ACwing算法基础课全程笔记（2021年8月12日开始重写+优化）_acwing的csp辅导课更新到什么时候-CSDN博客

y式变量翻译对照表 - AcWing

AcWing基础语法课总结(完) - AcWing

AcWing个人笔记汇总 - AcWing

一维差分

 差分数组的前缀和数组是原数组 若f()为求前缀和，a为原数组，则a = f(b) ,b为差分数组 )题目： ​ ​ 标题

下面程序的主要功能是处理一个数组的区间加操作。首先，程序定义了两个数组a和b，其中a数组用于存储原始数据，b数组用于存储每个位置的累加值（前缀和）。然后，程序使用insert函数在b数组上执行区间加操作。在执行完所有操作后，程序输出b数组的每个位置的值，即为每个位置从1到当前位置的和。

程序的实现思路是使用差分数组的方法来处理区间加操作。差分数组是一种用于处理区间加操作的数据结构，可以在O(1)的时间复杂度内完成区间加操作。具体来说，对于数组b，b[i]表示a[i]与a[i-1]的差值。当我们需要在区间[l, r]内加上c时，只需要在b[l]上加上c，在b[r+1]上减去c即可。这样，我们就可以在O(1)的时间复杂度内完成区间加操作。

最后，程序使用前缀和的方法来输出每个位置的值。前缀和是一种用于处理数组区间和的数据结构，可以在O(1)的时间复杂度内完成数组区间和的查询。具体来说，对于数组b，b[i]表示从1到i的和。当我们需要查询区间[l, r]的和时，只需要计算b[r] - b[l-1]即可。这样，我们就可以在O(1)的时间复杂度内完成数组区间和的查询。

#include using namespace std;const int N = 100010; int a[N], b[N]; //全局数组，默认初始化为全0// insert函数用于在区间[l, r]内加上cvoid insert(int l, int r, int c) {    b[l] += c; // 在l位置加上c    b[r + 1] -= c; // 在r+1位置减去c，这样可以保证区间内加上c，区间外不受影响}int main() {    int n, q; // 定义两个整数n和q，分别表示数组大小和操作次数    cin >> n >> q; // 输入n和q    for (int i = 1; i > a[i]; // 输入数组a的元素        insert(i, i, a[i]); // 初始化b[i],此时为差分数组，b[i]后缀和数组为a[i]    }    while (q--) { // 循环执行q次操作        int a, b, c;         cin >> a >> b >> c;         insert(a, b, c); // 在区间[a, b]内加上c，区间加操作时间辅助度为O(1)    }    for (int i = 1; i > x2 >> y2 >> c;         insert(x1, y1, x2, y2, c);     }    for (int i = 1; i a1>>b1){        int a[1001]={},b[1001]={},c[1001]={},lenc=0; //数组先全部初始化为0        for(int i=0;i=10){                c[lenc]-=10;//用-比%快                c[lenc+1]++;            }            lenc++;        }        if(c[lenc]==0)lenc--;        for(int i=lenc;i>=0;i--)cout> b) {        // 将字符串转换为向量         A.clear();//注意每轮清空向量        B.clear();        for (i = a.size() - 1; i >= 0; i--) {            A.push_back(a[i] - '0');        }        for (i = b.size() - 1; i >= 0; i--) {            B.push_back(b[i] - '0');        }        vector C = add(A, B);        for (i = C.size() - 1; i >= 0; i--) {            cout >i &1;//取出整数的第i位 if(!son[p][u]) son[p][u]=++idx;p=son[p][u];}}int query(int x){int p=0;int t=0;for(int i=30;i>=0;i--){int u=x>>i &1;if(son[p][!u]){p=son[p][!u];t=t*2+!u;}else{p=son[p][u];t=t*2+u;}}return t;}int main(){int n;cin>>n;for(int i=0;i>a[i];int res=0;for(int i=0;i a >> b;       //add(a, b), add(b, a); //把树作为无向图。        //add(a, b);  作为有向图，也可得出正确答案。    }    dfs(1); //可以任意选定一个节点开始遍历(相当于枚举重心在每个节点上，来迭代出答案)    cout m;    // 输入地图的行数和列数    for(int i=0;ig[i][j];    // 输入地图的每个位置的状态    cout