蓝桥杯每日一题模板总结

二分

模板1

( o 为 true . 为 false )
适用情况：check( ) 左边为 true ，右边为 false 时，求最后一个 true (即图示 v )
oooooov........

int bsearch_2(int l , int r){
    while(l < r){
        mid = l + r + 1 >> 1;
        if(check(mid))//找最后一个不满足的
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

模板2

( o 为 true . 为 false )
适用情况：check( ) 左边为 false ，右边为 true 时，求第一个 true (即图示 v )
.........voooooooo

int bsearch_2(int l , int r){
    while(l < r){
        mid = l + r >> 1;
        if(check(mid))//找最后一个不满足的
            r = mid;
        else
            l = mid + 1;
    }
    return r;
}

前缀和

int a[N],n;
int sum[N];//前缀和

//初始化前缀和数组
for(int i = 1 ; i <= n ;i ++){
    scanf("%d",&a[i]);
    sum[i] = sum[i-1] + a[i];
}

//求[l,r]区间的值的和
int result = sum[r] - sum[l-1];

一维差分

定理1：

a[n] = b[1] + b[2] + ... + b[n];

证明：

当(i > 0),设b[i] = a[i] - a[i-1];
b[1] = a[1] ; 
b[2] = a[2] - a[1];
b[3] = a[3] - a[2];
...
b[n-1] = a[n-1] - a[n-1];
b[n] = a[n] - a[n-1];

推出: a[n] = b[1] + b[2] + ... + b[n];

定理2：

b[1] + b[2] + ... +b[n] + b[n+1] =a[n+1] = 0;

证明：

又因为:
a[n+1] = 0;
b[n+1] = a[n+1] - a[n];

推出: b[1] + b[2] + ... +b[n] + b[n+1] =a[n+1] = 0;

定理3：

for(int i = l ;i <= r; i ++) a[i] += v ; 等同于 b[l] += v; b[r+1] -= v;
证明：

因为：
b[1] = a[1] ; 
b[2] = a[2] - a[1];
b[3] = a[3] - a[2];
...
b[l] = a[l] - a[l-1];
...
b[r] = a[r] - a[r-1];
...
b[n] = a[n] - a[n-1];

向a数组的[l,r]区间添加 v 值后
则a[l-1] += 0,a[l] += v,
a[r+1] += 0,a[r] += v;

由b[l] = a[l] - a[l-1]  推得：b[l] += v;
由b[r+1] = a[r+1] - a[r]  推得：b[r+1] -= v;

模板：

1.初始化差分数组

int a[N],n;
int b[N];
for(int i = 1; i <= n ; i ++){
    scanf("%d",&a[i]);
    b[i] = a[i] - a[i-1];
}
b[n+1] = - a[n];

2.add():向a数组的[l,r]区间添加 v 值;

void add(int l , int r , int v){
    b[l] += v;
    b[r+1] -= v;
}

3.csum():求a[x];

int csum(int x){
    int sum = 0;
    for(int i = 1 ; i <= x ; i ++){
        sum += b[i];
    }
    return sum;
}

二维差分

int a[N][N];//原数组
int b[N][N] = {0};//差分数组

1.构建差分

void insert_b(int x1,int y1,int x2,int y2,int c){
    b[x1][y1] += c;
    b[x1][y2+1] -= c;
    b[x2+1][y1] -=c;
    b[x2+1][y2+1] +=c;
}

2.求a[i][j];

for(int i = 1; i <= n ; i ++){
    for(int j = 1 ; j <= n ; j ++){
        a[i][j] =b[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
    }

}

区间合并

pair<int,int> p[N];//区间函数

1.对区间从小到大排列

sort(p,p+n);

2.区间合并：

vector<PII> result;
void merge(int n){
    int fa = p[1].first,la = p[1].second;
    for(int i = 2 ; i <= n ; i ++){
        if(la >= p[i].first)
            la = max(la,p[i].second);
        else{
            result.push_pack({fa,la});
            fa = p[i].first;
            la = p[i].second;
        }
    }

}

双指针

for(int i = 0,j = 0; i < n ; i ++){
    while(j < i && check())
        j++;
    //操作j-i区间
}

快速幂

解决：$当 0 < k < 10^9 $时，求$ (a ^ k) mod m $

原理：k 为奇数时：$a * ( a ^ k-1 )$;
k 为偶数时：$( a * a ) $^ $k/2$;

1.求快速幂

int qmi(int a,int b,int q){//底数，指数，模
    int sum = 1 ;
    while(b != 0){
        if(b & 1)//判断power是否为奇数
            sum = (LL)(sum * a) % q ;//加LL:long long防止爆int
        a = (LL)(a * a) % q;//底数变为底数的平方
        b >>= 1;//右移一位等于/2
    }
    return sum;
}

2.求逆元 (1 / a ) mod p = a ^ (p - 1) mod p;

    int invi(int a,int p){
        //a和p互质的条件下
        qmi(a,p-2,p);
    }

树状数组

1.lowbit():求 x 二进制的第一位 1

int tr[N],n;//树状数组下标从1开始


int lowbit(int x){
    return x & -x;
}

2.add():向树状数组的下标 x 位置加 v 的值

void add(int x,int v){
    for(int i = x; i <= n ; i += lowbit(i)){
        tr[i] += v;
    }

}

3.sum():求树状数组前m项和

int sum(int m){
    int s = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        s += tr[i];
    }
    return s;
}

size并查集

初始化：

int fa[N]//存i的父亲节点
int size[N]//集合元素个数，只有祖先节点有效

for (int i = 1; i <= n; i ++ ) {
    fa[i] = i;
    size[i] = 1;
}

1.find():查找返回x的祖先节点

//循环：
int find(int x){
    while(fa[x] != x){
        x = fa[x];
    }
    return x;
}
//递归：
int find(int x){
    if(x == fa[x])
        return x;
    return find(fa[x]);
}

2.合并两个集合(合并a,b集合)

//先后顺序不可变
size[find(b)] +=size[find(a)];
fa[find(a)] = find(b);

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];
        // 匹配成功后的逻辑
    }
}