算法总结-----到处搜集整理的，大多数来自acwing y总

分类:热门推荐日期:2024-03-12浏览:1评论:0

文章目录

  • 算法总结-----到处搜集整理的，大多数来自acwing y总
    • 一、基础算法
      • 1、快速排序
      • 2、归并排序
      • 3、二分
        • 整数二分
        • 浮点数二分
        • 4、高精度算法
          • 高精度加法
          • 高精度减法
          • 高精度乘法
          • 高精度除法
          • 5、前缀与差分
            • 一维前缀和
            • 二维前缀和
            • 一维差分
            • 二维差分
            • 6、双指针算法
              • 最长连续不重复子序列
              • 子序列的目标和
              • 7、位运算
              • 8、离散化
              • 9、区间合并
              • 二、数据结构
                • 单链表
                • 双链表
                • 栈
                • 队列
                  • 普通队列
                  • 循环队列
                  • 单调栈
                  • 单调队列
                  • KMP算法
                  • Trie树
                    • Trie字符串统计
                    • 求最大异或对
                    • 并查集
                      • 连通块中点的数量
                      • 堆
                      • 一般哈希
                      • 字符串哈希
                      • STL简介
                      • 三、搜索与图论
                        • 树与图的存储
                        • 树与图的遍历
                        • 拓扑排序
                        • 朴素dijkstra算法
                        • 堆优化版dijkstra算法
                        • Bellman-Ford算法
                        • spfa 算法（队列优化的Bellman-Ford算法）
                        • spfa判断图中是否存在负环
                        • floyd算法
                        • 朴素版prim算法
                        • Kruskal算法
                        • 染色法判别二分图
                        • 匈牙利算法
                        • 经典题目
                          • 排列数字
                          • n皇后问题
                          • 走迷宫
                          • 树的重心
                          • 图中点的层次
                          • 有向图的拓扑排序
                          • 四、数学知识
                            • 试除法判断质数
                            • 试除法分解质因数
                            • 朴素筛法求素数
                            • 线性筛法求素数
                            • 试除法求所有约数
                            • 约数个数和约数之和
                            • 欧几里得算法
                            • 求欧拉函数
                            • 筛法求欧拉函数
                            • 快速幂
                            • 扩展欧几里得算法
                            • 高斯消元
                            • 递推法求组合数
                            • 通过预处理逆元的方式求组合数
                            • Lucas定理
                            • 分解质因数法求组合数
                            • 卡特兰数
                            • NIM游戏
                            • 公平组合游戏ICG
                            • 有向图游戏
                            • Mex运算
                            • SG函数
                            • 有向图游戏的和
                            • 定理

                              算法总结-----到处搜集整理的，大多数来自acwing y总

                              一、基础算法

                              1、快速排序

                              void quick_sort(int a[],int l,int r)
{ if(l>=r) return;
    int i = l-1,j = r+1,mid = a[l+r>>1];
    //接下来就是进行交换操作
    while(i do i++;while(a[i]mid);
        if(i 
                              2、归并排序
                               
                              //归并排序需要一个tmp数组做临时数组，用于缓存数据
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;//k用作tmp数组的下标，i是对左半部分排序的左端点，j是对右半部分排序的左端点
    while(i<=mid&&j<=r)
    { if(q[i]<=q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    //上边对部分进行了排序，但是还有一部分没有加入tmp数组，接下来对剩下的数据加入tmp数组
    while(i<=mid) tmp[k++] = q[i++];
    while(j<=r) tmp[k++] = q[j++];
    
    //现在tmp数组中的数据顺序就是排好序的了，把tmp数组复制给q数组中；就大功告成了
    for(int i = l,j = 0;i<=r;i++,j++)//需要注意的是，i是q的下标，从l开始，而j是tmp的下标(即变量k)，从0开始
    { q[i] = tmp[j];
    }
    //上面就是归并排序的全部了，注释应该写的很清晰吧
}

                               
                              ​ 归并排序中有一个经典问题，就是求逆序对数量
                               
                              //大致和归并排序差不多，主要就是要返回数据
int merge_sort(int q,int l,int r)
{ if(l>=r) return 0;
    int mid = l+r>>1;
    int res = 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{ res+=mid-i+1;//这里我也解释不太清楚，记住就好了，这里是求逆序对的关键一步
            tmp[k++] = q[j++];
        }
    }
    
    while(i<=mid) tmp[k++] = q[i++];
    while(j<=r) tmp[k++] = q[j++];
    
    for(int i = l,j = 0;i<=r;i++,j++) q[i] = tmp[j];
    
    return res;//最后返回的res就是对当前左右两部分进行归并排序中发现的逆序对的数量
}

                               
                              3、二分
                               
                              整数二分
                               
                              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;
}

                               
                              4、高精度算法
                               
                              高精度加法
                               
                              #include#include#include
using namespace std;
vector add(vector &A,vector &B)
{ int t = 0;//用于存储每次相加的值
    vector res;
    for(int i = 0;i if(i string a,b;//用于输入
    vector A,B;//用于存储输入的数，并逆序
    cin>>a>>b;
    //接下来把ab加入到集合中，并逆序
    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');
    //加下来进行加法操作
    vector res = add(A,B);
    
    //由于res中的数据是逆序的，所以输出的时候也应该逆序输出
    for(int i = res.size()-1;i>=0;i--) printf("%d",res[i]);
    return 0;
}

                               
                              高精度减法
                               
                              #includeusing namespace std;
bool cmp(vector &A, vector &B)
{ if(A.size()!=B.size()) return A.size()>B.size();
    for(int i = A.size()-1;i>=0;i--)
    { if(A[i]!=B[i]) return A[i]>B[i];
    }
    return true;
}
vector sub(vector &A, vector &B)
{ vector c;
    for(int i = 0,t = 0;i t = A[i]-t;
        if(i1&&c.back() == 0) c.pop_back();
    return c;
}
int main()
{ string a,b;
    vector 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');
    vector c;
    if(cmp(A,B))
    { c = sub(A,B);
        for(int i = c.size()-1;i>=0;i--) printf("%d",c[i]);
    }else{ c = sub(B,A);
        printf("-");
        for(int i = c.size()-1;i>=0;i--) printf("%d",c[i]);
    }
    return 0;
}

                               
                              高精度乘法
                               
                              #includeusing namespace std;
vector mul(vector &A, int b)
{ int t = 0;
    vector c;
    for(int i=0;i if(i1&&c.back()==0) c.pop_back();
    return c;
}
int main()
{ string a;
    int b;
    vector A;
    cin>>a>>b;
    for(int i = a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    vector c = mul(A,b);
    for(int i = c.size()-1;i>=0;i--) printf("%d",c[i]);
    return 0;
}

                               
                              高精度除法
                               
                              #includeusing namespace std;
vector div(vector&A,int b,int &r)
{ vectorc;
    r = 0;
    for(int i = A.size()-1;i>=0;i--)
    { r = r*10+A[i];
        c.push_back(r/b);
        r%=b;
    }
    reverse(c.begin(),c.end());
    while(c.size()>1&&c.back()==0) c.pop_back();
    return c;
}
int main()
{ string a;
    int b;
    vector A;
    cin>>a>>b;
    for(int i = a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    int r;
    vector c = div(A,b,r);
    for(int i = c.size()-1;i>=0;i--) printf("%d",c[i]);
    cout< 
                              5、前缀与差分
                               
                              一维前缀和
                               
                              #includeusing namespace std;
const int N = 1000010;
int n,m;
int a[N],s[N];
int main()
{ cin>>n>>m;
    for(int i = 1;i<=n;i++)
    { cin>>a[i];
        s[i] = s[i-1]+a[i];
    }
    while(m--)
    { int l,r;
        cin>>l>>r;
        cout< 
                              二维前缀和
                               
                              #includeusing namespace std;
int n,m,q;//q个询问
const int N = 1010;
int a[N][N],s[N][N];
int main()
{ scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j<=m;j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    while(q--)
    { int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
    }
    return 0;
}

                               
                              一维差分
                               
                              #includeusing namespace std;
const int N = 100010;
int a[N],s[N];
int n,m;
void insert(int l,int r,int c)
{ s[l]+=c;
    s[r+1]-=c;
}
int main()
{ cin>>n>>m;
    for(int i = 1;i<=n;i++)
    { cin>>a[i];
        insert(i,i,a[i]);
    }
    while(m--)
    { int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i = 1;i<=n;i++) a[i] = a[i-1]+s[i];//把a数组当成s的前缀和
    for(int i = 1;i<=n;i++) cout< 
                              二维差分
                               
                              #includeusing namespace std;
const int N =  1010;
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()
{ scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i<=n;i++)
    { for(int j = 1;j<=m;j++)
            scanf("%d",&a[i][j]);
    }
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            insert(i,j,i,j,a[i][j]);
    while(q--)
    { int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&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];
    for(int i=1;i<=n;i++)
    { for(int j = 1;j<=m;j++) printf("%d ",b[i][j]);
        puts("");
    }   
    return 0;
}

                               
                              6、双指针算法
                               
                              最长连续不重复子序列
                               
                              #includeusing namespace std;
const int N  = 100010;
int a[N],s[N];
int n;
int main()
{ cin>>n;
    int res = 0;
    for(int i = 0;i>a[i];
    for(int i = 0,j = 0;i s[a[i]]++;
        while(s[a[i]]>1) 
        { s[a[j]]--;
            j++;
        }
        res = max(res,i-j+1);
    }
    cout< 
                              子序列的目标和
                               
                              #includeusing namespace std;
const int N = 1000010;
int n,m,x;
int a[N],b[N];
int main()
{ scanf("%d%d%d",&n,&m,&x);
    for(int i = 0;i while(j>-1&&a[i]+b[j]>x)j--;
        if(a[i]+b[j]==x){ printf("%d %d",i,j);
            return 0;
        }
    }
}

                               
                              7、位运算
                               
                              #includeusing namespace std;
int lowbit(int n)//返回n的二进制数据中的最后一位1
{ return n&-n;
}
int main()
{ int n;
    cin>>n;
    while(n--)
    { int x;
        cin>>x;
        int res = 0;
        while(x) x-=lowbit(x),res++;
        cout< 
                              8、离散化
                               
                              //这道题是求区间和
//https://www.acwing.com/activity/content/problem/content/836/
#include #include 
#include  using namespace std;
 
typedef pair PII;
 
const int N = 300010;
 
int n, m;
int a[N], s[N];
 
vector alls;//用来保存真实的下标和想象的下标的映射关系
vector add, query; //原来保存操作输入的值
 
int find(int x) { //二分查找
    int  l = 0, r = alls.size() - 1;
    while (l 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);
        alls.push_back(r);
//将其左右端点也映射进来，目的是可以让我们在虚拟的映射表里找到，
//这对于我们后面的前缀和操作时是十分的方便的。如果当我们在虚拟的
//映射表里找的时候，如果没有找到左右端点，那么前缀和无法求
    }
    sort(alls.begin(), alls.end());  //排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());//去除重复元素
   // 1）erase( pos, n); 删除从pos开始的n个字符，例如erase( 0, 1)，
   // 删除0位置的一个字符，即删除第一个字符
    //（2）erase( position); 
    //删除position处的一个字符（position是个string类型的迭代器）
    //（3）erase（first，last）;删除从first到last之间的字符，
   // （first和last都是迭代器）last 不能是x.end()
    //unique 使用 必须要先过一遍sort排序。再者，unique函数返的返回值是
    //一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的
    //下一个元素。所以如果 想要得到不重复元素的个数就需要用返回值-开始地址。
    for ( auto item : add) { //先对添加里的元素映射 赋值 
        int x = find(item.first);//找到x的映射值 往原数组中加c 
        a[x] += item.second; // 处理插入
    }
    //for(auto a:b)中b为一个容器，效果是利用a遍历并获得b容器中的每一个值，
    //但是a无法影响到b容器中的元素。
    for (int i = 1; i <= alls.size(); ++i)
    { s[i] = s[i - 1] + a[i];//前缀和
    }
    for (auto item : query) { int l = find(item.first), r = find(item.second);
            cout << s[r] - s[l - 1] << endl;
    }//每个元素都对应一组{first, first}键值对（pair），
    //键值对中的第一个成员称为first，第二个成员称为second.
    return 0;
}

                               
                              9、区间合并
                               
                              #includeusing namespace std;
int n;
typedef pair PII;
vector segs;
void merge(vector &segs)
{ vector res;
    sort(segs.begin(),segs.end());
    int st = -2e9,ed = -2e9;
    for(auto seg:segs)
    { if(ed if(st!=-2e9) res.push_back({st,ed});
            st = seg.first,ed  = seg.second;
        }else ed = max(ed,seg.second);
    }
    if(st!=-2e9) res.push_back({st,ed});
    segs = res;
}
int main()
{ cin>>n;
    for(int i = 0;i int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    merge(segs);
    cout< 
                              二、数据结构
                               
                              单链表
                               
                              // head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{ head = -1;
    idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{ e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove()
{ head = ne[head];
}

                               
                              双链表
                               
                              // e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{ //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x)
{ e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{ l[r[a]] = l[a];
    r[l[a]] = r[a];
}

                               
                              栈
                               
                              // tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{}

                               
                              队列
                               
                              普通队列
                               
                              // hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{}

                               
                              循环队列
                               
                              // hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{}

                               
                              单调栈
                               
                              常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{ while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

                               
                              单调队列
                               
                              常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{ while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

                               
                              KMP算法
                               
                              // s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{ while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{ while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    { j = ne[j];
        // 匹配成功后的逻辑
    }
}

                               
                              Trie树
                               
                              int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{ int p = 0;
    for (int i = 0; str[i]; i ++ )
    { int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
// 查询字符串出现的次数
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;
        p = son[p][u];
    }
    return cnt[p];
}

                               
                              Trie字符串统计
                               
                              #includeusing namespace std;
const int N = 1000010;
int son[N][26],cnt[N],idx;
char str[N];//要操作的字符串
//定义插入操作
void insert(char str[])
{ int p = 0;
    for(int i = 0; str[i]; i++){ int u = str[i]-'a';//将每个字符映射到0-25
        if(!son[p][u]) son[p][u] = ++idx;//如果这个字符串不存在，就加一
        p = son[p][u];//更新p的值
    }
    //当结束的时候，p就是最后一个字符，让p+1
    cnt[p]++;
}
//定义查询操作
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;
        p = son[p][u];
    }
    return cnt[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;
}

                               
                              求最大异或对
                               
                              #includeusing namespace std;
const int N = 100010,M = N*31;
int a[N];//预先存储各个数字
int n;//有多少个数字
int son[M][2],idx;//Trie树
//往Trie树中插入数据
void insert(int x)
{ int p = 0;//从根节点开始
    for(int i = 30;i>=0;i--){ int u = x>>i&1;//获取x的第i位数字是0还是1
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
//在Trie树中查询能够与指定数字异或值最大的数，并返回
int query(int x)
{ int res = 0,p = 0;//res返回最终结果，p表示每个结点
    for(int i = 30;i>=0;i--){ int u = x>>i&1;//找到x的第i位数字是0还是1
        if(son[p][!u])//如果另外一个方向存在的话，就尽量转到另外那个方向，这样异或得到的值是最大的
        { p = son[p][!u];//更改结点
            res = res*2+!u;//=更改res的值相当于是移位
        }else{ p = son[p][u];
            res = res*2+u;
        }
    }
    return res;
}
int main()
{ scanf("%d",&n);
    int res = 0;//结果
    for(int i = 0;i insert(a[i]);
        int t = query(a[i]);//找到与a[i]异或得到最大的那个数字
        res = max(res,t^a[i]);
    }
    printf("%d",res);
    return 0;
}

                               
                              并查集
                               
                              (1)朴素并查集：
    int p[N]; //存储每个点的祖宗节点
    // 返回x的祖宗节点
    int find(int x)
    { if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
	//返回祖宗结点的非递归算法
	int find(int x){ int r=x;
    while(p[r]!=r) r=p[r];//查找祖宗
    int i=x,j;
    while(i!=r){ j=p[i];//临时存i的父亲节点
        p[i]=r;//更改i的父亲节点为祖宗
        i=j;//对i的父亲下手
    }
    return r;
	}
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
(2)维护size的并查集：
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
    // 返回x的祖宗节点
    int find(int x)
    { if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    { p[i] = i;
        size[i] = 1;
    }
    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
    // 返回x的祖宗节点
    int find(int x)
    { if (p[x] != x)
        { int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    { p[i] = i;
        d[i] = 0;
    }
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
(4)merge合并操作
    void merge(int a,int b)
    { p[find(a)] = find(b);
    }

                               
                              连通块中点的数量
                               
                              #includeusing namespace std;
const int N = 100010;
int n,m;
int p[N],s[N];
int find(int x)
{ if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{ scanf("%d%d",&n,&m);
    for(int i =1;i<=n;i++)
    { p[i] = i;
        s[i] = 1;
    }
    while(m--)
    { char op[5];
        int a,b;
        scanf("%s",op);
        if(op[0]=='C')
        { scanf("%d%d",&a,&b);
            if(find(a)==find(b)) continue;
            s[find(b)]+=s[find(a)];
            p[find(a)] = find(b);
        }else if(op[1]=='1'){ scanf("%d%d",&a,&b);
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }else{ scanf("%d",&a);
            printf("%d\n",s[find(a)]);
        }
    }
    return 0;
}

                               
                              堆
                               
                              // h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{ swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}
void down(int u)
{ int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    { heap_swap(u, t);
        down(t);
    }
}
void up(int u)
{ while (u / 2 && h[u] < h[u / 2])
    { heap_swap(u, u / 2);
        u >>= 1;
    }
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

                               
                              一般哈希
                               
                              (1) 拉链法
    int h[N], e[N], ne[N], idx;
    // 向哈希表中插入一个数
    void insert(int x)
    { int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }
    // 在哈希表中查询某个数是否存在
    bool find(int x)
    { int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;
        return false;
    }
(2) 开放寻址法
    int h[N];
    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    { int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        { t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

                               
                              字符串哈希
                               
                              核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{ h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{ return h[r] - h[l - 1] * p[r - l + 1];
}

                               
                              STL简介
                               
                              vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序
pair first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址
queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素
priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue, greater> q;
stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素
deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)
    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []
    count()  返回有多少个1
    any()  判断是否至少有一个1
    none()  判断是否全为0
    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

                               
                              三、搜索与图论
                               
                              树与图的存储
                               
                              树是一种特殊的图，与的图的存储方式相同
                               
                              对于无向图的边ab，可以表示为a->b,b->a
                               
                              （1）邻接矩阵：g[a][b]存储边a->b
                               
                              （2）邻接表：
                               
                              // 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);

                               
                              树与图的遍历
                               
                              时间复杂度O(n+m)，n表示点数，m表示边数
                               
                              一、深度优先搜索
                               
                              int dfs(int u)
{ st[u] = true; // st[u] 表示点u已经被遍历过
    for (int i = h[u]; i != -1; i = ne[i])
    { int j = e[i];
        if (!st[j]) dfs(j);
    }
}

                               
                              二、广度优先搜索
                               
                              queue q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{ int t = q.front();
    q.pop();
    for (int i = h[t]; i != -1; i = ne[i])
    { int j = e[i];
        if (!st[j])
        { st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

                               
                              拓扑排序
                               
                              时间复杂度O(n+m)，n表示点数，m表示边数
                               
                              bool topsort()
{ int hh = 0, tt = -1;
    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;
    while (hh <= tt)
    { int t = q[hh ++ ];
        for (int i = h[t]; i != -1; i = ne[i])
        { int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

                               
                              朴素dijkstra算法
                               
                               时间复杂度是 
         
        
          O 
         
        
          ( 
         
         
         
           n 
          
         
           2 
          
         
        
          + 
         
        
          m 
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度是O(n^2+m)，n表示点数，m表示边数 
        
       
     时间复杂度是O(n2+m)，n表示点数，m表示边数
                               
                              int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{ memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n - 1; i ++ )
    { int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

                               
                              堆优化版dijkstra算法
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
        
          m 
         
         
          
          
            log 
           
          
            ⁡ 
           
          
         
           n 
          
         
        
          ) 
         
        
          , 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度O(m\log_n),n表示点数，m表示边数 
        
       
     时间复杂度O(mlogn​),n表示点数，m表示边数
                               
                              typedef pair PII;
int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{ memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue, greater> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号
    while (heap.size())
    { auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        { int j = e[i];
            if (dist[j] > distance + w[i])
            { dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

                               
                              Bellman-Ford算法
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
        
          n 
         
        
          m 
         
        
          ) 
         
        
          , 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度O(nm),n表示点数，m表示边数 
        
       
     时间复杂度O(nm),n表示点数，m表示边数
                               
                              int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离
struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{ int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{ memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    { for (int j = 0; j < m; j ++ )
        { int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

                               
                               
                              spfa 算法（队列优化的Bellman-Ford算法）
                               
                               时间复杂度，平均情况下 
         
        
          O 
         
        
          ( 
         
        
          m 
         
        
          ) 
         
        
          ，最坏情况下 
         
        
          O 
         
        
          ( 
         
        
          n 
         
        
          m 
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度，平均情况下O(m)，最坏情况下O(nm)，n表示点数，m表示边数 
        
       
     时间复杂度，平均情况下O(m)，最坏情况下O(nm)，n表示点数，m表示边数
                               
                              int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{ memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue q;
    q.push(1);
    st[1] = true;
    while (q.size())
    { auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        { int j = e[i];
            if (dist[j] > dist[t] + w[i])
            { dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                { q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

                               
                               
                              spfa判断图中是否存在负环
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
        
          n 
         
        
          m 
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度O(nm)，n表示点数，m表示边数 
        
       
     时间复杂度O(nm)，n表示点数，m表示边数
                               
                              int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{ // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
    queue q;
    for (int i = 1; i <= n; i ++ )
    { q.push(i);
        st[i] = true;
    }
    while (q.size())
    { auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        { int j = e[i];
            if (dist[j] > dist[t] + w[i])
            { dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                { q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

                               
                               
                              floyd算法
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
         
         
           n 
          
         
           3 
          
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数 
         
        
       
         时间复杂度O(n^3)，n表示点数 
        
       
     时间复杂度O(n3)，n表示点数
                               
                              初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{ for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

                               
                               
                              朴素版prim算法
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
         
         
           n 
          
         
           2 
          
         
        
          + 
         
        
          m 
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度O(n^2+m)，n表示点数，m表示边数 
        
       
     时间复杂度O(n2+m)，n表示点数，m表示边数
                               
                              int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{ memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    { int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];
        st[t] = true;
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

                               
                               
                              Kruskal算法
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
        
          m 
         
         
          
          
            log 
           
          
            ⁡ 
           
          
         
           m 
          
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度O(m\log_m)，n表示点数，m表示边数 
        
       
     时间复杂度O(mlogm​)，n表示点数，m表示边数
                               
                              int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组
struct Edge     // 存储边
{ int a, b, w;
    bool operator< (const Edge &W)const
    { return w < W.w;
    }
}edges[M];
int find(int x)     // 并查集核心操作
{ if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int kruskal()
{ sort(edges, edges + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    { int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        { p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}

                               
                               
                              染色法判别二分图
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
        
          n 
         
        
          + 
         
        
          m 
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度O(n+m)，n表示点数，m表示边数 
        
       
     时间复杂度O(n+m)，n表示点数，m表示边数
                               
                              int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{ color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    { int j = e[i];
        if (color[j] == -1)
        { if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }
    return true;
}
bool check()
{ memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            { flag = false;
                break;
            }
    return flag;
}

                               
                               
                              匈牙利算法
                               
                               时间复杂度 
         
        
          O 
         
        
          ( 
         
        
          n 
         
        
          m 
         
        
          ) 
         
        
          ， 
         
        
          n 
         
        
          表示点数， 
         
        
          m 
         
        
          表示边数 
         
        
       
         时间复杂度O(nm)，n表示点数，m表示边数 
        
       
     时间复杂度O(nm)，n表示点数，m表示边数
                               
                              int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x)
{ for (int i = h[x]; i != -1; i = ne[i])
    { int j = e[i];
        if (!st[j])
        { st[j] = true;
            if (match[j] == 0 || find(match[j]))
            { match[j] = x;
                return true;
            }
        }
    }
    return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{ memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}

                               
                              经典题目
                               
                              排列数字
                               
                              #include#include
using namespace std;
const int N = 100010;
int path[N];
bool st[N];
int n;
void dfs(int u)
{ if(u==n+1)
    { for(int i = 1;i<=n;i++) printf("%d ",path[i]);
        puts("");
        return;
    }
    for(int i = 1;i<=n;i++)
    { if(!st[i])
        { //更新数据
            path[u] = i;
            st[i] = true;
            dfs(u+1);//继续往下递归
            //回溯
           	st[i] = false;
        }
    }
}
int main()
{ cin>>n;
    dfs(1);
    return 0;
}

                               
                              n皇后问题
                               
                              #include#include
using namespace std;
const int N = 20;
char path[N][N];
bool col[N],dg[N],udg[N];
int n;
void dfs(int u)
{ if(u==n+1)
    { for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++)
                printf("%c",path[i][j]);
            puts("");
        }
        puts("");
        return;
    }
    for(int i = 1;i<=n;i++)
    { if(!col[i]&&!dg[u+i]&&!udg[n-u+i])
        { path[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true;
            
            dfs(u+1);
            
            path[u][i] = '.';
            col[i] = dg[u+i] = udg[n-u+i] = false;
        }
    }
}
int main()
{ cin>>n;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            path[i][j] = '.';
    dfs(1);
    
    return 0;
}

                               
                              走迷宫
                               
                              #include#include
#include#includeusing namespace std;
const int N = 110;
typedef pair PII;
int path[N][N];//用于记录图中的数据
int d[N][N];//用于记录每个点到起始点的距离
int n,m;//图的高度和宽度
queue q;
int bfs()
{ int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};//定义向量
    memset(d,-1,sizeof d);//将所有点的距离设为-1
    d[0][0] = 0;//将起始点的距离设为0;
    q.push({0,0});//将起始点的坐标加入队列
    while(!q.empty())
    { PII h = q.front();//取出队头元素
        q.pop();//每次取出队头元素之后，就应该删除队头元素
        //接下来对该元素的上下左右进行遍历
        for(int i = 0;i<4;i++)
        { int x = h.first+dx[i],y = h.second+dy[i];//设置某个方向上点的坐标
            //接下来判断该点是否满足条件，如果满足条件，那么就修改该点的距离，并加入队列以供下次遍历
            if(x>=0&&x=0&&y d[x][y] = d[h.first][h.second]+1;//修改距离
                q.push({x,y});//加入队列
            }
        }
    }
    
    
    return d[n-1][m-1];
}
int main()
{ cin>>n>>m;
    for(int i = 0;i>path[i][j];
    cout< 
                              树的重心
                               
                              #include#include#include
using namespace std;
const int N = 1000010,M = 2*N;
int h[N],e[M],ne[M],idx;
int n;
int ans = N;//初始化一个比较大的值，以便于后面做比较
bool st[N];
void add(int a,int b)
{ e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dfs(int u)
{ st[u] = true;
    int sum = 1,res = 0;//sum存储以u为根节点的子树的结点个数，res存储删除结点u之后各个连通块中sum的最大值
    for(int i = h[u];i!=-1;i = ne[i])
    { int j = e[i];
        if(!st[j])
        { int s = dfs(j);
            sum+=s;
            res = max(s,res);
        }
    }
    res = max(res,n-sum);/*上面的res仅仅是所有子树中sum的最大值，要求所有连通块的最大值，还需要与剩余部分进行比较，
                            而剩余部分的结点个数是n-sum，所以res的最终值是max(res,n-sum)*/
    ans = min(ans,res);/*找到删除结点u之后各个连通块结点数最大值之后，更新结果，取较小值*/
    
    return sum;//返回以u为根节点的树的总结点数
}
int main()
{ cin>>n;
    memset(h,-1,sizeof h);
    for(int i = 1;i int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    
    dfs(1);
    cout< 
                              图中点的层次
                               
                              #include#includeusing namespace std;
const int N = 100010;
int n,m;//要输入的数据
int d[N],q[N];//距离数组和队列
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{ e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int bfs()
{ int hh = 0,tt = 0;
    q[0] = 1;
    memset(d,-1,sizeof d);
    d[1] = 0;
    
    while(hh<=tt)
    { int t = q[hh++];
        for(int i = h[t];i!=-1;i = ne[i])
        { int j = e[i];
            if(d[j] == -1)
            { d[j] = d[t]+1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}
int main()
{ cin>>n>>m;
    memset(h,-1,sizeof h);
    
    
    for(int i = 0;i int a,b;
        cin>>a>>b;
        add(a,b);
    }
    
    cout< 
                              有向图的拓扑排序
                               
                              #include#include#include
using namespace std;
const int N = 100010;
int n,m;
int d[N],q[N];
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{ e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
bool topsort()
{ int hh = 0,tt = -1;
    for(int i = 1;i<=n;i++)
    { if(!d[i]) q[++tt] = i;
    }
    
    while(hh<=tt)
    { int t = q[hh++];
        for(int i = h[t];i!=-1;i = ne[i])
        { int j = e[i];
            d[j] --;
            if(!d[j]) q[++tt] = j;
        }
    }
    return tt == n-1;
}
int main()
{ cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i = 0;i int a,b;
        cin>>a>>b;
        add(a,b);
        d[b] ++;
    }
    
    if(topsort())
    { for(int i = 0;i 
                              四、数学知识
                               
                              试除法判断质数
                               
                              bool is_prime(int x)
{ if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

                               
                              试除法分解质因数
                               
                              void divide(int x)
{ for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        { int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

                               
                              朴素筛法求素数
                               
                              int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n)
{ for (int i = 2; i <= n; i ++ )
    { if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

                               
                              线性筛法求素数
                               
                              int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n)
{ for (int i = 2; i <= n; i ++ )
    { if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        { st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

                               
                              试除法求所有约数
                               
                              vector get_divisors(int x)
{ vector res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        { res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

                               
                              约数个数和约数之和
                               
                              如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

                               
                              欧几里得算法
                               
                              int gcd(int a, int b)
{ return b ? gcd(b, a % b) : a;
}

                               
                              求欧拉函数
                               
                              int phi(int x)
{ int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        { res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

                               
                              筛法求欧拉函数
                               
                              int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉
void get_eulers(int n)
{ euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    { if (!st[i])
        { primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        { int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            { euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }

                               
                              快速幂
                               
                              求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{ int res = 1 % p, t = m;
    while (k)
    { if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

                               
                              扩展欧几里得算法
                               
                              // 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{ if (!b)
    { x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

                               
                              高斯消元
                               
                              // a[N][N]是增广矩阵
int gauss()
{ int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    { int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if (fabs(a[t][c]) < eps) continue;
        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];
        r ++ ;
    }
    if (r < n)
    { for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];
    return 0; // 有唯一解
}

                               
                              递推法求组合数
                               
                              // c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

                               
                              通过预处理逆元的方式求组合数
                               
                              首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{ int res = 1;
    while (k)
    { if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{ fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

                               
                              Lucas定理
                               
                              若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int qmi(int a, int k, int p)  // 快速幂模板
{ int res = 1 % p;
    while (k)
    { if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{ if (a < b) return 0;
    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    { x = (LL)x * i % p;
        y = (LL) y * j % p;
    }
    return x * (LL)qmi(y, p - 2, p) % p;
}
int lucas(LL a, LL b, int p)
{ if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

                               
                              分解质因数法求组合数
                               
                              当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘
int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
bool st[N];     // 存储每个数是否已被筛掉
void get_primes(int n)      // 线性筛法求素数
{ for (int i = 2; i <= n; i ++ )
    { if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        { st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int get(int n, int p)       // 求n！中的次数
{ int res = 0;
    while (n)
    { res += n / p;
        n /= p;
    }
    return res;
}
vector mul(vector a, int b)       // 高精度乘低精度模板
{ vector c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    { t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    { c.push_back(t % 10);
        t /= 10;
    }
    return c;
}
get_primes(a);  // 预处理范围内的所有质数
for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
{ int p = primes[i];
    sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector res;
res.push_back(1);
for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

                               
                              卡特兰数
                               
                              给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)

                               
                              NIM游戏
                               
                              给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。
定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0

                               
                              公平组合游戏ICG
                               
                              若一个游戏满足：
	1、由两名玩家交替行动；
	2、在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
	3、不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

                               
                              有向图游戏
                               
                              给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

                               
                              Mex运算
                               
                              设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x属于自然数，且x不属于S

                               
                              SG函数
                               
                              在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

                               
                              有向图游戏的和
                               
                              设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

                               
                              定理
                               
                              有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号