• 思想：分治
  • 确定分界点：q[l],q[(l r)/2],q[r],随机
  • 调整范围 ：第一个区间的值小于等于x，第二个区间的值大于或等于x（重点）
  • 左右两端递归处理
• 做法

#include <iostream>  using namespace std;  const int N = 1e6   10;  int n; int q[N];  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) {         while(q[  i] < x);         while(q[--j] > x);         if(i < j) swap(q[i], q[j]);     }     quick_sort(q, l, j);     quick_sort(q, j   1, r); }  int main() {     scanf("%d", &n);     for(int i = 0; i < n; i  ) scanf("%d", &q[i]);     quick_sort(q, 0, n-1);     for(int i = 0; i < n; i  ) printf("%d ", q[i]);     return 0; } 

• 分界点处理问题

  1.  int x = q[l r>>1];  quick_sort(q,l,j);  quick_sort(q,j 1,r); 

  2.  int x = q[l r 1>>1];  quick_sort(q,l,i-1);  quick_sort(q,1,r); 

• 当主题数据加强时，尽量选择数据中点 输入数据为1、2时，可自行判断。

• 确定分界点 mid=(l r)/2
• 递归排序left，right
• 合并：合二为一

#include <iostream>  using namespace std; const int N=1000010; int n; int q[N],temp[N];  void mergersort(int l,int r){    if(l>=r) return;    int mid = l r>>1;    mergersort(l,mid),mergersort(mid 1,r);        int k=0,i=l,j=mid 1;    while(i<=mid&&j<=r){        if(q[i]<=q[j]) temp[k  ]=q[i  ];        else temp[k  ]=q[j  ];    }    while(i<=mid) temp[k  ]=q[i  ];    while(j<=r) temp[k  ]=q[j  ];        for(i=l,j=0;i<=r;i  ,j  ) q[i]=temp[j]; }  int main(){    scanf("%d",&n);    for(int i=0;i<n;i  ){        scanf("%d",&q[i]);    }    mergersort(0,n-1);    for(int i=0;i<n;i  )        printf("%d ",q[i]);            return 0; } 

算法思路：假设目标值在闭区间[l, r]中， 每次隔长度每次缩小一半时l = r我们找到了目标值。

• 当我们将区间[l, r]划分成[l, mid]和[mid 1, r]其更新操作是r = mid或者l = mid 1;，计算mid不需要加1。

 int bsearch_1(int l, int r) {     while (l < r)     {         int mid = l   r >> 1;         if (check(mid)) r = mid;         else l = mid   1;     }     return l; } 

• 当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]其更新操作是r = mid - 1或者l = mid;，此时，为了防止死循环，计算mid时需要加1。

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; } 

• 先写一个check函数
• 判定在check的情况下（true和false)，如何更新区间。
• 在check(m)==true分支如下：
  • l=mid中间点的更新方法是m=(l r 1)/2
  • r=mid中间点的更新方法是m=(l r)/2
• 该方法得到保证：
  1. 最后的l==r
  2. 搜索到达的答案是封闭区间，即a[l]是满足check()条件。

保留四位小数(1)e-6一定要多2） 

#include<iostream>  using namespace std;  double n;  int main(){     cin >> n;      double l = -1e4, r = 1e4;     while(r - l > 1e-8){         double mid = (l   r) / 2;         if(mid * mid * mid >= n) r = mid;         else l = mid;     }      printf("%lf", l);      return 0; } 

指大整数运算，包括加减乘除，这是算法开发面试中经常看到的看到的一种问题，实际上是对我们人工真实加减乘除的简单模拟。

• 因为C 中的 变量类型的一般操作 例如int、long long 大数字限制，大数字操作无法完成。

• 用数组存储，数组第0位通常存储大数个位，因为在进位时，在末尾添加数组更方便
• 加引用的作用是提高效率，这样数组就不会再复制了

#include<iostream> #include<vector> using namespace std; vector<int> sum(vector<int>& a,vector<int>& b) {     vector<int> result;     if(a.size()<b.size()) return sum(b,a);     int t=0;//进位     for(int i=0;i<a.size() || t;i  )//a.size() >= b.size()     {         if(i<a.size()) t =a[i];         if(i<b.size()) t =b[i];         result.push_back(t);         t/=10.//更新进位     }     return result; } int main() {     string a,b;     vector<int&g; c,d;
    vector<int> result;//存放结果
    cin>>a>>b;
    //按 个位 十位 百位 ...n位 存放
    for(int i=a.size()-1;i>=0;i--) c.push_back(a[i]-'0');//将字符a[i]转换成数值
    for(int i=b.size()-1;i>=0;i--) d.push_back(b[i]-'0');//将字符b[i]转换成数值
    result=sum(c,d);
    for(int i=result.size()-1;i>=0;i--) cout<<result[i];
    return 0;
}

• 和高精度加法差不多，值得注意的是
  • 减法的借位处理
  • 相减为负数的处理
  • 前导0的处理 while(C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前导0去除前导0，123-120=003，实际为300，这样去掉后面的0

• 对于 t = A[i] - B[i] - t； 可以拆为 t = A[i] - t如果B[i]合法，再t -= B[i] 这么两步来做
• 相减后t的处理 ，把 t >=0 和 t < 0 用一个式子来表示 t = (t + 10) % 10 这个木有想到
• A B大小判断，自己写的太冗余，不如单独拎出来

bool cmp(vector<int>& A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();  //直接ruturn 了就不用else

    for(int i = A.size(); i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;
}

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int>& A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();  //直接ruturn 了就不用else

    for(int i = A.size(); i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;
}

vector <int> sub(vector<int>& A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10 ); // 合而为1
        if(t < 0)  t = 1;
        else t = 0;

    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导0

    return C;
}

int main()
{
    string a ,b;
    vector<int> A, B;

    cin >> a >> b ;

    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    if (cmp(A,B)) 
    {
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }


}

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &A,int b)
{
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size()||t;i++)
    {
        t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    if(t) C.push_back(t);
    while(C.size()>1&&C.back()==0)
        C.pop_back(); 
    return C;
}
int main()
{
    string a;
    int b;
    vector<int> A;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)
        A.push_back(a[i]-'0');
    vector<int> C=mul(A,b);
    for(int i=C.size()-1;i>=0;i--)
        printf("%d",C[i]);
    return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//int r=0;
vector<int> div(vector<int> &A,int B,int &r){//r传入r的地址，便于直接对余数r进行修改
    vector<int> C;
    for(int i=0;i<A.size();i++){//对A从最高位开始处理
        r=r*10+A[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数
        C.push_back(r/B);//所得即为商在这一位的数字
        r=r%B;
    }
    //由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移，
    //因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}
int main(){
    string a;
    int B,r=0; //代表余数
    cin>>a>>B;
    vector<int> A;
    for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理
    //for(int i=0;i<A.size();i++) cout<<A[i];
    //cout<<B;
    auto C = div(A,B,r);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
    cout<<endl<<r;//输出余数
    cout<<endl;
    return 0;
}

• 算法模板

 for（int i=0, j=0; i<n ; i++){
     while(i<j && check(i,j)) j++;
     //每道题的具体逻辑
 }
 - 核心思想：
   for（int i=0; i<n ; i++){
        for（int j=0; j<n ; j++){
                O(N^2)
    运用某些性质
    将上面的朴素算法优化到O(N)

- [原题链接](www.acwing.com/solution/content/2354/)
```c++
#include <iostream>
#include <algorithm>

using namespace std;

const int N =1e5;

int n;
int q[N],w[N];

int main(){
    cin>>n;
    int res=0;
    for(int i=0;i<n;i++) cin>>q[i];
    
    for(int i=0,j=0;i<n;i++){
        w[q[i]]++;
        while(w[q[i]]>1){
            w[q[j]]--;
            j++;
        }
        res = max(res,i-j+1);
    }
    cout<<res<<endl;
}

• 作用：可以求特定区间里的和
• S[i]从1开始，S[0]=0可以处理边界问题(c++里面全局变量初始就是0了)
• 原题链接

#include <iostream>

using namespace std;

const int N=1e5+10;

int n,m;
int s[N],a[N];


int main(){
   
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]+a[i];//前缀和的初始化
        }
        int l,r;
        while(m--){
            cin>>l>>r;
            cout<<s[l]-s[r-1]<<endl;//区间和的计算
            
        }
    return 0;
}

类似于数学中的求导和积分，差分可以看成前缀和的逆运算

差分数组： 首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n]; 然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i]; 使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i] 也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。 考虑如何构造差分b数组？ 最为直接的方法 如下： a[0 ]= 0; b[1] = a[1] - a[0]; b[2] = a[2] - a[1]; b[3] =a [3] - a[2]; … b[n] = a[n] - a[n-1];

• 作用 给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;

暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。有没有更高效的做法吗? 考虑差分做法。 始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c; 然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c; 因此我们得出一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。

//差分 时间复杂度 o(m)
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i - 1];      //构建差分数组
    }
    int l, r, c;
    while (m--)
    {
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;     //将序列中[l, r]之间的每个数都加上c
        b[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = b[i] + a[i - 1];    //前缀和运算
        printf("%d ", a[i]);
    }
    return 0;
}

大佬题解 原题链接

#include <iostream>

using namespace std;
const int N =1e3+10;
int n,m,q;
int a[N][N],b[N][N];

void insert(int x1,int y1,int x2,int y2,int c){//二维差分矩阵的插入
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

int main(){
    cin>>n>>m>>q;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            insert(i,j,i,j,a[i][j]);//初始化差分矩阵，和插入二维矩阵类似，想象成1*1矩阵
        }
    }
    while(q--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];//二维矩阵求前缀和
            cout<<b[i][j]<<' ';
        }
        cout<<endl;
    }
}

- n>>k //右移 - X&1 看个位是几

2. lowbit(X) ：返回x的最后一位1的位置 lowbit(1010)返回值为10

• 作用：统计x中1的个数 [原题链接]（https://www.acwing.com/problem/content/description/25/）

class Solution {
public:
    int NumberOf1(int n) {
        int t=0;
        while(n){
            n-=n&-n;//每次减去n的最后一位1
            t++;
        }
        return t;
    }
};

x=1010 原码：000001010 x 反码：111110101 !x 补码：111110110 -x

• 值域很大但是值很少
• 为什么要离散化呢，因为存储的下标实在太大了，如果直接开这么大的数组，根本不现实，第二个原因，本文是数轴，要是采用下标的话，可能存在负值，所以也不能。
• 离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。 其实映射最大的难点是前后的映射关系，如何能够将不连续的点映射到连续的数组的下标。此处的解决办法就是开辟额外的数组存放原来的数组下标，或者说下标标志，本文是原来上的数轴上的非连续点的横坐标。 首先要明确find函数的功能，输入一个离散数组的位置（映射前的位置）x返回连续数组的位置+1（映射后的位置+1）。+1的目的是为了求区间和时少一步下标为0的判断。

vector<int> alls;
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
//二分找出x对应的离散化的值
int find(int x){//从左至右第一个大于等于x的值
    int l=0,r=all.size()-1;
    while(l<r){
        int mid =l+r>>1;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;//映射到1.2.3...n。为什么返回r + 1,这是变相的让映射后的数组从1开始。此处描述映射后的数组下标对应的数值用的是a数组。
}

• 原题链接
• 分析一下y总的代码。 主要分为5大步： 1.读输入。将每次读入的x c push_back()到add中，将每次读入的位置x push_back()到alls中，将每次读入的l r push_back()到query中。 2.排序、去重。 3.通过遍历add，完成在离散化的数组映射到的a数组中进行加上c的操作（用到find函数）。 4.初始化s数组。 5.通过遍历query，完成求区间[l,r]的和。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;//首先要明确alls中存放的是位置而不是值，也就是存放的是x而不是c。
vector<PII> add, query;

int find(int x)//第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;//和题目有关，从1开始映射
}


int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});

        alls.push_back(x);
    }

    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);//求前缀和就需要下标l r，如果不加入l r到alls中的话，第5步中遍历时query就没有办法通过输入的l r去访问a或者s。因为find函数就是输入映射前的下标，返回在alls中的下标+1。
        alls.push_back(r);
    }

    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(),alls.end()), alls.end());

    // 处理插入
    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }

    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];//因为映射从1开始到all.size()

    // 处理询问
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

• unique函数的实现(双指针)

vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i ++ )
        if (!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];
    // a[0] ~ a[j - 1] 所有a中不重复的数

    return a.begin() + j;
}

• 第一种方式：结构体(不推荐使用)

    struct Node{
        int val;
        Node *Next;
    }
    new Node();//每次调用这个函数，耗费的时间很长

• 数组模拟单链表 原题链接

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int h[N], e[N], ne[N], head, idx;
//比如ne[idx]，你可以理解为idx->next,同理 ne[ne[idx]]：ne->next>next，这样理解方便很多

//对链表进行初始化
void init(){
    head = -1;//最开始的时候，链表的头节点要指向-1，
    //为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束
    /*
    插句题外话，我个人认为head其实就是一个指针，是一个特殊的指针罢了。
    刚开始的时候它负责指向空结点，在链表里有元素的时候，它变成了一个指向第一个元素的指针

    当它在初始化的时候指向-1，来表示链表离没有内容。
    */
    idx = 0;//idx在我看来扮演两个角色，第一个是在一开始的时候，作为链表的下标，让我们好找
    //第二在链表进行各种插入，删除等操作的时候，作为一个临时的辅助性的所要操作的元素的下标来帮助操作。并且是在每一次插入操作的时候，给插入元素一个下标，给他一个窝，感动！
    }
//将x插入到头节点上
void int_to_head(int x){//和链表中间插入的区别就在于它有head头节点
    e[idx] = x;//第一步，先将值放进去
    ne[idx] = head;//head作为一个指针指向空节点，现在ne[idx] = head;做这把交椅的人换了
   
    head = idx;//head现在表示指向第一个元素了，它不在是空指针了。（不指向空气了）
    idx ++;//指针向下移一位，为下一次插入元素做准备。
}

//将x插入到下标为k的点的后面
void add(int k, int x){
    e[idx] = x;//先将元素插进去
    ne[idx] = ne[k];//让元素x配套的指针，指向它要占位的元素的下一个位置
    ne[k] = idx;//让原来元素的指针指向自己
    idx ++;//将idx向后挪
  
}

//将下标是k的点后面的点个删掉
void remove(int k){
    ne[k] = ne[ne[k]];//让k的指针指向，k下一个人的下一个人，那中间的那位就被挤掉了。
}
int main(){
    cin >> n;
    init();//初始化
    for (int i = 0; i < n; i ++ ) {
        char s;
        cin >> s;
        if (s == 'H') {
            int x;
            cin >> x;
            int_to_head(x);
        }
        if (s == 'D'){
            int k;
            cin >> k;
            if (k == 0) head = ne[head];//删除头节点
            else remove(k - 1);//注意删除第k个输入后面的数，那函数里放的是下标，k要减去1
        }
        if (s == 'I'){
            int k, x;
            cin >> k >> x;
            add(k - 1, x);//同样的，第k个数，和下标不同，所以要减1
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ' ;
    cout << endl;

    return 0;
}

原题链接

#include<iostream>
using namespace std;
const int N=1e5+10;
int e[N], l[N], r[N], idx;

void insert(int a, int x){
    e[idx]=x;
    l[idx]=a, r[idx]=r[a];
    l[r[a]]=idx, r[a]=idx++;
}
void remove (int a){
    l[r[a]]=l[a];
    r[l[a]]=r[a];
}
int main(){
    r[0]=1, l[1]=0, idx=2;
    int n;
    cin>>n;
    while(n--){
        string op;
        int k,x;
        cin>>op;
        if(op=="L"){
            cin>>x;
            insert(0, x);//! 同理  最左边插入就是 在指向 0的数的左边插入就可以了   也就是可以直接在 0的 有右边插入
        {
        }else if(op=="R"){
            cin>>x;
            insert(l[1], x);//!   0和 1 只是代表 头和尾  所以   最右边插入 只要在  指向 1的 那个点的右边插入就可以了
        }else if(op=="D"){
            cin>>k;
            remove(k+1); //idx从2开始， 所以删除的是k+1
        }else if(op=="IL"){
            cin>>k>>x;
            insert(l[k+1], x);
        }else if(op=="IR"){
            cin>>k>>x;
            insert(k+1, x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<' ';
    // !=1 一直遍历到1号节点， 也就是末尾节点
}

• 用于解决离它最近的最大/最小元素
• 分析性质 这道题目,最有用的性质,就是离自己最近,而且比自己身高高. 离自己最近:这个性质其实就是我们所谓的栈的必备性质. 身高高:看到这种类型的词汇,一定要第一时间反应,这道题目是不是拥有单调性. 原题链接

#include <iostream>

using namespace std;

const int N=1e5;
int st[N],tt;
int n;

 int main(){
     cin>>n;
     for(int i=0;i<n;i++){
         int x;
         cin>>x;
        while(tt && st[tt]>=x) tt--;//栈顶元素存在并且小于等于当前输入元素才能入栈                
         if(tt) cout<<st[tt]<<' ';
         else cout<<-1<<' ';
         
         st[++tt]=x;//操作结束后记得要入栈
         
     }
     return 0;
 }

原题链接

• 维持滑动窗口的大小 当队列不为空(hh <= tt) 且 当当前滑动窗口的大小,队列弹出队列头元素以维持滑动窗口的大小 if(hh <= tt && q[hh] < i - k + 1) hh ++;

• 构造单调递增队列 当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i) while(hh <= tt && a[q[tt]] >= a[i]) tt --; q[ ++ tt] = i;

#include <iostream>

using namespace std;

const int N =1e5;

int n,k,a[N],q[N];//q[N]存的是数组下标

int main(){
    int tt=-1,hh=0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }    
    for(int i=0;i<n;i++){
        if(hh<tt &&i-q[hh]+1>k) hh++;//判断队头是否已经滑出滑动窗口
        while(hh<=tt && a[q[tt]]>=a[i]) tt--;//构造递增队列
        q[++tt]=i;
        if(i+1>=k) cout<<a[q[hh]]<<' ';
    }
    cout<<endl;
    tt=-1,hh=0;
     for(int i=0;i<n;i++){
         if(hh<tt &&i-q[hh]+1>k) hh++;
        while(hh<=tt && a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i+1>=k) cout<<a[q[hh]]<<' ';
    }
    cout<<endl;
    return 0;
}

• char p[N],s[M];cin>> n >> p+1 >>m >>s+1;字符串的输入输出 原题链接

#include<iostream>
using namespace std;
const int N=10010,M=100010;
int n,m,ne[N];
char p[N],s[M];//S是大的串 p是子串
int main()
{
   cin>> n >> p+1 >>m >>s+1;//字符串输入，从数组下标1开始输入
   //对子串 求next数组 解决前后缀的问题 找到最大的前缀和后缀相同的位置 使得快速匹配
   for(int i=2,j=0;i<=n;i++)//j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始
   {
       while(j && p[i]!=p[j+1]) j=ne[j];//如果不能匹配就退一步 个人理解：之所以一直是S[i]和P[j+1]而非P[j]是因为：如果j+1不行的话方便直接用ne[j]进行操作。
       if(p[i]==p[j+1])  j++;//如果能就继续
       ne[i]=j;

   }
   //子串和大串的匹配过程
   for(int i=1,j=0;i<=m;i++)
   {
       while(j&&s[i]!=p[j+1]) j=ne[j];匹配不成功时 返回到先前前缀已经匹配到的位置上
       if(s[i]==p[j+1])  j++;
       if(j==n) { printf("%d ",i-n);j=ne[j];}//匹配成功
   }
 return 0;



}

• 基本用法
  1. 快速存储字符串集合
  2. 高速查找字符串的数据结构

原题链接

• 这里的☆就相当于代码中cnt[p] 要对每个字符串结尾的字母标记，比如abc，否则还以为abc不是Trie树中的元素，标记方式就是cnt[p] 不一定非得是叶子节点才能表☆，只要是字符串结尾的字母都表☆，有多少个不同的字符串就有多少个☆。
• Trie树还是堆，他们的基本单元都是一个个结点连接构成的，可以成为“链”式结构。 从y总给出的代码可以看出，idx的操作总是idx++，这就保证了不同的idx值对应不同的结点。因此可以利用idx把结构体内两个属性联系在一起了。因此，idx可以理解为结点。

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
// p 下标是p的点， p点的所有儿子都存在了son[p]中，
// son[p][0] son[p][1] 分别表示p的第一个儿子，第二个儿子...
// cnt[x]以x结尾的单词数量有多少个

// 插入字符串
void insert(char str[]) {
    int p = 0; //从根节点开始，从前往后遍历
    for (int i = 0; str[i]; i++) {//因为字符串结尾时'\0'，用'\0'判断字符串是否走到结尾
        int u = str[i] - 'a'; // 每次求出当前字母对应的子节点编号（0~25）
        if (!son[p][u])  son[p][u] = ++idx; //如果当前节点不存在对应“字母”，则创建出来。 p这个节点不存在u号这个儿子，则创建出来
        p = son[p][u]; // p向下更新（如果是走if下来的，则更新为刚创建的点,否则将当前父节点更新为该字符串对应p的儿子节点）（好难描述！）
    }
    cnt[p]++; //往字符串中插入结束时，p对应的点就是该字符串上最后一个点,cnt[p++]表示☆处，以这个点☆结尾的单词数量多了一个。
    //另外cnt[i]中要么是0或1，要么是同一个字符串出现的次数
}

int query(char str[]) {
    int p = 0; //从根节点开始，从前往后遍历
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u])  return 0; //如果不存在该子节点，直接return 0;不做插入处理，因为是查询
        p = son[p][u]; //存在该店，更新为子节点的编号
    }
    return cnt[p]; //返回字符串中出现的次数（返回以p结尾的单词数量）
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        char op[2];
        scanf("%s%s", op, str);
        if (op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

原题链接

• 基本用法

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合中

• 基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]表示x的父节点

• Q：如何判断一个节点是不是树根呢？ A：p[x]==x 原因是除根之外，p[x] 都不等于 x。

  Q：如何求 x 的集合编号呢？ A：while(p[x]!=x) x=p[x];

  Q：如何合并两个集合？ A：将某一树放在另一树某个位置即可，p[x]=y;

  Q：如何找出一个节点的所有集合？ A：找那个节点的爹，再判断他爹是不是树根，如果是就返回，不 是就找它爷爷……（爸爸的爸爸叫爷爷～）。

• 优化：如果搜一遍找到根节点，则将搜寻路径上所有点直接指向父节点

• c++读入字符串问题 scanf("%s%d%d",op,&a,&b); 用%s读入字符串，可以过滤掉空格和回车。

#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)//返回x的祖宗节点+路径压缩
{
    if(p[x]!=x) p[x]=find(p[x]);
    /*
    经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
    p[x]=x;
    */
    return p[x];
    //找到了便返回祖宗节点的值
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op=='M') p[find(a)]=find(b);//集合合并操作
        else
        if(find(a)==find(b))
        //如果祖宗节点一样,就输出yes
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

• 快速建堆： for(int i=n/2;i>=1;i--) down(q[i]);//从堆一半处开始向下调整 因为n/2处为倒数第二层 时间复杂度为O(n)

//如何手写一个堆？完全二叉树 5个操作
//1. 插入一个数         heap[ ++ size] = x; up(size);
//2. 求集合中的最小值   heap[1]
//3. 删除最小值         heap[1] = heap[size]; size -- ;down(1);
//4. 删除任意一个元素   heap[k] = heap[size]; size -- ;up(k); down(k);
//5. 修改任意一个元素   heap[k] = x; up(k); down(k);

原题链接

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少
//p指下标，h指堆
//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v)
{   
    swap(h[u],h[v]); 
     swap(hp[u],hp[v]);     
     swap(ph[hp[u]],ph[hp[v]]);            

}

void down(int u)
{
    int t=u;
    if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;
    if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;
    if(u!=t)
    {
        heap_swap(u,t);
        down(t);
    }
}
void up(int u)
{
    if(u/2>0&&h[u]<h[u/2]) 
    {
        heap_swap(u,u/2);
        up(u>>1);
    }
}

int main()
{
    int n;
    cin>>n;
    int m=0;      //m用来记录插入的数的个数
                //注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
                //对应上文 m即是hp中应该存的值
    while(n--)
    {
        string op;
        int k,x;
        cin>>op;
        if(op=="I")
        {
            cin>>x;
            m++;
            h[++cur_size]=x;
            ph[m]=cur_size;
            hp[cur_size]=m;
            //down(size);
            up(cur_size);
        }
        else if(op=="PM")    cout<<h[1]<<endl;
        else if(op=="DM")
        {
            heap_swap(1,cur_size);
            cur_size--;
            down(1);
        }
        else if(op=="D")
        {
            cin>>k;
            int u=ph[k];                //这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u,cur_size);          //因为在此处heap_swap操作后ph[k]的值已经发生 由于交换完后ph[k]的值变了，为ph[size]了，所以必须要在之前保存ph[k]的值，不然无法进行down和up操作。
            cur_size--;                    //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            up(u);
           down(u);
        }
        else if(op=="C")
        {
            cin>>k>>x;
            h[ph[k]]=x;                 //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
            down(ph[k]);                //所以可直接传入ph[k]作为参数
            up(ph[k]);
        }

    }
    return 0;
}

原题链接

• 开放寻址法

  1. 让人费解的参数：const int N = 200003; 1.1 开放寻址操作过程中会出现冲突的情况，一般会开成两倍的空间，减少数据的冲突 1.2如果使用%来计算索引， 把哈希表的长度设计为素数（质数）可以大大减小哈希冲突 比如 10%8 = 2 10%7 = 3 20%8 = 4 20%7 = 6 30%8 = 6 30%7 = 2 40%8 = 0 40%7 = 5 50%8 = 2 50%7 = 1 60%8 = 4 60%7 = 4 70%8 = 6 70%7 = 0

     这就是为什么要找第一个比空间大的质数

• memset()的用法 void * memset(void *_Dst,int _Val,size_t _Size); 这是memset的函数声明 第一个参数为一个指针，即要进行初始化的首地址 第二个参数是初始化值，注意，并不是直接把这个值赋给一个数组单元（对int来说不是这样） 第三个参数是要初始化首地址后多少个字节

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003; //开发寻找，会出现冲突的情况，一般会开成两倍的空间， 同时去下一个质数
const int null = 0x3f3f3f3f;  //这是一个大于10^9的数


int h[N];

int find(int x){
    int k = (x % N + N) % N;
    //冲突情况:当前位置不为空，并且不为x
    while(h[k] != null && h[k] != x){//符合条件的有两种情况：1.找到x 2.没找到x，但找到一个空闲位置
        k ++; 
        if(k == N) k = 0; //末尾，从头开始
    }
    return k;
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    while(n --){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x); //找到符合条件的位置
        if(*op == 'I') h[k] = x;
        else{
            if(h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

• 拉链法

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int const maxn=100003;

int h[maxn],e[maxn],ne[maxn],idx;
h[]是哈希函数的一维数组//e[]是链表中存的值//ne[]是指针存的指向的地址//idx是当前指针
void insert(int x)
{
    int k=(x%maxn + maxn)%maxn; 对负数的处理,k是哈希值

    e[idx]=x;ne[idx]=h[k];h[k]=idx++;    //如果不同单链表的idx都是从0开始单独计数，
   //那么不同链表之间可能会产生冲突。
    //这里的模型是这样的：e[]和ne[]相当于一个大池子，里面是单链表中的节点，会被所有单点表共用，idx相当于挨个分配池子中的节点的指针。
    //比如如果第0个节点被分配给了第一个单链表，那么所有单链表就只能从下一个节点开始分配，所以所有单链表需要共用一个idx。
    //h[k]意义算是一个插入的表头
}
bool find(int x)
{
    int k= (x%maxn+ maxn) %maxn;  ///为了让负数在整数有映射,负数的取模还是负数,加上maxn后为正,再%即可
    for(int i=h[k];i!=-1;i=ne[i])
        if(e[i]==x)
            return true;


return false;
}
int main(void)
{
   cin.tie(0);
   int n;
   cin>>n;
   memset(h,-1,sizeof(h));  ///所有槽都清空,对应的是单链表的头(head)[注:head存的是地址,详见单链表的课]指针为-1
   while(n--)
   {
       char op[2];
       int x;
       scanf("%s%d", op, &x);

        if(op[0]=='I') insert(x);
        else 
        {

            if(find(x)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
   }
return 0;    
}

可用于解决很多字符串难题

原题链接

• 利用 unsigned long long 自然溢出，相当于自动对2^64−1取模。 溢出不等于出错，溢出实际上就是取模，这里的溢出就是mod264

• 全称字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。

• 注意点：

  1. 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
  2. 冲突问题：通过巧妙设置P (131 或 13331) , Q (264)(264)的值，一般可以理解为不产生冲突。

• 问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和。

#include <algorithm>
#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e5 + 10, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    cin >> n >> m;
    cin >> (str + 1);
    p[0] = 1;  // p^0 =1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }

    while (m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}

变长数组，基本思想是倍增（类似于java中的ArrayList）

#include<iostream>
#include<vector>
using namespace std;

int main() {
    vector<int> a; // 最简单的初始化方式
    vector<int> a(10); // 定义一个长度为10的vector
    vector<int> a(10, 3); //定义一个长度为10的vector,并将每个元素初始化为3
    vector<int> a[10]; // 定义一个vector数组，数组大小为10
    
    // vector支持的函数
    a.size(); // vector中的元素个数
    a.empty(); // vector是否为空
    // 上面2个方法的时间复杂度是O(1), 并且其他的容器都有这2个方法
    a.clear(); // 清空
    a.front(); // 返回第一个
    a.back();
    a.push_back();
    a.pop_back();
    a.begin(); // 是第一个元素的位置
    a.end(); // 是最后一个元素的下一个位置
    // vector支持用[]进行随机寻址, 这一点与数组相同
    a[0]; // 取vector中第一个元素
    // vector支持比较运算
    vector<int> a(4, 3), b(3, 4);
    // a = [3,3,3,3]   b = [4,4,4]
    if(a < b) printf("a < b\n"); // 比较大小时是按照字典序
    
    // vector的遍历
    vector<int> a;
    for(int i = 0; i < 10; i++) a.push_back(i);
    for(int i = 0; i <a.size(); i++) cout << a[i] << " ";
    cout << endl;
    
    for(vector<int>::iterator it = a.begin(); i != a.end(); i++) cout << *i << " ";
    cout << endl;
    
    // C++ 11 的新特性, for each 遍历
    for(auto x : a) cout << x << " ";
    cout << endl;
    return 0;
}

注意：操作系统为某一个程序分配内存空间所需要的时间，与要分配的空间大小无关。只与分配次数有关。比如请求分配一个大小为1的空间，和请求分配一个大小为100的空间，所需时间是一样的。
比如，一次申请大小为1000的数组，与申请1000次大小为1的数组，它们各自所需的时间，就是1000倍的关系。
所以，变长数组，要尽量减少申请空间的次数。
所以vector的倍增，大概就是，每次数组长度不够时，就把大小扩大一倍（新申请一个大小为原先2倍的数组），并把旧数组的元素copy过来

存储一个二元组，二元组的变量类型可以任意

#include<iostream>
using namespace std;

int main() {
    pair<int,string> p;
    p.first; //第一个元素
    p.second; //第二个元素
    //pair也支持比较运算，以first为第一关键字，second为第二关键字
    // 构造一个pair
    p = make_pair(10, "hby");
    p = {10, "hby"}; // C++ 11 可以直接这样初始化
    // 当某一个事物有2个属性时，并且需要按照某一个属性进行排序时，
    // 可以将需要排序的属性放到fisrt, 另一个属性放到second
    
    // 当然也可以用pair来存3个属性, 如下
    pair<int, pair<int, int>> p;
}

字符串，常用的函数substr()，c_str()

#include<cstring>
#include<iostream>
using namespace std;

int main() {
    string a = "hby";
    a += "haha"; // 字符串拼接
    a += 'c';
    
    a.size();
    a.length(); // 两种取长度都可以
    
    a.empty();
    a.append("3");
    a.append(10, '3'); // 追加10个3
    
    a.find('b'); // 返回该字符的下标, 从左往右找到的第一个该字符
    
    a.front(); // 字符串第一个字符
    a.back(); // 字符串最后一个字符
    a.substr(1, 3); // 第一个参数是下标起始位置, 第二个参数是长度
    // 上面就是从下标为1的位置开始, 取后面长度为3的子串, 结果就是byh
    // 当第二个参数的长度, 超过了字符串的长度时, 会输出到字符串结尾为止
    a.substr(1); // 也可以省略第二个参数, 则返回下标1之后的子串
    
    a.c_str(); //返回字符串a存储字符串的起始地址
    printf("%s\n", a.c_str());
}

队列，push()，front()，back()，pop()

#include<iostream>
#include<queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1); // 向队尾插入
    q.pop(); // 弹出队头元素, 注意返回的是void
    q.front(); // 返回队头 
    q.back(); // 返回队尾
    q.size();
    q.empty();
    // queue 没有clear函数
    // 想清空一个queue怎么办? 
    q = queue<int>(); // 直接重新构造一个queue
}

优先队列，本质是个堆。push()，top()，pop()

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main() {
    // 默认是大根堆
    priority_queue<int> q;
    // 想定义一个小根堆 怎么办？
    // 1. 想插入x时, 直接插入-x
    // 2. 定义时, 直接定义成小根堆, 如下（需要借助vector）
    priority_queue<int, vector<int>, greater<int>> heap;
    
    q.push();
    q.top(); // 返回堆顶元素
    q.pop(); // 弹出堆顶元素
}

#include<iostream>
#include<stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(); // 压栈
    s.top(); // 返回栈顶
    s.pop(); // 弹出栈顶
}

双端队列。可以在队头队尾进行插入删除，并且支持随机访问

#include<iostream>
#include<deque>
using namespace std;

int main() {
    deque<int> q;
    q.clear(); // 有clear
    
    q.front();
    q.back();
    
    q.push_back();
    q.pop_back();
    
    q.push_front();
    q.pop_front();
    // 并且支持随机寻址
    q[0];
    // 支持begin()和end()迭代器
}

基于平衡二叉树（红黑树），动态维护有序序列。这些set/map支持跟排序相关的操作，如lower_bound/upper_bound方法，也支持迭代器的++和–，但是其增删改查的时间复杂度是O(logn)。

#include<iostream>
#include<set>
using namespace std;

int main() {
    set<int> s; // 不能有重复元素, 插入一个重复元素, 则这个操作会被忽略
    multiset<int> ms; // 可以有重复元素
    // set 和 multiset 支持的操作
    
    insert(1); // 时间复杂度 O(logn)
    find(1); // 查找一个数, 若不存在, 则返回end迭代器
    count(1); // 返回某个数的个数, set只会返回0或1, multiset则可能返回大于1
    erase(1); // 删除所有1的元素  时间复杂度 O(k + logn), 其中k为元素个数
    erase(??); // 输入一个迭代器, 则只会删迭代器
    // set 比较核心的操作
    lower_bound(x); //返回大于等于x的最小的数的迭代器（注意, 返回的是迭代器）
    upper_bound(x); // 返回大于x的最小的数的迭代器 （注意, 返回的是迭代器）
    // begin() , end() 迭代器
}

基于哈希表。这些set和map和上面的set/map类似。但是这些unordered的set/map的增删改查的时间复杂度是O(1)，效率比上面的更快，但不支持lower_bound()和upper_bound()，也不支持迭代器的++和– 如使用unordered_map，则需要头文件#include<unordered_map>

#include<iostream>
#include<map>
using namespace std;

int main() {
    insert(); // 插入的是一个pair
    erase(); // 输入的参数是一个pair或者迭代器
    find();
    lower_bound();
    upper_bound();
    // 可以像使用数组一样使用map
    // map的几乎所有操作的时间复杂度是 O(logn), 除了size(), empty() 
    
    map<string,int> m;
    m["hby"] = 1; // 插入可以直接这样操作
    
    cout << m["hby"] << endl; // 查找
}

比如想要开一个1024长度的bool数组，由于C++的bool类型是1个字节。 则需要1024个字节，即1KB。但实际我们可以用位来表示bool，则只需要1024个位，即128字节 bitset支持所有的位运算，以及移位

#include<iostream>
using namespace std;

int main() {
    bitset<1000> s;
    // 支持 ~, &, |, ^
    // 支持 >>, <<
    // 支持 ==, !=
    // 支持 []
    // count() 返回有多少个1
    // any() 是否至少有一个1
    // none() 是否全为0
    // set() 把所有位置置为1
    // set(k, v)  将第k位变成v
    // reset() 把所有位置变成0
    // flip() 把所有位置取反, 等价于 ~
    // flip(k) 把第k位取反
}

• DFS使用栈（stack）来实现，BFS使用队列（queue）来实现 DFS所需要的空间是树的高度h，而BFS需要的空间是2h （DFS的空间复杂度较低） DFS不具有最短路的特性，BFS具有最短路的特性

• 回溯：回溯的时候，一定要记得恢复现场 剪枝：提前判断某个分支一定不合法，直接剪掉该分支 全排列

#include <iostream>

using namespace std;

cosnt int  N=10;

int n;
int path[N];//用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
int str[N];//用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。

// x 代表当前是第几个位置的数， x 可能取值为0,1，2，3....，n
void bfs(int x){
    if(x==n){
        for(int i=1;i<n;i++) cout<<path[i]<<' ';
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[x]=i;
            st[i]=true;
            dfs(x+1);//dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
            st[i]=false;
        }
    }
}

int main()
{

    cin >> n;
    dfs(0);//从0开始
}

N皇后

• 方法一：全排列方法

#include <iostream>

using namespace std;

const int N = 20; //斜对角线 2n-1 所以开两倍N
int n;
char g[N][N];
bool col[N], dg[N], udg[N];// 同一列、对角线、斜对角线上只能有一个，分别记录的是该位置的列(斜)对角线上是否已经存在过，若均不存在，则填Q，并递归下一行

void dfs(int u) {
    if (u == n) { //有多少种满足条件的摆法就有多少次 u == n
        for (int i =0; i < n; i++) puts(g[i]);
        puts("");
        return ;
    }

    for (int i = 0; i < n; i++) //枚举第u行皇后该放在哪一列
        if (!col[i] && !dg[u + i] && !udg[i - u + n]) { // u+i和n-u+i怎么来的见图片
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true; //更新状态
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false; // 恢复现场
            g[u][i] = '.';
        }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++ ) 
        for (int j = 0; j < n; j++ )
            g[i][j] = '.';
    dfs(0);
    return 0;
}

• 方法2：从棋盘的第一个位置[1, 1]依次枚举到最后一个位置[n,n]。每个位置都有两种选择：放或者不放皇后（这就对应了两个分支）。对比解法一，此时我们就需要多维护一个针对行的状态变量了。其余逻辑和解法一类似，只是需要对每个位置的点进行枚举

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s) {
    if (y == n) x ++, y = 0; // y 出界，转到下一行第一个格子
    if (x == n) { //枚举到最后一行
        if (s == n) { // 如果此时摆的Q个数是n，说明找到了一组解，输出解
            for (int i = 0; i < n; i ++) puts(g[i]); //输出找到的一组解
            puts("");
        }
        return;
    }
    // 枚举下一个格子的两种选择，放皇后和不放皇后
    // 不放皇后
    dfs(x, y + 1, s);
    // 放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[n - x + y]) { //写成 y - x + n 不能AC，当n = 3时，不应该有答案，但是却有了错误答案
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[n - x + y] = true; //更新状态
        dfs(x , y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[n - x + y] = false; //恢复现场
        g[x][y] = '.'; //恢复现场
    }
}

int main () {
    cin >> n;
    for (int i = 0; i < n; i ++) 
        for (int j = 0; j < n; j ++)
            g[i][j] = '.';
    dfs(0,0,0); //从左上角(0, 0)开始搜，记录当前共有多少个皇后（第三个参数代表当前皇后个数，初始是0）

    return 0;
}

• 基本框架

插入一个初始状态到queue中
while(queue非空)
    把队头拿出来
    扩展队头
end

走迷宫834

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e2 + 7;
int g[N][N], d[N][N];
int n, m;


int bfs() {
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    queue <PII> q;

    memset(d, -1, sizeof d);

    d[0][0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
                d[x][y] = d[t.first][t.second]  + 1;
                q.push({x, y});
            }
        }

    }


        return d[n - 1][m - 1];
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }

    cout << bfs() << endl;

    return 0;
}

• 邻接矩阵 用一个二维数组来存，比如g[a,b]存储的就是a到b的边。邻接矩阵无法存储重复边，比如a到b之间有2条边，则存不了。（用的较少，因为这种方式比较浪费空间，对于有n个点的图，需要n2的空间，这种存储方式适合存储稠密图）
• 邻接表 使用单链表来存。对于有n个点的图，我们开n个单链表，每个节点一个单链表。单链表上存的是该节点的邻接点（用的较多）

树的重心846

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //表示重心的所有的子树中，最大的子树的结点数目

bool st[N]; //记录节点是否被访问过，访问过则标记为true
//a所对应的单链表中插入b  a作为根 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// dfs 框架
/*
void dfs(int u){
    st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) {
            dfs(j);
        }
    }
}
*/

//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
    int res = 0; //存储 删