一、基础算法(快排,归并,二分,高精度,前缀和,差分)

一、基础算法

快速排序

题目:给定你一个长度为 n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

数据范围:1≤n≤100000,所有整数均在 1∼10^9 范围内

#include <cstdio>  //数据比较大时,尽量用scanf,printf进行输入输出
#include <iostream>
using namespace std;     //swap函数需要std
const int N = 100010;
int n;
int a[N];
void quick_sort(int a[],int l,int r)
{
    if(l >= r) return;  //数组里只有1个或者没有数时返回
    int x = a[(l + r) / 2],i = l - 1,j = r + 1;  //数据加强,x只能取中间值,不能取两边值,否则超时
    while(i < j)
    {
        do i ++;while(a[i] < x);  //小于x即可,不需要小于等于
        do j --;while(a[j] > x);
        if(i < j) swap(a[i],a[j]);
    }
    quick_sort(a,l,j);   //如果取i的话,x取值需为(l + r + 1) / 2
    quick_sort(a,j + 1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
    quick_sort(a,0,n - 1);
    for(int i = 0;i < n;i ++)printf("%d ",a[i]);
    return 0;
}

题目:给定一个长度为 n的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k个数。

数据范围:1≤n≤100000,所有整数均在 1∼10^9 范围内

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int n,k;
int quick_sort(int l,int r,int k)  //k为第k个小的数
{
    if(l >= r)return a[l]; 
    int x = a[l + r >> 1];
    int i = l - 1;
    int j = r + 1;
    while(i < j)
    {
        while(a[ ++ i] < x);
        while(a[ -- j] > x);
        if(i < j)swap(a[i],a[j]);
    }
    int sl = j - l + 1;  //sl为左半边有多少个数
    if(sl >= k) return quick_sort(l,j,k);   //递归左半边
    else return quick_sort(j + 1,r,k - sl); //递归右半边,k-sl为右半边第k-sl个小的数
}
int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i ++ )scanf("%d",&a[i]);
    cout << quick_sort(0,n -1,k);
    return 0;
}

归并排序

题目:给定你一个长度为 n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

数据范围:1≤n≤100000,所有整数均在 1∼10^9 范围内

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int tmp[N];
int n;

void merge_sort(int a[],int l,int r)
{
    if(l >= r)return;    
    int mid = l + r >> 1;   //取中间值
    merge_sort(a,l,mid);
    merge_sort(a,mid + 1,r); //递归处理左右两边
    int i = l,j = mid + 1;   //指针指向左右两边起始处
    int k = 0 ;     //k为结果数组中已排好序的数量
    while(i <= mid && j <= r)
    {
        if(a[i] < a[j]) tmp[k ++] = a[i ++];
        else tmp[k ++] = a[j ++];
    }
    while(i <= mid) tmp[k ++] = a[i ++];
    while(j <= r) tmp[k ++] = a[j ++];   //如果有数组还剩余数,直接补到结果数组后

    for(int i = l,j = 0;i <= r;i ++ ,j ++)  //l到r为闭区间,将结果数组复制回去
    {
        a[i] = tmp[j];
    }

}
int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ )scanf("%d",&a[i]);
    merge_sort(a,0,n - 1);
    for(int i = 0;i < n;i ++ )printf("%d ",a[i]);
    return 0;
}

题目:给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。

数据范围:1≤n≤100000,所有整数均在 1∼10^9 范围内

#include <iostream>
using namespace std;
const int N = 100010;
int n,k;
int a[N],tmp[N];
typedef long long LL;   //数据超过int存储范围,需用long long
LL merge_sort(int l,int r)
{
    if(l >= r)return 0;
    int mid = l + r >> 1;
    int i = l,j = mid + 1;
    LL res = merge_sort(l,mid) + merge_sort(mid + 1,r); //递归处理左右两边
    k = 0;  //每次递归前k需要清零
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j])tmp[k ++ ] = a[i ++ ];
        else 
        {
            tmp[k ++ ] = a[ j ++ ];
            res += mid - i + 1;    //如果左边的数比右边大,那么左边这个数到中间的数都能形成逆序
        }
    }
    while(i <= mid)tmp[k ++ ] = a[i ++ ];
    while(j <= r)tmp[k ++ ] = a[ j ++ ];
    for(int i = l,j = 0;i <= r;i ++ ,j ++ )
        a[i] = tmp[j];
        return res;
}

int main()
{
    cin >> n ;
    for(int i = 0;i < n;i ++)
        scanf("%d",&a[i]);
    cout << merge_sort(0 ,n - 1);
    return 0;
}

二分

题目:给定一个按照升序排列的长度为 n的整数数组,以及 q个查询。

对于每个查询,返回一个元素 k的起始位置和终止位置(位置从 0开始计数)。

如果数组中不存在该元素,则返回 -1 -1

数据范围:1≤n≤100000,1≤q≤10000,1≤k≤10000

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int n,q;
int main()
{
    cin >> n >> q;
    for(int i = 0;i < n;i ++ )
        scanf("%d",&a[i]);
    while(q --)
    {
        int k;
        scanf("%d",&k);
        int l = 0,r = n - 1;  //有边界不包括n
        
        while(l < r)
        {
            int mid = l + r >> 1;   //每次改变区间后mid需要重新计算,所以mid放入循环中
            if(a[mid] >= k) r = mid; //取等号是因为答案有可能取到边界
            else l = mid + 1;
        }
        if(a[l] != k) cout << "-1 -1" << endl;
        else 
        {
            cout << l << " ";
            int l = 0,r = n - 1;
           
            while(l < r)
            { 
                int mid = l + r + 1 >> 1;
                if(a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

题目:给定一个浮点数 n,求它的三次方根。

数据范围:-10000≤n≤10000,结果保留6位小数。

#include <iostream>    
using namespace std;
int main()
{
    double n;//注意浮点数
    cin >> n;
    double l = -10000,r = 10000;//注意浮点数
    while(r - l > 1e-8)  //注意10的-8次方,注意是大于
    {
        double mid = (l + r) / 2;//注意浮点数
        if(mid * mid * mid >= n)r = mid;
        else l = mid;
    }
    printf("%.6lf",l);
    return 0;
}

高精度

题目:给定两个正整数(不含前导 0),计算它们的和。

数据范围:1≤整数长度≤100000

#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];  //如果B还有数才加,因为有可能B比A更短
        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');  //数据长,用vector存,倒着存
    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 --)cout << C[i];  //由于是倒着存的,所以结果要倒着打
    cout << endl;
    return 0;
}

题目:给定两个正整数(不含前导 0),计算它们的差,计算结果可能为负数。

数据范围:1≤整数长度≤10^5

#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;  //初始借位为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;  //如果减出来为负数,则肯定有借位,所以把借位置为1,否则置为0
        else t = 0;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();   //去掉前导0,如果刚好得0则不去掉这个0
    return C;
}
int main()
{
    string a,b;
    cin >> a >> b;
    vector<int> 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<int> C;
    if(cmp(A,B)) C = sub(A,B);  //比较哪个数更大,如果被减数更小,需要加负号,并计算B-A
    else 
    {
        C = sub(B,A);
        cout << "-";
    }
    
    for(int i = C.size() - 1;i >= 0;i --)
    {
        cout << C[i];
    }
    return 0;
}

题目:给定两个非负整数(不含前导 0) A和 B,请你计算 A×B 的值。

数据范围:1≤A的长度≤100000,0≤B≤10000

#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 ++)  //t为进位,需要等进位全部补入到最后才能结束循环
    {
        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;
    cin >> a >> b;
    vector<int> A;
    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;
}

题目:给定两个非负整数(不含前导 0) A,B,请你计算 A/B 的商和余数。

数据范围:1≤A的长度≤100000,0≤B≤10000,B 一定不为 0

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> dev(vector<int> &A,int b,int &r) //第一个引用的作用是少一遍数组拷贝,效率更高,第二个引用是将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());    //翻转回来后便于去掉前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i = a.size() - 1;i >= 0;i -- )A.push_back(a[i] - '0');
    int r;
    auto C = dev(A,b,r);
    for(int i = C.size() - 1;i >= 0;i --)printf("%d",C[i]);
    cout << endl;
    cout << r;
    return 0;
}

前缀和

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

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

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

数据范围:1≤l≤r≤n,1≤n,m≤100000,−1000≤数列中元素的值≤1000

#include <iostream>
using namespace std;
const int N = 100010;
int a[N],s[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++)s[i] = s[i - 1] + a[i];  //前缀和
    while(m --)
    {
        int l,r;
        cin >> l >> r;
        printf("%d",s[r] - s[l-1]);  
        cout << endl;
    }
    return 0;
}

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

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

数据范围:1≤n,m≤1000,1≤q≤200000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤矩阵内元素的值≤1000

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N],s[N][N];
int main()
{
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i ++)   //下标是从1开始的
    {
        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][j - 1] + s[i - 1][j] -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;
}

差分

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

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

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

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

#include <iostream>
using namespace std;
const int N = 100010;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l] += c;
    b[r + 1] -= c;
}
int main()
{
    int n,m;
    cin >> 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 ++)
    {
        b[i] += b[i - 1] ;
    }
    for(int i = 1;i <= n;i ++)printf("%d ",b[i]);
    return 0;
}

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

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

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

数据范围:1≤n,m≤1000,1≤q≤100000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤c≤1000,−1000≤矩阵内元素的值≤1000

#include <iostream>
using namespace std;
const int N = 1010;
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()
{
    int n,m,q;
    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][j - 1] + b[i - 1][j] -b[i - 1][j - 1] ;
    }
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
            printf("%d ",b[i][j]);
        cout << endl;
    }
    return 0;
}

更多内容请关注我的博客:bgemini.com

热门相关:首席的独宠新娘   仗剑高歌   寂静王冠   明月照大江   寂静王冠