之前（自用）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

之前（自用）

作者：

Milonia , 2024-10-23 19:41:50 , 所有人可见 , 阅读 4

1. 基础算法

1.1 快排

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

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

    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

1.2 实数二分

代码1：用于：在 > x 条件下，取范围最左位置（从小到大）
分为l,mid（满足） mid+1,r 两个区间

答案从小到大排序，找第一个满足check函数的位置；第一个满足 >x / >的位置。

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

//check(mid)  是判断mid是否符合要求

代码2：用于：在< x 条件下，去范围最右位置（从小到大）
分为mid,r（满足） l,mid-1 两个区间

答案从小到大排序，找最后一个满足check函数的位置；最后一个满足 <x / <=x 的位置。

int bsearch_2 (int l,int r){
    while (l<r) {
        int mid=(l+r+1)/2;
        if ( chech(mid) )  l=mid;
        else r=mid-1;
    }
    return l;
}

1.3 浮点数二分

代码1：用于：在 >=x 或 > x 条件下，取范围最左位置（从小到大）

double bsearch_3 (double l,double r){
    const double eps=1e-6;  //表示精度  注意灵活改变

    while (r-l>eps){
        double mid=(l+r)/2;
        if ( check(mid) ) r=mid;
        else l=mid;
    }

    return l;
}

代码2：用于：在 <=x 或 < x 条件下，取范围最右位置（从小到大）

double bsearch_3 (double l,double r){
    const double eps=1e-6;  //表示精度  注意灵活改变

    while (r-l>eps){
        double mid=(l+r)/2;
        if ( check(mid) ) l=mid;
        else r=mid;
    }

    return l;
}

1.4 高精度

1.4.1 加法

// C = A + B, A >= 0, B >= 0
#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A,vector<int> &B){
    if (A.size()<B.size()) return add(B,A);

    vector<int> C;
    int t=0;
    for (int i=0;i<A.size();i++){
        t+=A[i];
        if (i<B.size()) t+=B[i];
        C.push_back(t%10);
        t/=10;
    }

    if (t) C.push_back(t);
    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');

    auto C=add(A,B);

    for (int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}

1.4.2 减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
#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();
    for (int i=A.size()-1;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);
        if (t<0) t=1;
        else t=0;
    }

    while (C.size()>1 && C.back() ==0) C.pop_back() ;
    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]);
    } else {
        auto C=sub(B,A);
        printf("-");
        for (int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }
    return 0;
}

1.4.3 乘法（高精度 × 低精度）

// C = A * b, A >= 0, b > 0
#include <iostream>
#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++) {
        if (i<A.size()) t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    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');

    auto C=mul(A,b);

    for (int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}

1.4.4 除法（高精度 / 低精度）

// A / b = C ... r, A >= 0, b > 0
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int rr;

vector<int> div(vector<int> &A,int b,int &r){
    vector<int> C;
    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<int> A;

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

    auto C=div(A,b,rr);

    for (int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    printf("\n%d",rr);
    return 0;
}

1.5 前缀和

1.5.1 一维前缀和

$S[i] = a[1] + a[2] + … a[i]$
$a[l] + … + a[r] = S[r] - S[l - 1]$

1.5.2 二维前缀和

$S[i, j]$ = 第i行j列格子左上部分所有元素的和
以 $(x1, y1)$ 为左上角，$(x2, y2)$ 为右下角的子矩阵的和为

$S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]$

1.6 差分

1.6.1 一维差分

$B[i] = a[i] - a[i - 1]$
给区间[l, r]中的每个数加上c：$B[l] += c, B[r + 1] -= c$

1.6.2 二维差分

给以 $(x1, y1)$ 为左上角，$(x2, y2)$ 为右下角的子矩阵中的所有元素加上 $c$ ：
$S[x1, y1] += c$

$S[x2 + 1, y1] -= c$

$S[x1, y2 + 1] -= c$

$S[x2 + 1, y2 + 1] += c$

1.6.5 前缀和/差分规律

例子

s和：1 3 7 12 20 30 44 62
a原：1 2 4 5 8 10 14 18
c差：1 1 2 1 3 2 4 4

和对原（原对差上对下）：

$s[l]~s[r] +n$
$a[l]+n$ && $a[r+1]-n$

原对和（差对原下对上）：

$a[l]~a[r] +n$
$s[l]+n$ $s[l+1] +2n$
$s[l+2] +3n$
…
$s[l+x] +(l-x+1)*n$
$s[r]~s[end] +(l-r+1)*n$

1.7 双指针算法

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

    // 具体问题的逻辑
}

1.8 位运算

1.8.1 Acwing

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

1.8.2 补充

1.8.2.1 符号整理

& 两个位都为1时，结果才为1 0001&0001=1
| 两个位都为0时，结果才为0 0001|0001=0001
^ 两个位相同为0，相异为1 0001^0001=0000
~ 0变1,1变0 ~0=1, ~1=0
<< 左移-各二进位全部左移若干位，高位丢弃，低位补0
0001<<k=0100，k=2 左移k位

>>右移-各二进位全部右移若干位，对无符号数，高位补0，有符号数，右移补1
0100>>k=0001，k=2 右移k位

1.8.2.2 运算律

交换律 — A&B == B&A, A^B == B^A
结合律 — (A&B) &C == A&(B&C)
注意：只能在同符号下进行
等幂律 — A&A == A, A|A == A
零律 — A&0 == 0
互补律 — A&~A == 0, A|~A == -1
同一律 — A|0 == A, A^0 == A

1.8.2.3 高级操作（正数）

去掉最后一位      0100=>0010      x>>1
在最后加一个0     0100=>1000      x<<1 
在最后加一个1     0100=>1001      x<<1+1
将最后一位变为1    0100=>0101      x|1
将最后一位变为0    0101=>0100      (x|1)-1 由上行转变而来 
最后一位取反      0100=>0101      x^1

把右数的第k位变为1  0001=>1001  k=4     x|(1<<(k-1))
把右数的第k位变为0  1001=>0001  k=4     x&~(1<<(k-1))
    这个操作实际上就是先得到了1000，然后取反得到0111，最后利用按位与的性质其余位不变，最高位为0
把右数的第k位取反   1000=>0000  k=4     x^1(1<<(k-1))
    利用异或性质

取末k位        1011=>0011  k=2     x&(1<<k-1) 
取右数的第k位     1011=>0001  k=4     x>>(k-1)&1
    右移k-1位则是去掉了最后的k-1位，我们利用按位与即可将其提取出来 
把末k位全变为1    1000=>1111  k=3     x|(1<<k-1)
把末k位取反      0101=>1010  k=4     x^(1<<k-1)

把右边连续的1变为0      0111=>0000      x&(x+1)
把右起的第一个0变为1     0011=>0111      x|(x+1)
把右起连续的0变为1      1000=>1111      x|(x-1)
取右边连续的1         1011=>0011      (x^(x+1))>>1
去掉右起的第一个1的左边 1101=>0001     x&(x^(x-1))

1.8.2.4 高级操作（负数）

快速判断是否为-1       ~x==0 
lowbit函数-取最低位的1 x&(-x)

1.8.2.5 实现*2和/2

a<<1  <==>  a*2
a>>1  <==>  a/2

1.8.2.6 交换两个整数

void sswap(int &a,int &b){
    a ^= b;
    b ^= a;
    a ^= b;
}

1.8.2.7 判断奇偶数

x&1==1  奇数 
x&1==0  偶数

1.8.2.8 统计二进制1的个数

int count(int x){
    int cnt = 0;
    while(x){
        x = x & (x - 1);
        cnt ++;
    }
    return cnt;
}

1.9 离散化

应用场景：前提：a数组是有序的！！！

当值域很大但个数少的时候
并且要弄值来弄数组的时候
可以将值映射成从0开始到....的数

//下面三行按顺序来 
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

//二分求出x对应的离散化的值
int find(int 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.10 区间合并

将所有存在交集的区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            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;
}

2. 数据结构

2.1 单链表

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

2.2 双链表

// 0表示head，1表示结尾
// 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];
}

2.3 栈

先进后出

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0) {}

2.4 队列

先进先出

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt){}

2.5 单调栈

（肯定具有某种性质（一般来说是单调），那么可以对数据进行排除）

常见模型：找出每个数左边离它最近的比它大/小的数

int tt = 0;
for (int i = 1; i <= n; i ++ ) {
    while (tt && check(q[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

2.6 单调队列

（肯定具有某种性质（一般来说是单调），那么可以对数据进行排除）

常见模型：找出滑动窗口中的最大值/最小值

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

2.7 KMP

解决字符串匹配问题，大幅降低运行时间

2.7.1 ne数组含义

假如此时下标为5 $ababa$
前缀和后缀相同的最大前缀尾
前缀：$a$, $ab$, $aba$, $abab$
后缀：$a$, $ba$, $aba$, $baba$
第一、三行的相同取第三行的前缀的最后一项的下标
即$ne[5]=3$

字符串 $abababab$
下标 12345678
$ne[1]=ne[2]=0$ $ne[3]=1$ $ne[4]=2$
$ne[5]=3$ $ne[6]=4$ $ne[7]=5$ $ne[8]=6$

char s[],p[];
cin>>s+1>>p+1;

求Next数组：
// s[]是模式串，p[]是模板串, n是s的长度，m是p的长度
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];
        // 匹配成功后的逻辑
    }
}

2.7.2 结论

如果 $len \%\space (len-next[len]) ==0$ 就说明有循环节
$len-next[len]$ 的值，就是s的最小循环节的长度，
$len/（len-next[len]）$就是最大循环次数！
（其中 $len$ 是字符串的长度）。

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

2.9 并查集

2.9.1 朴素并查集

int p[N]; //存储每个点的祖宗节点

// 返回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;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

2.9.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所在的两个集合：
p[find(a)] = find(b);
size[b] += size[a];

2.9.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)的偏移量

2.10 模拟堆

// 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);

2.11 哈希表

2.11.1 一般哈希

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

2.11.2 字符串哈希

核心思想：将字符串看成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];
}

2.12 C++ STL

vetcor, 动态数组
string, 字符串，substr(), c_str()
queue, 队列，push(), front(), pop()
priority_queue, 优先队列, push(), top(), pop()
stack, 栈, push(), top(), pop()
deque, 双端队列
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
bitset, 压位

2.12.1 容器通用函数

 .size()：容器内的元素个数，无符号整型。
 .empty()：判断容器是否为空，返回一个 bool 值。
 .front()：返回容器第一个元素。
 .back()：返回容器最后一个元素。
 .begin()：指向容器第一个元素的指针。
 .end()：指向容器最后一个元素的下一个位置的指针。
 .swap(b)：交换两个容器的内容。
 ::iterator：迭代器。

2.12.2 vector

2.12.2.1 创建

vector<int>a; //创建一个空的vector，数据类型为int，数组名为a
vector<int>a(100); //创建一个vector，数组名为a，元素个数为100，所有数的初值都为0
vector<int>a(10,666); //创建一个vector，数组名为a，元素个数为10，所有数的初值都为666
vector<int>b(a); //b 是a 的复制
vector<int>b(a.begin()+3,a.end()-3); //复制[a.begin()+3,a.end()-3)区间内的元素到vector 中

// 创建二维数组
vector<int>a[5];//相当于创建了5 个vector，每个都是一个数组

2.12.2.2 增加元素

可以从尾部添加，也可以从中间添加

注意：在中间添加的效率很慢 O(n)

a.push_back(5); //在向量尾部增加一个元素5
a.insert(a.begin()+1,10); //在a.begin()+1 指向元素前插入一个10
a.insert(a.begin()+1,5,10); //在a.begin()+1 指向元素前插入5 个10
a.insert(a.begin()+1,b,b+3); //在a.begin()+1 指向元素前插入b 向量的区间元素

2.12.2.3 删除

a.pop_back(); //删除向量中的最后一个元素
a.erase(a.begin()+1); //删除指定位置的元素
a.erase(a.begin()+3,a.end()-3); //删除区间[first,last)中的元素
a.clear(); //清空

2.12.2.4 遍历

for(int i=0;i<a.size();i++)
    cout<<a[i]<<"\t";
for(vector<int>::iterator it=a.begin();it<a.end();it++)
    cout<<*it<<"\t";

2.12.2.5 改变存储大小

resize 可以改变当前向量的大小，如果它比当前向量大，则填充默认值；如果比当前向量小，则舍弃后面的部分

a.resize(5); //设置向量的大小为5，如果在当前向量内有8 个元素，则舍弃后面3 个

2.12.3 栈-stack

只允许在栈顶操作，不允许在中间位置进行插入和删除操作，不支持数组表示法和随机访问

 stack<int>s：创建一个空栈s，数据类型为int。
 push(x)：x 入栈。
 pop()：出栈。
 top()：取栈顶（未出栈）。
 empty()：判断栈是否为空，若为空则返回true。
 size()：求栈大小，返回栈中的元素个数。

2.12.4 队列-queue

只允许从队尾入队、从队头出队，不允许在中间位置插入和删除，不支持数组表示法和随机访问

 queue<int>q：创建一个空队q，数据类型为int。
 push(x)：x 入队。
 pop()：出队。
 front()：取队头（未出队）。
 empty()：判断队列是否为空，若为空，则返回true。
 size()：求队列大小，返回队列中的元素个数。

2.12.5 双向链表-list

可以在常数时间内插入和删除，不支持数组表示法和随机访问

函数如下：

 merge(b)：将链表 b 与调用链表合并，在合并之前，两个链表必须已经排序，合并后经过排序的链表被保存在调用链表中，b 为空。
 remove(val)：从链表中删除val 的所有节点。
 splice(pos,b)：将链表b 的内容插入pos 的前面，b 为空。
 reverse()：将链表翻转。
 sort()：将链表排序。
 unique()：将连续的相同元素压缩为单个元素。不连续的相同元素无法压缩，因此一般先排序后去重。

 push_front(x)/push_back(x)：x 从链表头或尾入。
 pop_front()/pop_back()：从链表头或尾出。
 front()/back()：返回链表头或尾元素。
 insert(p,t)：在p 之前插入t。
 erase(p)：删除p。
 clear()：清空链表。

2.12.6 双端队列-deque

可以在两端进出队，支持数组表示法和随机访问，经常在序列两端操作时应用

 push_front(x)/push_back(x)：x 从队头或队尾入队。
 pop_front()/pop_back()：从队头或队尾出队。
 front()/back()：返回队头或队尾元素。
 size()：返回队中的元素个数。
 empty()：判断队空，若为空，则返回true。
 clear()：清空双端队列。

2.12.7 优先队列-堆

priority_queue 是一个优先队列，优先级高的最先出队，默认最大值优先

可以自定义优先级控制出队顺序，如果是数值，则也可以采用加负号的方式实现最小值优先，优先队列不支持删除堆中的指定元素，只可以删除堆顶元素，如果需要删除指定元素，则可以采用懒操作

 push(x)：x 入队。
 pop()：出队。
 top()：取队头。
 size()：返回队中的元素个数。
 empty()：判断队空，若为空则返回true。 

priority_queue<int,vector<int>,less<int> >q1;    // 大根堆
priority_queue<int,vector<int>,greater<int> >q2; // 小根堆

2.12.8 bitset

暂略

2.12.9 set/multiset

set不能重复，multiset可以重复

set<int>a; //升序
set<int,greater<int> >a; //降序，注意greater<int>后面有空格，避免两个符号一起>>，有右移歧义

函数如下：

 size/empty/clear：元素个数、判空、清空。
 begin/end：开始位置和结束位置。
 insert(x)：将元素x 插入集合。
 erase(x)：删除所有等于x 的元素。
 erase(it)：删除it 迭代器指向的元素。
 find(x)：查找元素x 在集合中的位置，若不存在，则返回end。
 count(x)：统计等于x 的元素个数。
 lower_bound/upper_bound：返回大于或等于x 的最小元素位置、大于x 的最小元素位
置。

2.12.10 map/multimap-哈希表

支持双向访问，不支持随机访问

2.12.8.1 创建

map<string,int>a; //升序
map<string,int,greater<string> >a;//降序

2.12.8.2 插入

生成一对数(键,值)进行插入

a.insert(make_pair(s,i));

2.12.8.3 输出

for(map<string,int>::iterator it=a.begin();it!=a.end();it++)
    cout<<it->first<<"\t"<<it->second<<endl;

2.12.8.4 函数

 size/empty/clear：元素个数、判空、清空。
 begin/end：开始位置和结束位置。
 insert(x)：将元素x 插入集合（x 为二元组）。
 erase(x)：删除所有等于x 的元素（x 为二元组）。
 erase(it)：删除it 指向的元素（it 为指向二元组的迭代器）。
 find(k)：查找键为k 的二元组的位置，若不存在，则返回尾指针。

2.12.8.5

可以通过“[ ]”操作符直接得到键映射的值，也可以通过赋值操作改变键映射的值，例如h[key]=val

2.12.8.6 例子

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


int main() {
    map<string,int> m;
    string s;
    for (int i=1;i<=8;i++) {
        cin>>s;
        m[s]++;
    }

    cin>>s;
    cout<<m[s];
}

==>
654
321
21
54
87
654
654
6545

654

<==
3

2.12.11 algorithm

（1）min(x,y)：求两个元素的最小值。

（2）max(x,y)：求两个元素的最大值。

（3）swap(x,y)：交换两个元素。

（4）find(begin,end,x)：返回指向区间[begin,end)第1 个值为x 的元素指针。如果没找到，则返回end。

（5）count(begin,end,x)：返回指向区间[begin,end)值为x 的元素数量，返回值为整数。

（6）reverse(begin,end)：翻转一个序列。

（7）random_shuffle(begin,end)：随机打乱一个序列。

（8）unique(begin,end)：将连续的相同元素压缩为一个元素，返回去重后的尾指针。不连续的相同元素不会被压缩，因此一般先排序后去重。

（9）fill(begin,end,val)：将区间[begin,end)的每个元素都设置为val。

（10）sort(begin,end,compare)：对一个序列排序，参数begin 和end 表示一个范围，分别为待排序数组的首地址和尾地址；compare 表示排序的比较函数，可省略，默认为升序。stable_sort(begin, end, compare)为稳定排序，即保持相等元素的相对顺序。

（11）nth_element(begin,begin+k,end,compare)：使区间[begin,end)第k 小的元素处在第k 个位置上，左边元素都小于或等于它，右边元素都大于或等于它，但并不保证其他元素有序。

（12）lower_bound(begin,end,x)/upper_bound(begin,end,x)：两个函数都是利用二分查找的方法，在有序数组中查找第1 个满足条件的元素，返回指向该元素的指针。

（13）next_permutation(begin,end)/pre_permutation(begin,end)：next_permutation()是求按字典序的下一个排列的函数，可以得到全排列。pre_permutation()是求按字典序的上一个排列的函数。

3. 搜索与图论

3.1 DFS

=>递归

回溯、剪枝（可行性剪枝、非最优解剪枝）

3.2 BFS

=>队列

3.3 树与图的存储

有向图和无向图的存储是一样的

3.3.1 邻接矩阵：就是用二维数组存储

适用于：稠密图（边数是点数的平方级别）

g[a][b] 存储边a->b

3.3.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 ++ ;
}

3.4 树与图的遍历

3.4.1 深度优先遍历

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

3.4.2 宽度优先遍历

queue<int> 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 (!s[j]){
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

3.5 拓扑排序

拓扑序列：对于序列 $A$ 满足：每条边 $(x，y)$ ，$x$ 在 $A$ 中都出现在 $y$ 之前

即没有形成一个环

根据拓扑序列的概念，我们可以知道在拓扑序列 $A$ 中，至少存在一个入度为 $0$ 的点，也至少存在一个出度为 $0$ 的点

每次寻找入度为 $0$ 的点放在前面，并把与此点连接的点入度 $-1$ (即删去这条线) ，从此循环

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

int n,m;
const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int q[N],d[N];

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool toposort(){
    int hh=0,tt=-1;

    // d[i] 存储点i的入度
    for (int i=1;i<=n;i++) if (!d[i]) q[++tt]=i;

    while (hh<=tt) {
        auto p=q[hh++];
        for (int i=h[p];i!=-1;i=ne[i]) {
            int t=e[i];
            d[t]--;
            if (!d[t]) q[++tt]=t;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt==n-1;
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while (m--) {
        int a,b;  cin>>a>>b;  add(a,b);  d[b]++;
    }

    if (toposort()) {
        for (int i=0;i<n;i++) cout<<q[i]<<' ';
    } else cout<<"-1"<<endl;
    return 0;
}

3.6 Dijkstra

3.6.1 朴素Dijkstra

正权边、稠密图、单源

步骤：

对所有点的距离进行初始化 $(+\infty)$ ，起点初始化为 $0$
遍历 $n$ 次（即为点的个数）
1. 找到目前离起点最近的点(最开始就是起点)
2. 确定这个点的距离就是它的最短路，并进行标记
3. 用这个点的距离，对其他点的距离进行更新
4. 回到 $1.$

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

int n,m;
const int N=510;
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=1;i<=n;i++) {
        int t=-1;  // 在还未确定最短路的点中，寻找距离最小的点
        for (int j=1;j<=n;j++) {
            if (!st[j] && (t==-1 || dist[j]<dist[t]))
                t=j;
        }   

        st[t]=1;
        // 用t更新其他点的距离
        for (int j=1;j<=n;j++) 
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    if (dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while (m--) {
        int a,b,c;  cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }

    int t=dijkstra();
    cout<<t<<endl;
    return 0;
}

3.6.2 堆优化 Dijkstra

正权边、稀疏图、单源

步骤：

初始化，把起点加入堆
遍历堆顶的临边，更新其余点的距离

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

typedef pair<int,int> PII;

int n,m;
const int N=1.5e5+10;
int h[N],e[N],w[N],ne[N],idx;
bool st[N];   // 存储每个点的最短距离是否已确定
int dist[N];  // 存储所有点到1号点的距离

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});  // first存储距离，second存储节点编号

    while (heap.size()){
        auto p=heap.top();
        heap.pop();

        int ver=p.second,distance=p.first;
        if (st[ver]) continue;
        st[ver]=1;

        for (int i=h[ver];i!=-1;i=ne[i]) {
            int j=e[i];
            if (dist[j]>dist[ver]+w[i]) {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }

    if (dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while (m--) {
        int a,b,c; cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=dijkstra();
    cout<<t<<endl;
    return 0;
}

3.7 bellman-ford

存在负权边、限定路径次数、可以存在负权回路、单源

（用结构体存储）

步骤：

初始化
遍历次数（ $k$ 次）
遍历每一条边（ $m$条），用每一条边对每个点进行距离更新

更新的时候，用的一定得是上一层循环的 $dist$ 数据，避免发生数据串联导致错误

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

struct Edge  // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, c;
}edges[M];

int n, m, k;
int dist[N]; // dist[x]存储1到x的最短路距离
int last[N];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < k; i ++ )
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}

3.8 spfa（队列优化的Bellman-Ford算法）

存在负权边、求负权回路、单源
能判断是否存在负权回路

但如果是求最短距离，那么就不能存在负权回路

3.8.1 求最短路

步骤：

初始化 dist 数组
用队列表示目前dist 距离发生变化的数
根据队头的距离，来更新其他点的距离，如果发生变化且队列里没有这个点，那么就入队

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

int n,m;
const int N=1e5+10;
int h[N],w[N],e[N],ne[N],idx;
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N];  // 存储每个点是否在队列中

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    queue<int> q;
    q.push(1);
    st[1]=0;

    while (q.size()){
        auto p=q.front();
        q.pop();

        st[p]=0;
        for (int i=h[p];i!=-1;i=ne[i]) {
            int j=e[i];
            if (dist[j]>dist[p]+w[i]) {
                dist[j]=dist[p]+w[i];
                if (!st[j]) {
                    // 如果队列中已存在j，则不需要将j重复插入
                    st[j]=1;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for (int i=0;i<m;i++) {
        int a,b,c; cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=spfa();

    if (t==0x3f3f3f3f) puts("impossible");
    else cout<<t;
    return 0;
}

3.8.2 判断是否存在负环

步骤：

同样的用邻接表存储，同样的使用spfa 算法，但是另外开一个 cnt 数组

如果距离更新之后，也更新 cnt 数组： $cnt[j]=cnt[p]+1$

在更新的时候，如果 $cnt[j] \geq n$ 那么表明存在负环

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

int n,m;
const int N=1e4+10;
int h[N],e[N],w[N],ne[N],idx;
bool st[N]; // 存储每个点是否在队列中
int dist[N],cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

// 如果存在负环，则返回true，否则返回false。
int spfa(){
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
    queue<int> q;
    for (int i=1;i<=n;i++) q.push(i),st[i]=1;

    while (q.size()) {
        auto p=q.front();
        q.pop();
        st[p]=0;

        for (int i=h[p];i!=-1;i=ne[i]) {
            int j=e[i];
            if (dist[j]>dist[p]+w[i]) {
                dist[j]=dist[p]+w[i];
                cnt[j]=cnt[p]+1;

                if (cnt[j]>=n) return 1; 
                // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环

                if (!st[j]) {
                    st[j]=1;
                    q.push(j);
                }
            }
        }
    }
    return 0;
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for (int i=0;i<m;i++) {
        int a,b,c; cin>>a>>b>>c; add(a,b,c);
    }

    if (spfa()) cout<<"Yes";
    else cout<<"No";
    return 0;
}

3.9 Floyd

多源（多次查询）、存在负权边

背包思路

先写 $k$ ，再写 $i$ 和 $j$

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

int n,m,t;
const int N=210,INF=0x3f3f3f3f;
int g[N][N];

void floyd(){
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}


int main(){
    cin>>n>>m>>t;
    // 初始化
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i==j) g[i][j]=0;
            else g[i][j]=INF;

    while (m--) {
        int a,b,c; cin>>a>>b>>c; g[a][b]=min(g[a][b],c);
    }

    floyd();

    while (t--) {
        int a,b; cin>>a>>b;
        if (g[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<g[a][b]<<endl;
    }
    return 0;
}

3.10 Prim

求最小生成树

步骤：

找到没有在区间的最近的点 $i$
$st[i]=1$
用 $i$ 来更新其余最小生成树一定是唯一的和 $pre$ 数组（路径个数）

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

int n,m;
const int N=510,INF=0x3f3f3f3f;
int g[N][N],dist[N];  bool st[N];

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[j]<dist[t])) 
                t=j;
        }

        if (i && dist[t]==INF) return INF;
        if (i) res+=dist[t];

        for (int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
        st[t]=1;
    }
    return res;
}

int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for (int i=0;i<m;i++) {
        int a,b,c; cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }

    int t=prim();

    if (t==INF) cout<<"impossible";
    else cout<<t<<endl;

    return 0;
}

3.11 Kruskal

求最小生成树

步骤：

给所有的边排序
遍历所有边
1. 如果这条边不会与已选的边构成回路，就加入
2. 否则不要这条边

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

int n,m;
const int N=2e5+10;
int p[N];

struct Edge{
    int a,b,w;

    bool operator<(const Edge &W) {
        return w<W.w;
    }
}edges[N];

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<=m;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 0x3f3f3f3f;
    return res;
}


int main(){
    cin>>n>>m;
    for (int i=0;i<m;i++) {
        int a,b,w;cin>>a>>b>>w;edges[i]={a,b,w};
    }

    int t=kruskal();

    if (t==0x3f3f3f3f) cout<<"impossible";
    else cout<<t;
    return 0;
}

3.12 染色法判定二分图

二分图：

有两个集合，每个集合里的两个点是没有连接的，但是两个集合之间的点是有链接的

原理：

开始对任意一未染色的顶点染色。

判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。

若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

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


int n,m;
const int N=1e5+10,M=2e5+10;
int h[N],e[M],ne[M],idx;
int color[N];

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int x,int c){
    color[x]=c;

    for (int i=h[x];i!=-1;i=ne[i]) {
        int j=e[i];
        if (!color[j]) {
            if (!dfs(j,3-c)) {
                return 0;
            }
        } else if (color[j]==c) return 0;
    }
    return 1;
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while (m--) {
        int a,b;cin>>a>>b;add(a,b);add(b,a);
    }

    int fl=1;
    for (int i=1;i<=n;i++) {
        if (!color[i]) {
            if (!dfs(i,1)) {
                fl=0;
                break;
            }
        }
    }

    if (fl) cout<<"Yes";
    else cout<<"No";
    return 0;
}

3.13 匈牙利算法

二分图的匹配问题

原理：

$A$ 找 $B$ ，$C$ 找 $D$ ，如果 $E$ 只能要找 $B$ ，那么让 $A$ 找另外一个，把 $B$ 给 $E$ ......

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

int n1,n2,m;
const int N=510,M=1e5+10;
int h[N],e[M],ne[M],idx;
int match[N];bool st[N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int x){
    for (int i=h[x];i!=-1;i=ne[i]) {
        int j=e[i];
        if (!st[j]) {
            st[j]=1;
            if (match[j]==0 || find(match[j])) {
                match[j]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main(){
    cin>>n1>>n2>>m;
    memset(h,-1,sizeof h);
    while (m--) {
        int a,b; cin>>a>>b; add(a,b);
    }

    int res=0;
    for (int i=1;i<=n1;i++) {
        memset(st,0,sizeof st);
        if (find(i)) res++;
    }
    cout<<res;return 0;
}

4. 数论

4.1 快速幂

#define ll long long

ll quick_power(ll base,ll power) {
    ll res=1;
    while (power) {
        if (power&1) {
            res=res*base%mod;
        }
        power>>=1;
        base=base*base%mod;
    }
    return res;
}

4.2 求逆元

quick_power(a,MOD-2,MOD)

4.3.1 组合数1

求 $n$ 组 $C^{b}_{a}$ ，$b\leq a\leq 2000$ ，$n\leq 10^5$

定理：$C^{b}_{a}=C^{b-1}_{a-1}+C^{b}_{a-1}$

#include <iostream>
using namespace std;

const int N=2010,MOD=1e9+7;
int c[N][N];

void init() {
    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;
}

int main(){
    init();
    int t,a,b; cin>>t;
    while (t--) {
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
}

4.3.2 组合数2

求 $n$ 组 $C^{b}_{a}$ ，$b\leq a\leq 10^5$ ，$n\leq 10000$

定理：$C^{b}_{a}=\frac{a!}{b!*(a-b)!}$

#include <iostream>
using namespace std;

#define int long long

const int N=1e5+5,MOD=1e9+7;
int fact[N],infact[N];

int qp(int base,int power,int p) {
    int res=1;
    while (power) {
        if (power&1) res=res*base%MOD;
        power>>=1;
        base=base*base%MOD;
    }
    return res;
}

signed main() {
    fact[0]=infact[0]=1;
    for (int i=1;i<N;i++) {
        fact[i]=fact[i-1]*i%MOD;
        infact[i]=infact[i-1]*qp(i,MOD-2,MOD)%MOD;
    }

    // 另外一个方法求 infact
    infact[N]=qp(f1[N],MOD-2,MOD);
    for (int i=N-1;i>=0;i--)
        infact[i]=infact[i+1]*(i+1)%MOD;


    int t; cin>>t;
    while (t--) {
        int a,b;
        cin>>a>>b;
        cout<<fact[a]*infact[b]%MOD*infact[a-b]%MOD<<endl;
    }
}

4.3.3 组合数3

求 $n$ 组 $C^{b}_{a}$ ，$b\leq a\leq 10^{18}$ ，$n\leq 20$

定理：$C^{b}_{a}=C^{b\space mod\space p}_{a\space mod\space p}*C^{b\space /\space p}_{a\space /\space p}$

#include <iostream>
using namespace std;

#define int long long

int p;

int qp(int base,int power,int p) {
    int res=1;
    while (power) {
        if (power&1) res=res*base%p;
        power>>=1;
        base=base*base%p;
    }
    return res;
}

int C(int a,int b) {
    int res=1;
    for (int i=1,j=a;i<=b;i++,j--) {
        res=res*j%p;
        res=res*qp(i,p-2,p)%p;
    }
    return res;
}

int lucas(int a,int b) {
    if (a<p && b<p) return C(a,b);
    else return C(a%p,b%p)*lucas(a/p,b/p)%p;
}

signed main() {
    int t; cin>>t;
    while (t--) {
        int a,b; cin>>a>>b>>p;
        cout<<lucas(a,b)<<endl;
    }
}

5. DP

5.1 背包问题

5.1.1 01背包

有很多个物品，但是每个物品只能选1次

直接优化成一维

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

int n,m;
const int N=1010;
int v[N],w[N];
int f[N][N];

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            f[i][j]=f[i-1][j];
            if (j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }



    cout<<f[n][m];
    return 0;
}

5.1.2 完全背包

有多个物品，但每个物品可以选无限次

#include <iostream>
using namespace std;

int n,m;
const int N=1010;
int v[N],w[N];
int f[N][N];

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for (int i=1;i<=n;i++) 
        for (int j=1;j<=m;j++){
            f[i][j]=f[i-1][j];
            if (j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }

    cout<<f[n][m];
    return 0;
}

5.1.3 多重背包

有多个物品，每个物品能选的次数有限制

二进制优化之后，并用以为数组记录，后面就相当于01背包问题

最后 $n$ 要等于新的 $cnt$

所以 $cnt$ 最好要等于打包数的个数不要超过

#include <iostream>
using namespace std;

int n,m;
const int N=25000;
int v[N],w[N],f[N];

int main(){
    cin>>n>>m;
    int cnt=0;
    for (int i=1;i<=n;i++) {
        int a,b,s;
        cin>>a>>b>>s;

        int k=1;
        while (k<=s) {
            cnt++;
            v[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
        }
        if (s>0) {
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }

    n=cnt;

    for (int i=1;i<=n;i++)
        for (int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}#include <iostream>
using namespace std;

int n,m;
const int N=110;
int v[N][N],w[N][N],s[N],f[N];

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

    for (int i=1;i<=n;i++)
        for (int j=m;j>=0;j--)
            for (int l=0;l<s[i];l++)
                if (v[i][l]<=j)
                    f[j]=max(f[j],f[j-v[i][l]]+w[i][l]);

    cout<<f[m];
    return 0;
}

5.1.4 分组背包

有多组物品，每组物品里有多个物品，只能在每组物品里选一个物品

#include <iostream>
using namespace std;

int n,m;
const int N=110;
int v[N][N],w[N][N],s[N],f[N];

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

    for (int i=1;i<=n;i++)
        for (int j=m;j>=0;j--)
            for (int l=0;l<s[i];l++)
                if (v[i][l]<=j)
                    f[j]=max(f[j],f[j-v[i][l]]+w[i][l]);

    cout<<f[m];
    return 0;
}

5.2 线性DP

5.2.1 数字三角形

#include <iostream>
using namespace std;

int n;
const int N=510;
int a[N][N],dp[N][N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    for (int i=0;i<n;i++) dp[n-1][i]=a[n-1][i];

    for (int i=n-2;i>=0;i--) {
        for (int j=0;j<=i;j++) dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
    }

    cout<<dp[0][0];
    return 0;
}

5.2.2 最长上升子序列

#include <iostream>
using namespace std;

int n;
const int N=1e5+10;
int a[N],q[N];

int main(){
    cin>>n;
    for (int i=0;i<n;i++) cin>>a[i];

    int len=0;
    q[0]=-2e9;
    for (int i=0;i<n;i++) {
        int l=0,r=len;
        while (l<r) {
            int mid=(l+r+1)/2;
            if (q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,r+1);
        q[r+1]=a[i];
    }
    cout<<len;
    return 0;
}

5.3 区间DP

5.3.1 石子合并

#include <iostream>
using namespace std;

int n;
const int N=1010,INF=1e9;
int a[N],s[N];
int f[N][N];


int main(){
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    for (int len=2;len<=n;len++) 
        for (int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            f[l][r]=INF;
            for (int k=l;k<=r;k++) {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }

    cout<<f[1][n];
    return 0;
}

5.3 记忆化搜索

5.3.1 滑雪

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

int n,m;
const int N=310;
int h[N][N],f[N][N];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int dp(int x,int y){
    int &v=f[x][y];
    if (v!=-1) return v;

    v=1;
    for (int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if (a>=1 && a<=n && b>=1 && b<=m && h[a][b]<h[x][y])
            v=max(v,dp(a,b)+1);
    }
    return v;
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin>>h[i][j];


    memset(f,-1,sizeof f);
    int ans=0;

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            ans=max(ans,dp(i,j));

    cout<<ans;
}

6. 贪心

考虑排序、区间等等方案

有些可能需要从小问题开始推，一直推到全局问题

注意分析题目条件的性质、或者考虑

6.1 绝对值不等式

货仓选址

思路：

对于点 $a$ 和点 $b$ ，请问货仓在他们两个点的距离之和的最小值？

由 $|x_a-k|+|x_b-k|\geq|x_a+x_b|$ ，当且仅当 $k$ 在两点之间。

那么对于所有的点，只要货仓在每对首尾点的中间即可让距离之和最小，

即：让货仓在点的中间

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

int n;
const int N=1e5+10;
int a[N];

int main(){
    cin>>n;
    for (int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);

    int ans=0;
    for (int i=0;i<n;i++) ans+=abs(a[i]-a[n/2]);
    cout<<ans<<endl;
}

6.2 推公式

要耍杂技的牛

思路：

将所有牛按 $w_i+s_i$ 从小到大排序，最小的放在上面即可

变相理解：

$w_i$ 小、$s_i$ 大的得放在下面，因为承重能力强

$w_i$ 大、$s_i$ 小的也最好放在下面，让其他牛的承重压力变小

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

int n;
const int N=5e4+10;
pair<int,int> cow[N];


int main(){
    cin>>n;
    for (int i=0;i<n;i++) {
        int w,s;cin>>w>>s;
        cow[i]={w+s,w};
    }

    sort(cow,cow+n);
    int ans=-2e9,sum=0;
    for (int i=0;i<n;i++) {
        int w=cow[i].second,s=cow[i].first-w;
        ans=max(ans,sum-s);
        sum+=w;
    }
    cout<<ans<<endl;
    return 0;
}

0 评论

App 内打开

之前（自用）

目录

1. 基础算法

1.1 快排

1.2 实数二分

1.3 浮点数二分

1.4 高精度

1.4.1 加法

1.4.2 减法

1.4.3 乘法（高精度 × 低精度）

1.4.4 除法（高精度 / 低精度）

1.5 前缀和

1.5.1 一维前缀和

1.5.2 二维前缀和

1.6 差分

1.6.1 一维差分

1.6.2 二维差分

1.6.5 前缀和/差分规律

例子

和对原（原对差 上对下）：

原对和（差对原 下对上）：

1.7 双指针算法

1.8 位运算

1.8.1 Acwing

1.8.2 补充

1.8.2.1 符号整理

1.8.2.2 运算律

1.8.2.3 高级操作（正数）

1.8.2.4 高级操作（负数）

1.8.2.5 实现*2和/2

1.8.2.6 交换两个整数

1.8.2.7 判断奇偶数

1.8.2.8 统计二进制1的个数

1.9 离散化

1.10 区间合并

2. 数据结构

2.1 单链表

2.2 双链表

2.3 栈

2.4 队列

2.5 单调栈

2.6 单调队列

2.7 KMP

2.7.1 ne数组含义

2.7.2 结论

2.8 Trie 树

2.9 并查集

2.9.1 朴素并查集

2.9.2 维护size的并查集

2.9.3 维护到祖宗节点距离的并查集：

2.10 模拟堆

2.11 哈希表

2.11.1 一般哈希

2.11.2 字符串哈希

2.12 C++ STL

2.12.1 容器通用函数

2.12.2 vector

2.12.2.1 创建

2.12.2.2 增加元素

2.12.2.3 删除

2.12.2.4 遍历

2.12.2.5 改变存储大小

2.12.3 栈-stack

2.12.4 队列-queue

2.12.5 双向链表-list

2.12.6 双端队列-deque

2.12.7 优先队列-堆

2.12.8 bitset

2.12.9 set/multiset

2.12.10 map/multimap-哈希表

2.12.8.1 创建

2.12.8.2 插入

2.12.8.3 输出

2.12.8.4 函数

2.12.8.5

2.12.8.6 例子

2.12.11 algorithm

3. 搜索与图论

3.1 DFS

3.2 BFS

和对原（原对差上对下）：

原对和（差对原下对上）：