算法进阶之分治

1.

P1177 【模板】排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例 #1

输入 #1

5
4 2 4 5 1

输出 #1

1 2 4 4 5

说明/提示

对于 $20\%$ 的数据，有 $1 \leq N \leq 10^3$；

对于 $100\%$ 的数据，有 $1 \leq N \leq 10^5$，$1 \le a_i \le 10^9$。

解：

#include<iostream>
#include<vector>

using namespace std;

void quick_sort(vector<int>& a, int l, int r){
    if(l>=r) return;

    int p=a[(l+r)/2];
    int i=l-1,j=r+1;

    while(i<j){
        do{i++;}while(a[i]<p);
        do{j--;}while(a[j]>p);

        if(i<j){
            swap(a[i], a[j]);
        }
    }
    quick_sort(a, l, j);
    quick_sort(a, j+1, r);
}

int main(){
    int n;
    cin>>n;
    vector<int> a(n,0);

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

    quick_sort(a, 0, n-1);

    for(int i=0;i<n;i++){
        cout<<a[i];
        if(i!=n-1) cout<<" ";
    }

    return 0;
}

#include<iostream>
#include<vector>

using namespace std;

void merge(vector<int>& a,int l,int m,int r){
    int n1=m-l+1;
    int n2=r-m;
    vector<int> la(n1);
    vector<int> ra(n2);
    for (int i = 0; i < n1; i++) {
        la[i] = a[l + i];
    }
    for (int j = 0; j < n2; j++) {
        ra[j] = a[m + 1 + j];
    }

    int i=0,j=0,k=l;

    while(i<n1&&j<n2){
        if(la[i]<=ra[j]){
            a[k]=la[i];
            i++;
        }
        else{
            a[k]=ra[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        a[k] = la[i];
        i++;
        k++;
    }
    while (j < n2) {
        a[k] = ra[j];
        j++;
        k++;
    }
}

void merge_sort(vector<int>& a,int l,int r){
    if(l<r){
        int m=(l+r)/2;
        merge_sort(a,l,m);
        merge_sort(a,m+1,r);
        merge(a,l,m,r);
    }
} 

int main() {
    int n;
    cin >> n;  
    vector<int> a(n);    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    merge_sort(a, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
        cout << a[i];
        if (i != n - 1) {
            cout << " ";
        }
    }
    cout << endl;
    
    return 0;
}

【评】快排（不稳定）和归并（稳定）排序模板，时间复杂度均为$O(nlog n)$。若要直接调用<algorithm>库函数，则sort(vec.begin(), vec.end(), greater<int>());（降序）。

2.

P1908 逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update：数据已加强。

输入格式

第一行，一个数 $n$，表示序列中有 $n$ 个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

输出序列中逆序对的数目。

输入输出样例 #1

输入 #1

6
5 4 2 6 3 1

输出 #1

11

说明/提示

对于 $25\%$ 的数据，$n \leq 2500$。

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$1 \leq n \leq 5 \times 10^5$。

应该不会有人 $O(n^2)$ 过 50 万吧 —— 2018.8 chen_zhe。

解：

#include<iostream>
#include<vector>

using namespace std;

long long merge(vector<int>& a, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> la(n1);
    vector<int> ra(n2);
    
    for (int i = 0; i < n1; i++) {
        la[i] = a[l + i];
    }
    for (int j = 0; j < n2; j++) {
        ra[j] = a[m + 1 + j];
    }

    int i = 0, j = 0, k = l;
    long long inv_count = 0;  // 用于统计逆序对数量[1,3](@ref)

    while (i < n1 && j < n2) {
        if (la[i] <= ra[j]) {
            a[k] = la[i];
            i++;
        } else {
            a[k] = ra[j];
            j++;
            // 关键修改：当左半部分元素大于右半部分元素时[2,7](@ref)
            // 左半部分当前元素及之后的所有元素都与右半部分当前元素构成逆序对[3,4](@ref)
            inv_count += n1 - i;  // 统计逆序对数量[1,8](@ref)
        }
        k++;
    }

    while (i < n1) {
        a[k] = la[i];
        i++;
        k++;
    }
    while (j < n2) {
        a[k] = ra[j];
        j++;
        k++;
    }
    
    return inv_count;
}

long long merge_sort(vector<int>& a, int l, int r) {
    long long inv_count = 0;
    if (l < r) {
        int m = (l + r) / 2;
        // 递归统计左右子数组的逆序对[5,7](@ref)
        inv_count += merge_sort(a, l, m);
        inv_count += merge_sort(a, m + 1, r);
        // 统计跨越中点的逆序对[3,6](@ref)
        inv_count += merge(a, l, m, r);
    }
    return inv_count;
} 

int main() {
    int n;
    cin >> n;  
    vector<int> a(n);    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    long long inverse_pairs = merge_sort(a, 0, n - 1);
    
    cout << inverse_pairs << endl;
    
    return 0;
}

【评】只需在左右数组合并时额外加一行代码计数即可

3.

P1226 【模板】快速幂

题目描述

给你三个整数 $a,b,p$，求 $a^b \bmod p$。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

输入输出样例 #1

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示

样例解释

$2^{10} = 1024$，$1024 \bmod 9 = 7$。

数据规模与约定

对于 $100\%$ 的数据，保证 $0\le a,b < 2^{31}$，$a+b>0$，$2 \leq p \lt 2^{31}$。

解：

#include <iostream>
using namespace std;

long long fastPow(long long a, long long b, long long p) {
    long long result = 1 % p;  // 初始结果为1，注意对p取模
    a %= p;  // 先对a取模，防止初始值过大
    
    while (b > 0) {
        // 如果b的二进制最低位为1，则将当前a乘入结果
        if (b & 1) {
            result = (result * a) % p;
        }
        // a自乘，相当于指数右移一位
        a = (a * a) % p;
        // b右移一位，相当于除以2
        b >>= 1;
    }
    
    return result;
}

int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    
    long long result = fastPow(a, b, p);
    cout << a << "^" << b << " mod " << p << "=" << result << endl;
    
    return 0;
}