首页acwing算法基础课模版

acwing算法基础课模版

时间: 2025-01-25 09:03:59 AIGC 浏览: 44

### AcWing 算法基础课模板示例代码 #### 归并排序求逆序对数量归并排序可以用于计算数组中的逆序对数量。这种方法基于分治思想，在每次合并两个有序子数组的过程中统计跨越这两个子数组的逆序对数目。 ```cpp #include <iostream> using namespace std; long long merge_and_count(int a[], int temp[], int l, int r) { if (l >= r) return 0; int mid = (l + r) >> 1; long long res = merge_and_count(a, temp, l, mid) + merge_and_count(a, temp, mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (a[i] <= a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; res += mid - i + 1; // 记录逆序数 } } while (i <= mid) temp[k++] = a[i++]; while (j <= r) temp[k++] = a[j++]; for (int i = l; i <= r; ++i) a[i] = temp[i]; return res; } long long inverse_pairs(int a[], int n) { int* temp = new int[n]; long long count = merge_and_count(a, temp, 0, n - 1); delete[] temp; return count; } ``` 此段代码实现了使用归并排序来查找给定整数数组`a`内的所有逆序对，并返回其总数目[^1]。 #### KMP字符串匹配算法模板 KMP算法是一种高效的字符串匹配方法，它能够在线性时间内完成模式串在主串中的定位工作。下面是一个简单的C++实现： ```cpp void get_next(const string& pattern, vector<

阅读全文