[AcWing算法基础课] Week1 习题课

2021-12-15 23:06:34

文章目录

AcWing 786 第k个数

1.对整个数组使用快速排序，然后直接输出从小到大排序后的第 k 个数。时间复杂度为O(nlogn)

#include <iostream>
using namespace std;

const int N=100000;
int n;
int k;
int q[N];

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;
    while(i<j){
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    return;
}

int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    printf("%d",q[k-1]);
    return 0;
}

2.快速选择算法

每次只需要递归一边的区间，时间复杂度为O(n)

找到分界点，分界点可以是q[L]、q[(L+R)/2]、q[R]或者一个随机的数组元素
调整范围，挑选出x（x是个值），使得第一个区间里（Left）的所有数都小于等于x，第二个区间（Right）里的所有数都大于等于x
统计左边（Left）所有元素的个数 s l s_l sl
判断k和 s l s_l sl的大小
如果k<= s l s_l sl，那么第k小的数一定在Left里，我们只需要递归处理Left，无需处理Right了
如果k> s l s_l sl，那么第k小的数一定在Right里，我们只需要递归处理Right，无需处理Left了
5.k表示从l到r整个区间第k小的数，那么我们把Left里的小的数全部减掉，得到右半边区间Right的第k小的数，即k- s l s_l sl

#include <iostream>
using namespace std;

const int N=100010;
int n,k;
int q[N];

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

int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    int res=quick_choose(q,0,n-1,k);
    cout<<res<<endl;
    return 0;
}

AcWing 788. 逆序对的数量

我们将所有的逆序对分为三类：

两个数同时出现在左半边
两个数同时出现在右半边
一个出现在左半边，一个出现在右半边

我们赋予递归函数的意义就是在进行归并排序的同时求出区间内部的所有逆序对的个数

那么整个区间[L,R]的逆序对的个数为：merge(Left)+merge(Right)+左右两边的逆序对的个数

有两个指针i、j，q[i]>q[j]
因为Left和Right是有序的，所以从i到mid之间的所有元素都大于q[j]，而i之前的所有元素都小于q[j]

划分区间 [L,R]–>[L,mid]和[mid+1,R]
递归处理[L,mid]和[mid+1,R]两个区间
归并求出左右两边的逆序对的数量

#include <iostream>
using namespace std;
typedef long long LL;

int n;
const int N=100010;
int q[N],temp[N];

LL merge(int q[],int l,int r){
    if(l>=r) return 0;
    LL res=0;
    int mid=(l+r)>>1;
    res=merge(q,l,mid)+merge(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r){
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else{
            res+=mid-i+1;
            temp[k++]=q[j++];
        }
    }
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
    return res;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    cout<<merge(q,0,n-1)<<endl;
    return 0;
}

求数组中的逆序对的数量在力扣上是剑指 Offer 51. 数组中的逆序对

AcWing 790. 数的三次方根

见[AcWing算法基础课] Chapter1 基础算法（一）

#include <iostream>
using namespace std;
double n;

int main(){
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if(mid*mid*mid>=n) r=mid;
        else l=mid;
    }
    printf("%lf\n",l);
    return 0;
}

AcWing 795. 前缀和

这道题之前也做过了。代码如下

#include <iostream>
using namespace std;
int n,m;
const int N=100010;
int q[N],s[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&q[i]);
    s[0]=0;
    for(int i=1;i<=n;i++) s[i]=s[i-1]+q[i];
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);
    }
    return 0;
}

AcWing 796. 子矩阵的和

从一维前缀和扩展到二维前缀和。

我们规定i是行，j是列

s i j s_{ij} sij的含义是(i,j)左上角所有数的和。例如 s 34 s_{34} s34就是图中绿色部分的所有数的和。

考虑两个问题：

s i j s_{ij} sij如何计算？
给定以点(x1,y1)为左上角，以点(x2,y2)为左下角的子矩阵，求该子矩阵里面所有数的和该如何计算？

问题2的公式为：s[ x 2 x_2 x2, y 2 y_2 y2]-s[ x 1 − 1 x_{_1-1} x1−1, y 2 y_2 y2]-s[ x 2 x_2 x2, y 1 − 1 y_{_1-1} y1−1]+s[ x 1 − 1 x_{_1-1} x1−1, y 1 − 1 y_{_1-1} y1−1]

问题1如何求 s i j s_{ij} sij的公式为：s[i,j]=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j]

#include <iostream>
using namespace std;
const int N=1010;
int n,m,q;
//a是原数组 s是前缀和数组
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;
}

AcWing 797. 差分

同样的是写过的一道题。

#include <iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];

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

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;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++) a[i]=a[i-1]+b[i];
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

AcWing 798. 差分矩阵

扩展到二维差分。

给定原矩阵a[i,j]，构造差分矩阵b[i,j]，使得a[][]是b[][]的二维前缀和。

我们假定a[][]全是0，那么b[][]也全是0，我们只要在核心操作的基础上把a[][]构建出来就可以了。

核心操作：给以(x1,y1)为左上角，以(x2,y2)为右下角的子矩阵中的所有数（是原数组里的a[i][j]）加上C

对于差分数组的影响：

b[x1][y1]+=c
b[x1][y2+1]-=c
b[x2+1][y1]-=c
b[x2+1][y2+1]+=c

因为a[][]是b[][]的前缀和，二维前缀和是左上角所有数的和，所以b[x1][y1]+=c会将以(x1,y1)为左上角的，右下角的全部数加上C（即下图中所有绿色部分）

所有绿色点的前缀和都是包含(x1,y1)的，所以b[x1][y1]+=c后，所有绿色点也加上了C

我们把a[][]想象成全0，然后把以(i,j)为左上角，以(i,j)为右下角的矩阵加上a[i][j]。

#include <iostream>
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[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++)
            a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+b[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d ",a[i][j]);
    printf("\n");
    }
    return 0;
}

码农公寓