头像

SolitudeAlma

中山大学南方学院




离线:7小时前



SolitudeAlma
14小时前

今天我们来讲一下二维差分

更好的阅读体验

什么是二维差分呢?

相信了解一维差分的小伙伴都知道,差分和前缀和其实是互逆的。二位前缀和是计算矩阵中的一个点包括其和左上角的所有点的值的和,那么差分的作用就是在时间复杂度是 $O(1)$ 的情况下对一个矩阵操作,比如某区域的点都加上一个数。

那么我们应该怎么构建差分数组呢,其实和一维差分差不多,只不过是多了一维。那么有了一维差分的构建经验对于二位差分我们直接用插入函数即可,原理下面会说。

由一维差分我们可以知道, a[i]b[1]...b[i] 的前缀和,如果我们要对区间 [l , r] 中的数都加上一个数c的话只需要让 b[l] += c 并且 b[r + 1] -= c 即可,这样用差分数组构建新数组时,区间 [l , r] 中的数都会在原基础上加上c。

如果我们把这个区间放缩一下,并且让数组元素都为0的这个数组a作为我们的原数组,那么数组a的差分数组b也是全为0,这样我们就构成了差分数组,那么我们真正需要输入到数组中的数就可以利用二位差分的性质进行了,也就是当区间 l = r时,我们让其加上一个需要输入的数,这样既输入了数据,也构成了差分数组。

我们来看一下对任意子矩阵都加上一个数的话,应该怎么利用差分数组。

二维差分

从图中我们可以很清楚的看到,如果在x1,y1上加一个数c那么它右下角的数都会加上c,那么该怎么办呢,其实这也是容斥定理。我们只需要减去右边多加的部分和下边多加的部分最后再加上重复减去的部分即可

那么代码该怎么写呢,我们来看看模板吧


给以(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

其实挺简单的,我们来做一道模板题熟悉一下吧

AcWing 798.差分矩阵

题目描述

输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数n,m,q。

接下来n行,每行包含m个整数,表示整数矩阵。

接下来q行,每行包含5个整数x1, y1, x2, y2, c,表示一个操作。

输出格式

共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

数据范围

$1≤n,m≤1000,$
$1≤q≤100000,$
$1≤x1≤x2≤n,$
$1≤y1≤y2≤m,$
$−1000≤c≤1000,$
$−1000≤矩阵内元素的值≤1000$

输入样例:

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例:

2 3 4 1
4 3 4 1
2 2 2 2

C++代码


#include <cstdio>

using 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[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= 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]);
            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];
            printf("%d " , b[i][j]);
        }
        puts("");
    }
    return 0;
}

引用

引用一些大佬的题解

p_c AcWing 798. 差分矩阵

dongwa_zzuli AcWing 798. 差分矩阵_java

vanilla AcWing 798. 差分矩阵




SolitudeAlma
20小时前
#include <cstdio>

using namespace std;

const int N = 30;
int n , m;
int st[N];

void dfs(int u , int start)
{
    if(u - 1 + n - start + 1 < m) return; 
    if(u == m + 1)
    {
        for(int i = 1; i <= m; i ++) printf("%d " , st[i]);
        printf("\n");
        return;
    }

    for(int i = start; i <= n; i ++)
    {
        st[u] = i;
        dfs(u + 1 , i + 1);
        st[u] = 0;
    }
}

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

    dfs(1 , 1);

    return 0;
}


活动打卡代码 AcWing 717. 简单斐波那契

#include <cstdio>

using namespace std;

const int N = 50;

int n;
long long a[N];

int f(int n)
{
    if(n == 1) a[n] = 0;
    else if(n == 2) a[n] = 1;
    else if(n == 3) a[n] = 1;
    else 
    {
        if(!a[n]) a[n] = f(n - 1) + f(n - 2);
        return a[n];
    }

    return a[n];
}

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

    f(n);
    for(int i = 1; i <= n; i ++) printf("%lld " , a[i]);

    return 0;
}



#include <cstdio>

using namespace std;

const int N = 10;

int n;
int st[N];
bool used[N];

void dfs(int u)
{
    if(u > n)
    {
        for(int i = 1; i <= n; i ++)
           printf("%d " , st[i]);
        puts("");

        return;
    }

    for(int i = 1; i <= n; i ++)
    {
        if(!used[i])
        {
            st[u] = i;
            used[i] = true;
            dfs(u + 1);
            st[u] = 0;
            used[i] = false;
        }
    }
}

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

    dfs(1);

    return 0;
}



#include <iostream>

using namespace std;

const int N = 16;

int n , st[N];

void dfs(int u)
{

    if(u > n)
    {
        for(int i = 1; i <= n; i ++)
            if(st[i] == 1) cout << i << ' ';
        puts("");

        return;
    }

    st[u] = 2;
    dfs(u + 1);
    st[u] = 0;

    st[u] = 1;
    dfs(u + 1);
    st[u] = 0;
}

int main()
{
    cin >> n;

    dfs(1);

    return 0;
}



今天我们来讲一下二位前缀和

更好的阅读体验

什么叫二位前缀和呢?

给我们一个 $n \times m$ 的矩阵,矩阵中任意一点的左上角的点的数之和加上这个点的值为该点的二维前缀和 $s[i][j]=\sum_{i=1…i}^{j=1…j} a[i][j]$。

那么我们应该怎么用公式求呢?

首先我们用s数组来表示前缀和,那么 s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i- 1][j - 1] + a[i][j] ,即这一个点的二位前缀和等于它左边的点和上面的点的前缀和之和减去左上角的点的前缀和(即多加的部分)再加上这个点的值就是该点的二维前缀和,其实就是容斥定理。可以结合下图理解。

二位前缀和

橙色部分是左边的点的前缀和,红色部分是上面的点的前缀和,绿色的点是重复部分,褐色是当前的点

既然我们求出了每一个点对应的二维前缀和,那么如果需要求子矩阵的二维前缀和呢,该怎么求。

其实也很简单,从定义出发,以(x1,y1)为左上角,(x2,y2)为右上角的子矩阵的前缀和可以看成是(x2,y2)的前缀和减去(x2,y1-1)的前缀和再减去(x1-1,y2)的前缀和最后再加上(x1-1,y1-1)的前缀和即可。用公式表示就是 s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] 。可以结合下图理解。

任意子矩阵二位前缀和

红色部分为所求区域,绿色和橙色是多余部分要减去,而灰色部分是多减了要加回来。

到这里相信你也懂得了怎么求矩阵的二维前缀和,那么我们直接上模板吧


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]

接着我们来做一道模板题

AcWing 796.子矩阵的和

题目描述

输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数n,m,q。

接下来n行,每行包含m个整数,表示整数矩阵。

接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。

输出格式

共q行,每行输出一个询问的结果。

数据范围

$1≤n,m≤1000,$
$1≤q≤200000,$
$1≤x1≤x2≤n,$
$1≤y1≤y2≤m,$
$−1000≤矩阵内元素的值≤1000$

输入样例:

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例:

17
27
21

C++代码

#include <cstdio>

using namespace std;

const int N = 1010;

int n , m , q;
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]) , 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;
}

引用

引用一下大佬的题解

Bug_FreeOωO AcWing 796. 子矩阵的和

zning AcWing 796. 子矩阵的和_Java



活动打卡代码 AcWing 796. 子矩阵的和

#include <cstdio>

using namespace std;

const int N = 1010;

int n , m , q;
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]) , 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;
}



今天我们来讲一下一维差分

更好的阅读体验
什么是差分呢?

其实差分和前缀和是逆运算,由定义 b[i]=a[i]-a[i-1] ;可得 $a[i] = \displaystyle\sum_{j = 1}^i b[j]$ ,那么就称b是a的差分数组。差分数组可以将对a数组任意区间的同一操作优化到$O(1)$

那么构造差分数组其实也挺简单的,用第i个元素减去第i-1个元素存入b[i]即可

常见的一维差分操作是令某一段区间的数同时加上一个数,我们利用定义出发很容易就能想到只要在区间起点位置加上一个数就行了,但是这样的话我们构成的新数组就是从起点开始以后的数都加上一个数,因为我们想要的只是一段区间,所以只需要在终点的下一个位置减去这个数即可

我们来看看模板吧

b[l] += c;
b[r + 1] -= c;

其实在我们构造一维差分数组是有一个更便捷的方法,就是将一段区间加上一个数这一操作特殊化。

我们将差分数组初始化为0,这时原数组也是0,可以看成b数组是a数组的差分数组,而a数组则是b数组的前缀和数组。那么我们需要对a数组输入数据,就可以看成是对 [i , i] 这个区间加上一个数,那么进行n次操作后我们就可以构造出一个新的差分数组了,因为后续我们需要对一段区间操作,所以利用这一性质我们可以直接合并这一操作,使其利用率更大2333

那么我们直接用模板题试一下吧

AcWing 797.差分

题目描述

输入一个长度为n的整数序列。

接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数,表示整数序列。

接下来m行,每行包含三个整数l,r,c,表示一个操作。

输出格式

共一行,包含n个整数,表示最终序列。

数据范围

$1≤n,m≤100000,$
$1≤l≤r≤n,$
$−1000≤c≤1000,$
$−1000≤整数序列中元素的值≤1000$

输入样例:

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例:

3 4 5 3 4 2

C++代码

#include <cstdio>

using namespace std;

const int N = 100010;

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

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

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

    //这里其实也可以不用a数组,用变量也行,但是可能后续需要用到和为了方便理解,所以用到了a数组
    for(int i = 1; i <= n; i ++) scanf("%d" , &a[i]) , insert(i , i , a[i]);

    while(m --)
    {
        int l , r , c;
        scanf("%d%d%d" , &l , &r , &c);
        insert(l , r , c);
    }

    // 只需对差分数组求前缀和即可得到操作后的新数组
    for(int i = 1; i <= n; i ++) b[i] = b[i - 1] + b[i] , printf("%d " , b[i]);

    return 0; 
}

引用

引用一下我觉得还不错的题解,我解释的可能稍微抽象点

dongwa_zzuli AcWing 797. 差分_java

z林深时见鹿 AcWing 797. 差分 【c++详细题解】

自由周某 AcWing 797. 差分




今天我们来讲讲一维前缀和

更好的阅读体验

首先我们来介绍一下一维前缀和,emmm其实和数列的前n项和差不多,它能在 $O(1)$ 的时间复杂度操作数组的任意子区间,比如我们要找出一段区间的和。

我们先预处理出一个前缀和数组,为了方便使用,前缀和数组下标从1开始,数组初始化时我们看作原数组是一个元素全为0的数组,这个在输入数据的同时我们就能对其一边输入一边求前缀和,当然要是不能理解,也是可以分步的

前缀和数组我们用s表示,那么 s[1] 的计算就能看成是 s[0] + a[1] ,即起始下标到当前下标的区间前缀和为 s[i - 1] + a[i] 。那么如果我们要求任意一段区间的前缀和呢?其实也很简单,区间 [l , r] 的前缀和为 a[l] + ... + a[r] 等价于 s[r] - s[l - 1]
比如我们要求区间3-5的前缀和,那么其实相当于1-5这个区间的前缀和减去1-2这个区间的前缀和
一维前缀和

模板其实也很简单

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

那么我们直接来做模板题吧

AcWing 795.前缀和

题目描述

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问,每个询问输入一对 l,r。

对于每个询问,输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数,表示整数数列。

接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。

输出格式

共m行,每行输出一个询问的结果。

数据范围

$1≤l≤r≤n,$
$1≤n,m≤100000,$
$−1000≤数列中元素的值≤1000$

输入样例:

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例:

3
6
10

C++代码

#include <cstdio>

using namespace std;

const int N = 100010;

int a[N] , s[N];

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

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

    while(m --)
    {
        int l , r;
        scanf("%d%d" , &l , &r);

        printf("%d\n" ,s[r] - s[l - 1]);
    }

    return 0;
}

引用

引用一些大佬的题解,他们解释得比较清楚

z林深时见鹿 AcWing 795. 前缀和 【c++详细题解】

Bug_FreeOωO AcWing 795. 前缀和

zning AcWing 795. 前缀和理解_Java




今天我们来介绍一下高精度除法

更好的阅读体验
什么是高精度除法呢?

我们来看看百度百科是怎么介绍高精度除法的,但是并没有搜到相关信息,逛了一圈发现也没人介绍,那我在这里就简单提一下。

一般我们计算高精度除法分为高精度除高精度和高精度除低精度,在这里我们只讲第二种,计算的过程很多时候都是不能整除的,所以我们需要计算商与余数,计算过程也非常简单。

首先我们回想一下在草稿纸上我们是如何计算的,第一步看最高位,最高位除以除数作为商的第一位,对除数求余作为下一步计算的数的一部分,每一次求余过后我们都让余数扩大10倍再加上下一位,如此往复计算即可。

那么我们来看看模板是怎么写的

vector<int> div(vector<int> &A , int b , int &r)
{
    vector<int> C;
    r = 0; //余数,这里用到了C++的引用,所以返回的时候可以不用返回余数
    // 这里正着算,从最高位开始
    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;
}

接下来试试模板题吧

AcWing 794.高精度除法

题目描述

给定两个非负整数A,B,请你计算 A / B的商和余数。

输入格式

共两行,第一行包含整数A,第二行包含整数B。

输出格式

共两行,第一行输出所求的商,第二行输出所求余数。

数据范围

$1≤A的长度≤100000,$
$1≤B≤10000$
$B 一定不为0$

输入样例:

7
2

输出样例:

3
1

C++代码

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

using namespace std;

vector<int> A;
string a;
int b;

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()
{
    cin >> a >> b;

    // 因为高精度计算往往并不是单单一个,而是两三个一起,所以我们在这里统一存入方式,避免不必要的错误
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    int r;
    auto C = div(A , b, r);

    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];
    cout << endl << r;

    return 0;
}

引用

引用一些比较好的题解,比较详细有配图

空_22 AcWing 794. 基础_高精度_高精度除法java_python_c++

zyz. AcWing 794. 高精度除法

Bug_FreeOωO AcWing 794. 高精度除法