算法板子

库引用

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

标准库

algorithm

__gcd(a, b)                     // 求两个数的最大公因数
__builtin_popcount(a)           // 求 int 的二进制里多少个 1

is_sorted(a, a + n)             // 是否升序
is_sorted_until(a, a + n)       // 到哪里是升序
sort(a, a + n)                  // 不稳定排序(默认升序)
sort(a, a + n, greater<int>())  // 降序排序
stable_sort(a, a + n)           // 稳定排序
nth_element(a, a + k, a + n)    // 将第 k 大元素放到 a[k]
unique(begin, end)              // 对有序数组去重，返回末尾地址

max(a, b)                       // 返回较大值
min(a, b)                       // 返回较小值
max_element(a, a + n)           // 返回最大值位置
min_element(a, a + n)           // 返回最小值位置

lower_bound(a, a + n, key)      // 返回第一个不小于 key 的元素的位置
upper_bound(a, a + n, key)      // 返回第一个大于 key 的元素的位置
binary_search(a, a + n, key)    // 二分查找是否存在

is_heap(a, a + n)               // 判断是否为大顶堆
is_heap_until(a, a + n)         // 到哪里是大顶堆
make_heap(a, a + n)             // 区间建堆
push_heap(a, a + n)             // 末尾元素入堆并调整，与 push_back() 配合
pop_heap(a, a + n)              // 堆顶移到末尾并调整，与 pop_back() 配合
sort_heap(a, a + n)             // 升序堆排序

is_permutation()                // 两个序列是否互为另一个的排序
next_permutation()              // 下一个排序
prev_permutation()              // 上一个排序
 
fill(a, a + n, val)             // 批量赋值
reverse(a, a + n)               // 数组翻转

vector

v.at(k)             // 访问 v[k]
v.front()           // 首元素
v.back()            // 末元素
v.begin()           // 首地址(迭代器)
v.end()             // 末地址(迭代器)
v.empty()           // 是否空
v.size()            // 大小
v.max_size()        // 最大空间
v.clear()           // 清除
v.insert(pos, item) // 在 pos(迭代器) 位置插入 item
v.eraze(pos)        // 擦除 pos(迭代器) 位置的元素
v.push_back(item)   // 末尾插入
v.pop_back()        // 末尾删除

queue

/*----- queue -----*/
q.front()        // 访问队头
q.back()         // 访问队尾
q.empty()        // 是否空
q.size()         // 大小
q.push(item)     // item 入队
q.emplace(item)  // item 替换队尾
q.pop()          // 出队
/*----- priority_queue -----*/
priority_queue<int, vector<int>, greater<int>> pq
pq.top()         // 访问队首
pq.empty()       // 优先队列是否空
pq.size()        // 大小
pq.push(item)    // 插入 item
pq.pop()         // 出队

stack

s.top()          // 访问栈顶
s.empty()        // 栈是否空
s.size()         // 大小
s.push(item)     // item 入栈
s.emplace(item)  // item 替换栈顶
s.pop()          // 出栈

set

/*----- set -----*/
s.size()          // 大小
s.empty()         // 是否空
s.clear()         // 清除
s.insert(key)     // 插入
s.erase(pos/key)  // 删除
s.count(key)      // 是否存在
s.find(key)       // 查找，成功返回位置，失败返回 s.end()
/*----- multiset -----*/
ms.size()         // 大小
ms.empty()        // 是否空
ms.clear()        // 清除
ms.insert(key)    // 插入
ms.erase(pos/key) // 删除
ms.count(key)     // 计数
ms.find(key)      // 查找，成功返回位置，失败返回 s.end()

分治

逆序对计数

//这段代码通过归并排序的分治思想计算数组中的逆序对数量。逆序对的定义是：数组中满足 i < j 且 a[i] > a[j] 的数对。
#include <iostream>
using namespace std;
typedef long long ll;  // 逆序对数量可能极大（如2e5元素最多2e10对），必须用long long避免溢出

int temp[200005];  // 归并排序的临时数组，全局定义避免递归中频繁创建

/**
 * @brief 递归计算逆序对数量，同时对数组进行归并排序
 * @param a 待处理的数组
 * @param left 当前处理区间的左边界
 * @param right 当前处理区间的右边界
 * @return 当前区间内的逆序对总数（左区间+右区间+跨区间）
 */
ll solve(int a[], int left, int right) {
    // 递归终止条件：区间只有一个元素，无逆序对
    if (left == right)
        return 0;
    else {
        // 分治：将区间拆分为左右两部分
        int mid = (right - left) / 2 + left;  // 计算中点（避免 (left+right)/2 溢出）
        ll s1 = solve(a, left, mid);         // 左区间[left, mid]的逆序对数量
        ll s2 = solve(a, mid + 1, right);    // 右区间[mid+1, right]的逆序对数量
        ll s3 = 0;                           // 跨左右区间的逆序对数量（核心统计部分）

        // 合并两个有序子数组，并统计跨区间逆序对
        int i = left;    // 左区间的指针（初始指向左区间起点）
        int j = mid + 1; // 右区间的指针（初始指向右区间起点）
        int k = 0;       // 临时数组temp的偏移量（相对于left）

        // 同时遍历左右两个有序子数组，合并并统计逆序对
        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                // 左区间元素更小，无逆序对，直接放入临时数组
                temp[left + k] = a[i];
                k++;
                i++;
            } else {
                // 右区间元素更小，左区间[i, mid]的所有元素都比a[j]大，新增(mid-i+1)个逆序对
                temp[left + k] = a[j];
                s3 += (mid - i + 1);  // 统计跨区间逆序对
                k++;
                j++;
            }
        }

        // 处理左区间剩余元素（右区间已遍历完）
        if (i <= mid) {
            while (i <= mid) {
                temp[left + k] = a[i];
                k++;
                i++;
            }
        }
        // 处理右区间剩余元素
        else {
            while (j <= right) {
                temp[left + k] = a[j];
                k++;
                j++;
            }
        }

        // 将临时数组中排好序的部分复制回原数组
        for (int l = left; l <= right; l++) {
            a[l] = temp[l];
        }

        // 返回总逆序对数量：左区间 + 右区间 + 跨区间
        return s1 + s2 + s3;
    }
}

int main() {
    int n;          // 数组长度
    int a[200005] = {};  // 存储输入的数组，初始化为0
    cin >> n;       // 输入数组长度
    for (int i = 0; i < n; i++) {
        cin >> a[i];  // 输入数组元素
    }
    // 计算并输出逆序对总数
    cout << solve(a, 0, n - 1);
    return 0;
}

多数问题

#include <stdio.h>  
const int N = 2000000;    // 定义数组的最大长度上限
int a[N];                 // 全局数组：存储输入的待检测数组

/**
 * @brief 分治法求解数组区间的多数元素问题
 * @param a 待检测的数组
 * @param start 当前处理区间的左边界下标
 * @param end 当前处理区间的右边界下标
 * @param result 输出型参数：若存在多数元素，存储其值；否则无有效值
 * @return 布尔值（int型）：1表示当前区间存在多数元素，0表示不存在
 */
int majorityDC(int a[], int start, int end, int *result) {
    // 递归终止条件：区间只有一个元素（start == end），该元素即为当前区间的候选多数元素
    if (start == end) {  
        *result = a[end];  // 唯一元素作为候选
        return 1;          // 单个元素的区间，该元素自然是多数（出现次数=1 > 0.5）
    } else {  
        int m1, m2;        // m1：左子区间候选多数元素；m2：右子区间候选多数元素
        
        // 递归处理左子区间 [start, mid]，获取候选多数元素m1
        int mid = (start + end) / 2;
        majorityDC(a, start, mid, &m1);    
        // 递归处理右子区间 [mid+1, end]，获取候选多数元素m2
        majorityDC(a, mid + 1, end, &m2);   
        
        // 统计m1、m2在当前区间 [start, end] 的出现次数
        int count1 = 0, count2 = 0;  
        for (int i = start; i <= end; i++) {  
            if (a[i] == m1) {   // 统计m1的出现次数
                count1++;  
            }  
            if (a[i] == m2) {   // 统计m2的出现次数
                count2++;  
            }  
        }  
        
        // 判断m1是否为当前区间的多数元素（出现次数 > 区间长度的一半）
        if (count1 > ((end - start + 1) / 2)) {  
            *result = m1;      // 记录多数元素值
            return 1;          // 存在多数元素，返回1
        } 
        // 判断m2是否为当前区间的多数元素
        else if (count2 > ((end - start + 1) / 2)) {  
            *result = m2;      // 记录多数元素值
            return 1;          // 存在多数元素，返回1
        } 
        // 两个候选元素都不是多数，当前区间无多数元素
        else {  
            return 0;  
        }  
    }  
}  

int main() {  
    int n, resultDC;  // n：数组长度；resultDC：存储最终的多数元素（若存在）
    scanf("%d", &n);  // 输入数组长度
    
    // 输入数组的n个元素（注意：scanf("%d\n", &a[i])中\n会吸收换行符，不影响输入）
    for(int i = 0; i < n; i++) {  
        scanf("%d\n", &a[i]);  
    }  
    
    // 调用分治函数，判断是否存在多数元素
    if (majorityDC(a, 0, n - 1, &resultDC)) {  
        printf("%d", resultDC);  // 存在
    } else {  
        printf("Can not find the majority!");  // 不存在
    }  
    
    return 0;  
}

动态规划

01背包问题

//01 背包的核心特征是：每个物品仅有 “选” 或 “不选” 两种选择，求解在给定背包容量限制下，能装入物品的最大价值。
#include <iostream>
#include <algorithm>  // 包含max函数

#define ll long long   
#define MAX_NUM 1005   // 物品数量的最大上限
#define MAX_CAP 100005 // 背包容量的最大上限
using namespace std;

ll dp[MAX_CAP];  // dp[j]表示容量为j的背包能装的最大价值
int v[MAX_NUM];  // 存储每个物品的价值
int w[MAX_NUM];  // 存储每个物品的重量

/**
 * @brief 求解01背包问题的最大价值
 * @param Bag 一维动态规划数组（dp）
 * @param value 物品价值数组（v）
 * @param weight 物品重量数组（w）
 * @param num 物品总数（n）
 * @param cap 背包最大容量（k）
 * @return 背包能装的最大价值
 */
ll backBag(ll Bag[], int *value, int *weight, int num, int cap) {
    // 初始化dp数组：所有容量的背包初始价值为0
    for(int i = 0; i <= cap; i++)
        Bag[i] = 0;
    
    // 遍历每个物品
    for (int i = 1; i <= num; i++) {
        // 倒序遍历背包容量：从最大容量cap到当前物品重量weight[i]
        // 倒序的目的：避免同一物品被重复选择
        for (int j = cap; j >= weight[i]; j--) {
            // 状态转移方程：
            // 选第i个物品：Bag[j - weight[i]] + value[i]
            // 不选第i个物品：Bag[j]（保持原有价值）
            // 取两者的最大值作为容量j的新最大价值
            Bag[j] = max(Bag[j - weight[i]] + value[i], Bag[j]);
        }
    }
    // 返回容量为cap的背包能装的最大价值
    return Bag[cap];
}

int main() {
    int n, k;  // n：物品数量，k：背包最大容量
    cin >> n >> k;  // 输入物品数量和背包容量
    
    // 输入每个物品的价值和重量
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    
    // 调用01背包函数，输出最大价值
    cout << backBag(dp, v, w, n, k);
    return 0;
}

完全背包问题

//完全背包的核心特征是：每个物品可以无限次选取，求解在给定背包容量限制下，能装入物品的最大价值。
#include <iostream>
#include <algorithm>  // 包含max函数

#define ll long long    
#define MAX_NUM 10005   // 物品数量的最大上限
#define MAX_CAP 10000005// 背包容量的最大上限
using namespace std;

ll dp[MAX_CAP];  // dp[j]表示容量为j的背包能装的最大价值
int v[MAX_NUM];  // 存储每个物品的价值
int w[MAX_NUM];  // 存储每个物品的重量

/**
 * @brief 求解完全背包问题的最大价值
 * @param Bag 一维动态规划数组（dp）
 * @param value 物品价值数组（v）
 * @param weight 物品重量数组（w）
 * @param num 物品总数（n）
 * @param cap 背包最大容量（k）
 * @return 背包能装的最大价值
 */
ll backBag(ll Bag[], int *value, int *weight, int num, int cap) {
    // 初始化dp数组
    for(int i = 0; i <= cap; i++)
        Bag[i] = 0;
    
    // 遍历每个物品
    for (int i = 1; i <= num; i++) {
        // 正序遍历背包容量
        //允许同一物品被重复选择
        for (int j = weight[i]; j <= cap; j++) {
            // 状态转移方程：
            // 选第i个物品（可重复选）：Bag[j - weight[i]] + value[i]
            // 不选第i个物品：Bag[j]（保持原有价值）
            // 取两者的最大值作为容量j的新最大价值
            Bag[j] = max(Bag[j - weight[i]] + value[i], Bag[j]);
        }
    }
    // 返回容量为cap的背包能装的最大价值
    return Bag[cap];
}

int main() {
    int n, k;  // n：物品数量，k：背包最大容量
    cin >> k >> n;  // 输入背包容量k，再输入物品数量n
    
    // 输入每个物品的重量和价值
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    
    // 调用完全背包函数，输出最大价值
    cout << backBag(dp, v, w, n, k);
    return 0;
}

分组背包

//分组背包的核心规则是：物品被划分为若干组，每组中最多选择一个物品（选本组某一个物品 或 不选本组任何物品），求解在给定背包容量限制下，能装入物品的最大价值。
#include <iostream>
#include <algorithm>  // 包含max函数

typedef long long ll; 

const int MAX = 1005; // 最大组数/每组最大物品数/最大背包容量的上限

// 分组背包的组结构体：存储每组的物品信息
struct {
    int cnt;        // 该组的物品数量
    ll ID[MAX];     // 该组中每个物品的编号（关联到weight/val数组）
} group[MAX];       // group[k]表示第k组的信息（组号从0开始，根据输入的k动态分配）

ll dp[MAX];         // dp[j]表示容量为j的背包能装的最大价值
ll val[MAX];        // val[i]表示第i个物品的价值
ll weight[MAX];     // weight[i]表示第i个物品的重量

/**
 * @brief 求解分组背包问题的最大价值
 * @param cap 背包最大容量
 * @param max_group 所有物品所属组的最大组号（遍历到该组即可覆盖所有组）
 * @return 背包能装的最大价值
 */
ll group_bag(int cap, int max_group);

using namespace std;

int main() {
    int n, m;       // n：物品总数，m：背包最大容量（注意输入顺序是先m后n）
    cin >> m >> n;  // 输入背包容量m，再输入物品数量n
    
    int a, b, k, max_group = 0; // a：物品重量，b：物品价值，k：物品所属组号；max_group记录最大组号
    for (int i = 1; i <= n; i++) { // n个物品输入
        cin >> a >> b >> k;        // 输入第i个物品的重量a、价值b、所属组k
        weight[i] = a;             // 记录第i个物品的重量
        val[i] = b;                // 记录第i个物品的价值
        group[k].ID[group[k].cnt++] = i; // 将物品i加入第k组的ID列表，组内物品数cnt+1
        max_group = max(max_group, k);   // 更新最大组号
    }
    
    // 调用分组背包函数，输出最大价值
    cout << group_bag(m, max_group);
    return 0;
}

ll group_bag(int cap, int max_group) {
    // 分组背包核心三层循环：
    // 第一层：遍历每一组（从0到最大组号max_group）
    for (int i = 0; i <= max_group; i++) {
        // 第二层：倒序遍历背包容量（从cap到0）—— 类似01背包，避免同一组选多个物品
        for (ll j = cap; j >= 0; j--) {
            // 第三层：遍历当前组内的所有物品
            for (int k = 0; k < group[i].cnt; k++) {
                // 获取当前组内第k个物品的编号
                ll item_id = group[i].ID[k];
                // 若当前容量j >= 该物品重量，则尝试选择该物品
                if (j >= weight[item_id]) {
                    // 状态转移方程：
                    // 选该组的这个物品：dp[j - weight[item_id]] + val[item_id]
                    // 不选该组的这个物品：dp[j]
                    // 取最大值作为容量j的新最大价值
                    dp[j] = max(dp[j], dp[j - weight[item_id]] + val[item_id]);
                }
            }
        }
    }
    // 返回容量为cap的背包能装的最大价值
    return dp[cap];
}

最大子列和

//“最大子数组和” 指：在一个整数数组中，找出一段连续的子数组（元素在原数组中连续排列，不能为空），使得该子数组的元素累加和最大，返回这个最大值。

#include <iostream>
#include <algorithm>  // 包含max函数

#define MAX 1000005   // 定义数组的最大长度上限
#define ll long long  
using namespace std;

int a[MAX];  // 全局数组，存储输入的待处理数组

/**
 * @brief 采用Kadane算法（逆序遍历版）求解数组的最大子数组和
 *        核心逻辑：维护当前子数组的和sum，若sum≤0则重置为当前元素（重新开始累加），否则累加当前元素；
 *        同时维护遍历过程中出现的最大子数组和Max。
 * @param array 待处理的数组指针
 * @param n 数组的长度
 * @return 数组的最大子数组和（子数组为连续元素组成的数组）
 */
ll maxSubArray(int *array, int n) {
    // 初始化最大子数组和为极小值
    ll Max = -0x3f3f3f3f3f3f3f3f;
    ll sum = 0;  // 维护当前子数组的累加和
    
    // 逆序遍历数组
    for (int i = n - 1; i >= 0; i--) {
        // 核心判断：若当前累加和sum≤0，说明继续累加前序元素会拉低当前值，重置sum为当前元素（重新开始一个子数组）
        if (sum <= 0)
            sum = array[i];
        // 若sum>0，说明累加当前元素能增大子数组和，继续累加
        else
            sum += array[i];
        
        // 更新最大子数组和：取当前sum和历史最大值Max中的较大值
        Max = max(sum, Max);
    }
    // 返回最终的最大子数组和
    return Max;
}

int main() {
    int n;  // 存储数组的长度
    cin >> n;  // 输入数组长度
    
    // 输入数组的n个元素，存入全局数组a中（下标从0开始）
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    // 调用maxSubArray函数计算最大子数组和，并输出结果
    cout << maxSubArray(a, n);
    return 0;
}

最长公共子序列

#include <iostream>
#include <string>
#define MAX 1005  // 定义字符串最大长度上限
using namespace std;

// 回溯路径结构体：记录当前位置(i,j)的LCS状态来自哪个前驱位置(x,y)
struct Tab {
    int x, y;  // x对应字符串sa的前x个字符，y对应字符串sb的前y个字符
} trac[MAX][MAX];  // trac[i][j]：记录计算lcs[i][j]时的前驱位置，用于回溯打印LCS

int lcs[MAX][MAX]; // 动态规划数组：lcs[i][j]表示sa前i个字符和sb前j个字符的LCS长度

/**
 * @brief 递归回溯打印LCS的具体字符序列
 * @param str 参考字符串
 * @param i 当前回溯到sa的前i个字符位置
 * @param j 当前回溯到sb的前j个字符位置
 */
void print_lcs(string str, int i, int j);

int main() {
    int k;          // 输出模式控制：k=0输出长度，k≠0输出LCS序列
    cin >> k;       // 输入模式控制参数
    string sa, sb;  // 待求解LCS的两个字符串
    cin >> sa >> sb;
    
    int la = (int)sa.length();  // 字符串sa的长度
    int lb = (int)sb.length();  // 字符串sb的长度
    
    // 动态规划求解LCS长度，并记录回溯路径
    // i遍历sa的前i个字符（i从1到la，对应sa[i-1]）
    for (int i = 1; i <= la; i++) {
        // j遍历sb的前j个字符（j从1到lb，对应sb[j-1]）
        for (int j = 1; j <= lb; j++) {
            // 情况1：sa的第i个字符（sa[i-1]）和sb的第j个字符（sb[j-1]）相等
            if (sa[i - 1] == sb[j - 1]) {
                // LCS长度 = 前i-1和j-1个字符的LCS长度 + 1（当前字符加入LCS）
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
                // 记录路径：当前状态来自(i-1,j-1)（因为当前字符匹配）
                trac[i][j] = {i - 1, j - 1};
            }
            // 情况2：字符不相等，取“sa前i-1个 & sb前j个”的LCS长度
            else if (lcs[i - 1][j] >= lcs[i][j - 1]) {
                lcs[i][j] = lcs[i - 1][j];
                // 记录路径：当前状态来自(i-1,j)
                trac[i][j] = {i - 1, j};
            }
            // 情况3：字符不相等，取“sa前i个 & sb前j-1个”的LCS长度
            else {
                lcs[i][j] = lcs[i][j - 1];
                // 记录路径：当前状态来自(i,j-1)
                trac[i][j] = {i, j - 1};
            }
        }
    }
    
    // 根据k的值选择输出模式
    if (k == 0)
        cout << lcs[la][lb];  // 输出LCS的长度
    else
        print_lcs(sa, la, lb); // 输出LCS的具体字符序列
    
    return 0;
}

void print_lcs(string str, int i, int j) {
    // 递归终止条件：回溯到字符串开头（i=0或j=0），无字符可输出
    if (i == 0 || j == 0)
        return;
    
    // 情况1：当前路径来自(i-1,j-1) → 说明sa[i-1]是LCS的字符，先递归再输出（保证顺序）
    if (trac[i][j].x == i - 1 && trac[i][j].y == j - 1) {
        print_lcs(str, i - 1, j - 1);  // 先回溯前驱位置
        cout << str[i - 1];            // 输出当前匹配的字符
    }
    // 情况2：当前路径来自(i-1,j) → 继续回溯该方向
    else if (trac[i][j].x == i - 1 && trac[i][j].y == j) {
        print_lcs(str, i - 1, j);
    }
    // 情况3：当前路径来自(i,j-1) → 继续回溯该方向
    else {
        print_lcs(str, i, j - 1);
    }
}

最小编辑距离

#include <iostream>
#include <string>
#define MAX 2005  // 定义字符串最大长度上限（适配输入的字符串长度）
using namespace std;

/**
 * @brief 辅助函数：返回三个整数中的最小值
 * @param a 第一个整数
 * @param b 第二个整数
 * @param c 第三个整数
 * @return a、b、c中的最小值
 */
int min3(int a, int b, int c) {
    int m = a;       // 初始化最小值为a
    if (b < m)       // 比较b和当前最小值，更新
        m = b;
    if (c < m)       // 比较c和当前最小值，更新
        return c;
    return m;        // 返回最终最小值
}

/**
 * @brief 计算两个字符串的编辑距离（最少操作数：插入/删除/替换）
 * @param word1 源字符串（需要转换的字符串）
 * @param word2 目标字符串（转换后的字符串）
 * @return 将word1转为word2的最少操作次数
 */
int minDistance(string word1, string word2) {
    // 空间优化：用两行dp数组（dp[0]表示上一行，dp[1]表示当前行），替代传统的l1×l2二维数组
    int dp[2][MAX] = {};  // 初始化为0
    int l1 = word1.length();  // 源字符串word1的长度
    int l2 = word2.length();  // 目标字符串word2的长度

    // 初始化dp[0]行（对应word1为空字符串时，转换为word2前j个字符需要j次插入操作）
    for (int j = 0; j <= l2; j++)
        dp[0][j] = j;

    // 遍历word1的每个字符（i表示处理到word1的前i个字符）
    for (int i = 1; i <= l1; i++) {
        // 初始化当前行dp[1]的第0列：word2为空时，删除word1前i个字符需要i次操作
        dp[1][0] = i;

        // 遍历word2的每个字符（j表示处理到word2的前j个字符）
        for (int j = 1; j <= l2; j++) {
            // 情况1：word1的第i个字符（word1[i-1]）和word2的第j个字符（word2[j-1]）相等
            // 无需任何操作，操作数等于“处理到word1前i-1、word2前j-1个字符”的操作数
            if (word1[i - 1] == word2[j - 1])
                dp[1][j] = dp[0][j - 1];
            // 情况2：字符不相等，取“替换、删除、插入”三种操作的最小操作数 + 1
            else
                // dp[0][j-1]+1：替换（把word1[i-1]换成word2[j-1]，操作数+1）
                // dp[0][j]+1：删除（删掉word1[i-1]，操作数+1）
                // dp[1][j-1]+1：插入（在word1后插入word2[j-1]，操作数+1）
                dp[1][j] = min3(dp[0][j - 1], dp[0][j], dp[1][j - 1]) + 1;
        }

        // 将当前行（dp[1]）的数据复制到上一行（dp[0]），为下一轮遍历做准备（滚动更新）
        for (int j = 0; j <= l2; j++)
            dp[0][j] = dp[1][j];
    }

    // dp[0][l2]即为处理完word1全部字符、word2全部字符的最少操作数
    return dp[0][l2];
}

int main() {
    string a;  // 源字符串（对应word1）
    string b;  // 目标字符串（对应word2）
    cin >> a >> b;  // 输入两个待计算编辑距离的字符串
    cout << minDistance(a, b);  // 计算并输出编辑距离
    return 0;
}

最长单调子序列

#include <vector>   
#include <algorithm> // 包含lower_bound/upper_bound二分查找函数
using namespace std; // 适配原代码的命名空间

/**
 * @brief 求解数组的最长严格单调递增子序列（LSRSA）的长度
 *        严格递增定义：子序列中任意相邻元素满足 a[i] < a[i+1]
 * @param a 输入的待处理数组（const引用避免拷贝，提高效率）
 * @return 最长严格单调递增子序列的长度
 */
int lsrsa(const vector<int> &a) {
    vector<int> sa; // 核心贪心数组：sa[i]表示长度为i+1的严格递增子序列的最小末尾元素
    // 遍历原数组的每个元素
    for (auto x : a) {
        // 情况1：当前元素x大于sa的最后一个元素 → 可接在sa后，形成更长的严格递增子序列
        if (sa.empty() || x > sa.back()) {
            sa.push_back(x);
        }
        // 情况2：当前元素x不大于sa的最后一个元素 → 用二分查找找到sa中第一个≥x的位置，替换为x
        // 目的：保持sa的严格递增性，且让该长度的子序列末尾元素尽可能小，利于后续接更长的序列
        else {
            // lower_bound：在有序区间[sa.begin(), sa.end())中找第一个≥x的元素的迭代器
            *lower_bound(sa.begin(), sa.end(), x) = x;
        }
    }
    // sa的长度即为最长严格单调递增子序列的长度（sa本身不是子序列，仅长度等价）
    return (int)sa.size();
}

/**
 * @brief 求解数组的最长单调不减子序列（LRSA）的长度
 *        单调不减定义：子序列中任意相邻元素满足 a[i] ≤ a[i+1]
 * @param a 输入的待处理数组（const引用避免拷贝，提高效率）
 * @return 最长单调不减子序列的长度
 */
int lrsa(const vector<int> &a) {
    vector<int> sa; // 核心贪心数组：sa[i]表示长度为i+1的单调不减子序列的最小末尾元素
    // 遍历原数组的每个元素
    for (auto x : a) {
        // 情况1：当前元素x≥sa的最后一个元素 → 可接在sa后，形成更长的单调不减子序列
        if (sa.empty() || x >= sa.back()) {
            sa.push_back(x);
        }
        // 情况2：当前元素x < sa的最后一个元素 → 用二分查找找到sa中第一个>x的位置，替换为x
        // 目的：保持sa的单调不减性，且让该长度的子序列末尾元素尽可能小，利于后续接更长的序列
        else {
            // upper_bound：在有序区间[sa.begin(), sa.end())中找第一个>x的元素的迭代器
            *upper_bound(sa.begin(), sa.end(), x) = x;
        }
    }
    // sa的长度即为最长单调不减子序列的长度（sa本身不是子序列，仅长度等价）
    return (int)sa.size();
}

钢管切割问题

#include <bits/stdc++.h>  
using namespace std;  

#define MAX 100          // 定义钢条最大长度上限（适配n≤100的场景）
#define MIN_VALUE (-1)   // 初始化最大收益的极小值（收益非负，用-1表示初始无效值）

int s[MAX];  // s[j]：长度为j的钢条的最优切割中，「第一段」的长度（用于回溯切割方案）
int r[MAX];  // r[j]：长度为j的钢条能获得的最大收益

/**
 * @brief 自底向上的动态规划求解钢条切割的最大收益，并记录切割方案
 * @param p 价格表数组：p[i]表示长度为i的钢条的售价（p[0]=0，无实际意义）
 * @param n 需要切割的钢条总长度
 */
void EXTENDED_BOTTOM_UP_CUT_ROD(int *p, int n) {
    r[0] = 0;  // 初始化
    
    // 遍历所有长度j（从1到n），计算每个长度的最大收益r[j]
    for (int j = 1; j <= n; j++) {
        int q = MIN_VALUE;  // 初始化当前长度j的最大收益为极小值
        
        // 尝试切割第一段为i（i从1到j），剩余长度为j-i，计算总收益p[i]+r[j-i]
        for (int i = 1; i <= j; i++) {
            // 若当前切割方案的收益更大，更新最大收益q，并记录最优的第一段长度s[j]
            if (q < p[i] + r[j - i]) {
                q = p[i] + r[j - i];  // 更新最大收益
                s[j] = i;             // 记录长度j的最优切割的第一段长度
            }
        }
        
        r[j] = q;  // 保存长度为j的钢条的最大收益
    }
}

/**
 * @brief 输出钢条切割的最大收益和具体切割方案
 * @param p 价格表数组（同EXTENDED_BOTTOM_UP_CUT_ROD）
 * @param n 需要切割的钢条总长度
 */
void PRINT_CUT_ROD_SOLUTION(int *p, int n) {
    // 先调用动态规划函数，计算最大收益r[n]和切割方案s[1..n]
    EXTENDED_BOTTOM_UP_CUT_ROD(p, n);
    
    // 输出长度为n的钢条的最大收益
    printf("%d\n", r[n]);
    
    // 回溯切割方案：从总长度n开始，逐步拆分每一段的长度
    while (n > 0) {
        printf("%d ", s[n]);  // 输出当前最优切割的第一段长度
        n -= s[n];            // 剩余长度 = 总长度 - 已切割的第一段长度，继续回溯
    }
}

int main() {
    // 价格表p：p[0]=0，p[1]=1（长度1售价1），p[2]=5（长度2售价5）...p[10]=30（长度10售价30）
    // 注意：p[11]~p[14]未显式赋值，默认值为0（长度11-14的钢条无定价，售价为0）
    int p[15] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    
    // 求解长度为14的钢条的最大收益和切割方案
    PRINT_CUT_ROD_SOLUTION(p, 14);
    
    return 0;
}

矩阵链乘法

#include <bits/stdc++.h>  
using namespace std;  

/*  
* 核心数组说明：
* p: 矩阵规模数组，矩阵 A_i 的规模为 p[i-1] * p[i]（i从1到n）
* s: 分割点数组，s[i][j]表示矩阵链 A_i~A_j 最优括号化的分割点k（即拆分为 A_i~A_k 和 A_k+1~A_j）
* m: 最小乘法次数数组，m[i][j]表示矩阵链 A_i~A_j 相乘所需的最少标量乘法次数
*/
#define MAX 100                  // 矩阵链最大长度上限
long long p[MAX];                // 存储矩阵规模的数组（长度n+1）
long long m[MAX][MAX];           // 存储最小标量乘法次数的二维数组
long long s[MAX][MAX];           // 存储最优分割点的二维数组

/**
 * @brief 自底向上动态规划求解矩阵链乘法的最小标量乘法次数，并记录最优分割点
 * @param n 矩阵链中矩阵的个数（A₁~Aₙ）
 */
void MATRIX_CHAIN_ORDER(int n) {  
    // 初始化：单个矩阵（i=j）无需乘法，标量乘法次数为0
    for(int i = 1; i <= n; i++) {  
        m[i][i] = 0;  
    }  
    
    // l表示矩阵链的长度（从2开始，因为长度1已初始化），遍历所有可能的链长度
    for(int l = 2; l <= n; l++) {    
        // i表示矩阵链的起始矩阵下标（A_i），确保结束下标j=i+l-1 ≤n
        for(int i = 1; i <= n - l + 1; i++) {    
            int j = i + l - 1;              // 矩阵链的结束矩阵下标（A_j）
            m[i][j] = 9223372036854775807;  // 初始化最小次数为long long的最大值（表示无穷大）
            
            // k遍历所有可能的分割点（将A_i~A_j拆分为A_i~A_k 和 A_k+1~A_j）
            for(int k = i; k <= j - 1; k++) {  
                // 计算当前分割点k对应的标量乘法总次数：
                // m[i][k]（A_i~A_k的最小次数） + m[k+1][j]（A_k+1~A_j的最小次数） + p[i-1]*p[k]*p[j]（两个子链相乘的次数）
                long long q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];  
                
                // 若当前分割点的总次数更小，更新最小次数和最优分割点
                if(q < m[i][j]) {  
                    m[i][j] = q;  
                    s[i][j] = k;  
                }  
            }  
        }  
    }  
}  

/**
 * @brief 递归回溯输出矩阵链 A_i~A_j 的最优括号化方案
 * @param i 矩阵链的起始下标
 * @param j 矩阵链的结束下标
 */
void PRINT_OPTIMAL_PARENS(long long i, long long j) {  
    // 递归终止条件：单个矩阵，直接输出"A"（结合下标区分，实际应为A_i，简化为A）
    if(i == j) {  
        printf("A");  
    } else {  
        printf("(");                          // 左括号
        PRINT_OPTIMAL_PARENS(i, s[i][j]);     // 递归输出左子链 A_i~A_s[i][j] 的最优括号化
        PRINT_OPTIMAL_PARENS(s[i][j]+1, j);   // 递归输出右子链 A_s[i][j]+1~A_j 的最优括号化
        printf(")");                          // 右括号
    }  
}  

int main() {  
    int n;                                    // 矩阵链中矩阵的个数
    scanf("%d", &n);                          // 输入矩阵个数n
    
    // 输入矩阵规模数组p：p[0]~p[n]，共n+1个值（A_i的规模为p[i-1]×p[i]）
    for(int i = 0; i <= n; i++) {  
        scanf("%lld", &p[i]);  
    }  
    
    // 计算最小标量乘法次数和最优分割点
    MATRIX_CHAIN_ORDER(n);  
    
    // 输出A₁~Aₙ相乘的最少标量乘法次数
    printf("%lld\n", m[1][n]);   
    // 输出A₁~Aₙ的最优括号化方案
    PRINT_OPTIMAL_PARENS(1, n);   
    return 0;  
}

排序

归并排序

#include <stdio.h>    // 标准输入输出头文件（printf/scanf）
#include <ctype.h>    // 字符处理头文件
#include <string.h>   // 字符串处理头文件
#include <math.h>     // 数学函数头文件
#include <stdlib.h>   // 标准库头文件
#define MAX 1000      // 定义数组最大长度上限

int temp[MAX];        // 归并排序的临时数组：存储合并过程中的有序元素
// 待排序数组：初始值为{50, 10, 20, 30, 70, 40, 80, 60}，长度为8
int ans[MAX] = {50, 10, 20, 30, 70, 40, 80, 60};  

/**
 * @brief 归并排序的递归分治函数：将数组[startId, endId]拆分为左右子数组，分别排序后合并
 * @param startId 当前待排序区间的左边界下标
 * @param endId 当前待排序区间的右边界下标
 */
void Mergesort(int startId, int endId);  

/**
 * @brief 归并排序的合并函数：将两个有序子数组[startId, midId]和[midId+1, endId]合并为一个有序数组
 * @param startId 左子数组的左边界下标
 * @param midId 左子数组的右边界下标（也是分割点）
 * @param endId 右子数组的右边界下标
 */
void Merge(int startId, int midId, int endId);  

int main() {  
    // 对ans数组的[0,7]区间进行归并排序（数组长度为8，下标0~7）
    Mergesort(0, 7);  

    // 遍历输出排序后的数组元素
    for(int i=0; i<8; i++)  
        printf("%d ", ans[i]);  

    return 0;
}  

void Mergesort(int startId, int endId) {  
    // 计算当前区间的中点（避免(startId+endId)/2溢出，等价写法）
    int midId = startId + (endId - startId)/2;  

    // 递归终止条件：当startId >= endId时，区间只有一个元素（或空），无需排序
    if(startId < endId) {  
        Mergesort(startId, midId);       // 递归排序左子区间[startId, midId]
        Mergesort(midId+1, endId);       // 递归排序右子区间[midId+1, endId]
        Merge(startId, midId, endId);    // 合并两个已排序的子区间
    }  
}  

void Merge(int startId, int midId, int endId) {  
    // 初始化指针：
    // i：左子数组[startId, midId]的遍历指针
    // j：右子数组[midId+1, endId]的遍历指针
    // k：临时数组temp的存储指针
    int i = startId, j = midId + 1, k = startId;  

    // 同时遍历左右两个有序子数组，按升序将元素存入temp
    while(i <= midId && j <= endId) {  
        if(ans[i] < ans[j]) {            // 左子数组元素更小，存入temp
            temp[k] = ans[i];  
            k++; i++;                    // 移动temp指针和左子数组指针
        } else {                         // 右子数组元素更小，存入temp
            temp[k] = ans[j];  
            k++; j++;                    // 移动temp指针和右子数组指针
        }  
    }  

    // 处理左子数组的剩余元素
    while(i <= midId) {  
        temp[k] = ans[i];  
        k++; i++;  
    }  

    // 处理右子数组的剩余元素
    while(j <= endId) {  
        temp[k] = ans[j];  
        k++; j++;  
    }  

    // 将临时数组temp中排序好的元素复制回原数组ans（覆盖当前区间）
    for(i = startId; i <= endId; i++) {  
        ans[i] = temp[i];  
    }  
}

插入排序

/**
 * @brief 直接插入排序（升序）：将数组分为已排序/未排序区间，逐个插入未排序元素到已排序区间的正确位置
 * @param k 待排序的数组（支持任意可比较的keytype类型，如int）
 * @param n 数组的长度（元素个数）
 */
void insertSort(keytype k[], int n) {  
    keytype temp;  // 临时变量：存储当前待插入的元素
    
    // 外层循环：遍历未排序区间的元素
    for(int i = 1; i < n; i++) {  
        temp = k[i];  
        // 内层循环：向前遍历已排序区间（j从i-1开始），找到temp的插入位置
        // 循环条件：j≥0（未遍历完已排序区间）且 temp < k[j]（当前元素比temp大，需要后移）
        int j;  // 单独声明j，方便循环结束后获取插入位置
        for(j = i - 1; j >= 0 && temp < k[j]; j--) {  
            k[j + 1] = k[j];  // 将k[j]后移一位，为temp腾出位置
        }
        k[j + 1] = temp;  // 将temp插入到正确位置（j+1是第一个≤temp的元素的下一位）
    }  
}

堆排序

#include <iostream>  
#include <algorithm>  // 提供swap函数
using namespace std;

/**
 * @brief 非递归维护最大堆的性质（核心函数）
 * @param arr 待维护的堆数组（最大堆）
 * @param start 需要调整的父节点起始下标（堆顶/待修复节点）
 * @param end 堆的最后一个元素下标（堆的边界，超出则无需调整）
 * 逻辑：从start节点开始，向下迭代比较父节点与子节点，确保父节点≥子节点（最大堆性质）
 */
void max_heapify(int arr[], int start, int end) {  
    // 初始化父节点、子节点下标：
    // dad = 当前需要调整的父节点（初始为start）
    // son = dad的左子节点（堆的下标规则：左子=2*dad+1，右子=2*dad+2）
    int dad = start;  
    int son = dad * 2 + 1;  

    // 循环条件：子节点下标不超过堆的边界（son ≤ end）
    while (son <= end) {  
        // 第一步：比较两个子节点（左/右），选择值更大的那个子节点
        // 注意：son+1 ≤ end 确保右子节点存在，避免越界
        if (son + 1 <= end && arr[son] < arr[son + 1]) {
            son++;  // 右子节点更大，切换到右子节点
        }

        // 第二步：判断父节点是否已经≥最大的子节点（满足最大堆性质）
        if (arr[dad] > arr[son]) {
            return;  // 堆性质已满足，直接退出
        } 
        // 第三步：父节点 < 子节点，交换父子节点，继续向下调整
        else {  
            swap(arr[dad], arr[son]);  // 交换父子节点值
            dad = son;                 // 父节点下标更新为当前子节点（继续调整下一层）
            son = dad * 2 + 1;         // 子节点下标更新为新父节点的左子节点
        }  
    }  
}  

/**
 * @brief 堆排序主函数（升序排序）
 * @param arr 待排序的数组
 * @param len 数组长度
 * 核心步骤：1. 构建最大堆；2. 交换堆顶与未排序区间末尾，重整堆结构
 */
void heap_sort(int arr[], int len) {  
    // 第一步：构建最大堆
    // 从最后一个非叶子节点开始向前遍历，逐个调整为最大堆
    // 最后一个非叶子节点下标 = len/2 - 1（堆的下标从0开始）
    for (int i = len / 2 - 1; i >= 0; i--) {
        max_heapify(arr, i, len - 1);  // 调整以i为根的子堆
    }  

    // 第二步：堆排序（升序）
    // 从数组末尾向前遍历，逐个将堆顶（最大值）交换到当前未排序区间末尾
    for (int i = len - 1; i > 0; i--) {  
        swap(arr[0], arr[i]);  // 堆顶（最大值）交换到未排序区间的最后一位
        // 重整堆：仅调整[0, i-1]区间（已排序的i位置不再参与堆调整）
        max_heapify(arr, 0, i - 1);  
    }  
}

// 测试主函数（补充后可直接运行）
int main() {
    int arr[] = {9, 5, 7, 1, 3, 8, 2, 6, 4};
    int len = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前数组：";
    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    heap_sort(arr, len);

    cout << "排序后数组：";
    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

堆排序c++标准库版

#include <bits/stdc++.h>  // 万能头文件：包含vector、algorithm、iostream等核心头文件
using namespace std;  

int main() {  
    // 初始化待处理的vector数组：元素为1~9的升序序列
    vector<int> a = {1,2,3,4,5,6,7,8,9};  

    // 第一步：构建最大堆（默认构建最大堆，堆顶为数组最大值）
    // 作用：将vector a从无序状态转为最大堆结构（完全二叉树，父节点≥子节点）
    make_heap(a.begin(), a.end());  

    // 输出构建后的最大堆数组
    cout << "构建最大堆后的数组：";
    for(int i : a) {  // 范围for循环遍历vector（C++11及以上支持）
        cout << i << " ";  
    }  
    cout << endl;  

    // 第二步：堆排序（基于已构建的最大堆，升序排序）
    // 注意：sort_heap必须基于make_heap构建的堆，否则行为未定义
    sort_heap(a.begin(), a.end());  

    // 输出堆排序后的升序数组
    cout << "堆排序后的升序数组：";
    for(int i : a) {  
        cout << i << " ";  
    }  
    cout << endl;

    return 0;  
}

FFT

两个多项式的多项式乘法

#include <iostream>  
#include<bits/stdc++.h>  
using namespace std;  

const int maxn = 1000000 + 7;  
#define PI acos(-1)  

// Complex结构体
struct Complex {  
    double x, y; // 实部和虚部  
    Complex operator+(const Complex &b) const {  
        return {x + b.x, y + b.y};  
    }  
    Complex operator-(const Complex &b) const {  
        return {x - b.x, y - b.y};  
    }  
    Complex operator*(const Complex &b) const {  
        return {x * b.x - y * b.y, x * b.y + y * b.x};  
    }  
};  

int n,m; // 两个多项式的次数  
Complex a[maxn*3], b[maxn*3]; // 存储多项式的系数  

// FFT函数
void FFT(Complex* A, int len, int type) {
    // 预处理位逆序位置
    int *pos = new int[len];
    pos[0] = 0;
    for (int i = 1; i < len; i++) {
        pos[i] = pos[i >> 1] >> 1;
        if (i & 1) pos[i] |= len >> 1;
    }
    // 按位逆序重排
    for (int i = 0; i < len; i++) {
        if (i < pos[i]) swap(A[i], A[pos[i]]);
    }
    // 合并区间
    for (int L = 2; L <= len; L <<= 1) {
        int half = L / 2;
        Complex Wn = {cos(2.0 * PI / L), type * sin(2.0 * PI / L)};
        for (int R = 0; R < len; R += L) {
            Complex w = {1, 0};
            for (int k = 0; k < half; k++, w = w * Wn) {
                Complex buf = A[R + k];
                A[R + k] = buf + w * A[R + k + half];
                A[R + k + half] = buf - w * A[R + k + half];
            }
        }
    }
    // IDFT时归一化
    if (type == -1) {
        for (int i = 0; i < len; i++) {
            A[i].x /= len;
            A[i].y /= len;
        }
    }
    delete[] pos; // 释放动态内存，避免泄漏
}  

int main(){  
    int maxLen = 1, l = 0; // maxLen为FFT的长度，l为log2(maxLen)  
    scanf("%d%d", &n, &m);  

    // 计算满足条件的最小2的幂次
    while(maxLen < n+m+1){  
        maxLen <<= 1;  
        l++;  
    }  

    // 读取第一个多项式的系数
    for(int i = 0;i<=n;i++){  
        scanf("%lf",&a[i].x);  
    }  
    // 读取第二个多项式的系数
    for(int i = 0;i<=m;i++){  
        scanf("%lf",&b[i].x);  
    }  

    // 正FFT：时域→频域
    FFT(a, maxLen, 1);  
    FFT(b, maxLen, 1);  

    // 频域相乘（对应多项式卷积）
    for(int i = 0;i<maxLen;i++)  
        a[i] = a[i] * b[i];  

    // 逆FFT：频域→时域
    FFT(a, maxLen, -1);  

    // 输出卷积结果（四舍五入为整数）
    for(int i=0; i<n+m+1; i++){  
        if(i != 0) printf(" ");  
        printf("%d", (int)(a[i].x + 0.49)); // +0.49等价于四舍五入
    }  
    printf("\n");  

    return 0;  
}

题目

#include <iostream>  
#include<bits/stdc++.h>  
using namespace std;  

const int maxn = 1000000 + 7;  
#define PI acos(-1)  

// Complex结构体
struct Complex {  
    double x, y; // 实部和虚部  
    Complex operator+(const Complex &b) const {  
        return {x + b.x, y + b.y};  
    }  
    Complex operator-(const Complex &b) const {  
        return {x - b.x, y - b.y};  
    }  
    Complex operator*(const Complex &b) const {  
        return {x * b.x - y * b.y, x * b.y + y * b.x};  
    }  
};

// FFT函数
void FFT(Complex* A, int len, int type) {
    // 预处理位逆序位置
    int *pos = new int[len];
    pos[0] = 0;
    for (int i = 1; i < len; i++) {
        pos[i] = pos[i >> 1] >> 1;
        if (i & 1) pos[i] |= len >> 1;
    }
    // 按位逆序重排
    for (int i = 0; i < len; i++) {
        if (i < pos[i]) swap(A[i], A[pos[i]]);
    }
    // 合并区间
    for (int L = 2; L <= len; L <<= 1) {
        int half = L / 2;
        Complex Wn = {cos(2.0 * PI / L), type * sin(2.0 * PI / L)};
        for (int R = 0; R < len; R += L) {
            Complex w = {1, 0};
            for (int k = 0; k < half; k++, w = w * Wn) {
                Complex buf = A[R + k];
                A[R + k] = buf + w * A[R + k + half];
                A[R + k + half] = buf - w * A[R + k + half];
            }
        }
    }
    // IDFT时归一化
    if (type == -1) {
        for (int i = 0; i < len; i++) {
            A[i].x /= len;
            A[i].y /= len;
        }
    }
    delete[] pos; // 释放动态内存，避免泄漏
}

int main()
{
    int n;cin>>n;
    int N=1<<n;
    Complex *f = new Complex[N]; // 动态分配，避免栈溢出
    for(int i=0;i<N;i++) {
        int c;cin>>c;
        f[i].x=c;
        f[i].y=0;
    }
    
    FFT(f,N,1);

    Complex z={0,0};   
    for(int k=0;k<N;k++) {
        double cos_k = cos(k);
        z = z + Complex{cos_k * f[k].x, cos_k * f[k].y};
    }

    printf("%.2f %.2f\n", z.x, z.y);
    delete[] f; // 释放动态内存
    return 0;
}

高精度乘法

#include <iostream>  
#include<bits/stdc++.h>  
using namespace std;  

const int maxn = 1000000 + 7;  
#define PI acos(-1)  

// Complex结构体
struct Complex {  
    double x, y; // 实部和虚部  
    Complex operator+(const Complex &b) const {  
        return {x + b.x, y + b.y};  
    }  
    Complex operator-(const Complex &b) const {  
        return {x - b.x, y - b.y};  
    }  
    Complex operator*(const Complex &b) const {  
        return {x * b.x - y * b.y, x * b.y + y * b.x};  
    }  
};

// FFT函数
void FFT(Complex* A, int len, int type) {
    // 预处理位逆序位置
    int *pos = new int[len];
    pos[0] = 0;
    for (int i = 1; i < len; i++) {
        pos[i] = pos[i >> 1] >> 1;
        if (i & 1) pos[i] |= len >> 1;
    }
    // 按位逆序重排
    for (int i = 0; i < len; i++) {
        if (i < pos[i]) swap(A[i], A[pos[i]]);
    }
    // 合并区间
    for (int L = 2; L <= len; L <<= 1) {
        int half = L / 2;
        Complex Wn = {cos(2.0 * PI / L), type * sin(2.0 * PI / L)};
        for (int R = 0; R < len; R += L) {
            Complex w = {1, 0};
            for (int k = 0; k < half; k++, w = w * Wn) {
                Complex buf = A[R + k];
                A[R + k] = buf + w * A[R + k + half];
                A[R + k + half] = buf - w * A[R + k + half];
            }
        }
    }
    // IDFT时归一化
    if (type == -1) {
        for (int i = 0; i < len; i++) {
            A[i].x /= len;
            A[i].y /= len;
        }
    }
    delete[] pos; // 释放动态内存，避免泄漏
}

int n, m; // 两个大数的长度（对应多项式次数）  
Complex a[maxn*3], b[maxn*3]; // 存储多项式系数（大数的逆序数字）  
long long ans[maxn*3];        // 存储大数乘法结果（进位后）  

int main(){  
    int t;  
    scanf("%d", &t);  
    while(t--){  
        int maxLen = 1, l = 0; // maxLen为FFT长度（2的幂），l=log2(maxLen)  
        char str1[maxn], str2[maxn];  
        scanf(" %s %s", str1, str2); // 读取两个大数字符串  

        // 计算大数长度（对应多项式次数）
        n = strlen(str1);  
        m = strlen(str2);  

        // 计算满足条件的最小2的幂次（需≥n+m）
        while(maxLen < n + m){ // 优化：无需+1，n+m已足够
            maxLen <<= 1;  
            l++;  
        }  

        // 初始化数组（清空之前的结果）
        for(int i=0; i<=maxLen; i++){  
            a[i].x = a[i].y = 0;  
            b[i].x = b[i].y = 0;  
            ans[i] = 0;  
        }  

        // 大数转多项式系数（逆序存储：个位→下标0，十位→下标1...）
        for(int i = 0; i < n; i++) {  
            a[i].x = str1[n - i - 1] - '0';  
        }  
        for(int i = 0; i < m; i++) {  
            b[i].x = str2[m - i - 1] - '0';  
        }  

        // 正FFT：时域（数字）→ 频域
        FFT(a, maxLen, 1);  
        FFT(b, maxLen, 1);  

        // 频域相乘（对应多项式卷积，即大数乘法）
        for(int i = 0; i < maxLen; i++)  
            a[i] = a[i] * b[i];  

        // 逆FFT：频域→时域（卷积结果）
        FFT(a, maxLen, -1);  

        // 处理进位（大数乘法核心：将卷积结果转为十进制数）
        for (int i = 0; i < maxLen; i++){  
            ans[i] += round(a[i].x); // 浮点转整数（四舍五入）
            ans[i + 1] += ans[i] / 10; // 进位到高位
            ans[i] %= 10; // 保留当前位（0-9）
        }  

        // 去除结果前导零（从后往前找第一个非零位）
        int t1 = maxLen;  
        while (ans[t1] == 0 && t1 > 0)  
            t1--;  

        // 输出结果（逆序输出：从高位到低位）
        while (t1 >= 0)  
            printf("%lld", ans[t1--]);  
        cout << endl;  
    }  
    return 0;  
}  

最大公约数辗转相除法（欧几里得算法）

int euclid(int a, int b){
	if(b == 0){
		return a;
	}else{
		return euclid(b, a%b);
	}
}