Datastrucure and algorithm collection --
二分
multiset
有序集合，默认从小到大
multiset<int> ms;
可以自定义比较器使它从大到小排序
multiset<int, greater<>> ms;
lower_bound
查找容器中第一个>= value的元素
#include <algorithm>
iterator lower_bound(iterator first, iterator last, const T& value);
vector<int> v = {1, 3, 5, 7, 9};
int target = 110;
auto it = lower_bound(v.begin(), v.end(), target);
if (it != v.end()) {
cout << "第一个不小于 " << target << " 的值是 " << *it << endl; } else {
cout << "所有元素都小于 " << target << endl;
}
upper_bound
返回第一个 > x 的元素位置
upper_bound(v.begin(), v.end(), x)
往前移动一个位置就是最后一个 <= k的元素
upper_bound(v.begin(), v.end(), x) - 1
二分答案
// **左满足（左true）**
int binary_search_l(int l, int r){
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
// **右满足（右true）**
int binary_search_r(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
flowchart TD
A[Christmas] -->|Get money| B(Go shopping)
B --> C{Let me think}
C -->|One| D[Laptop]
C -->|Two| E[iPhone]
C -->|Three| F[fa:fa-car Car]
滑动窗口
求最长窗口
枚举右端口，滑动左端口，窗口长度不减
/**
* 1208. 尽可能使字符串相等
* 将s[i]变为t[i]花费为|s[i] - t[i]|，求不超过花费maxCost，使s[l..r] == t[l..r]的最长 .[l..r]
* @param s
* @param t
* @param maxCost
* @return
* */
int equalSubstring(string s, string t, int maxCost) {
int n = (int) s.length();
int l = 0, r = 0, cost = 0/*, ans = 0*/;
for (r = 0; r < n; ++r) {
cost += abs(s[r] - t[r]);
// 考虑花费是否够
if (cost > maxCost) {
cost -= abs(s[l] - t[l]);
++l;
}
// ans = max(ans, r - l + 1);
}
// return ans;
// 由于这个滑动窗口每次最多滑入/划出一位，因此l-r+1本身就是最长的子串的长度。遍历完后n=r+1
return n - l;
}
/**
* 904. 水果成篮
* @param fruits * @return */int totalFruit_k(vector<int>& fruits, int k) {
/*
* 找到最长的子串，元素种类<=k
*/ int l = 0;
int n = (int) fruits.size();
unordered_map<int, int> cnt;
for (int r = 0; r < n; ++r) {
++cnt[fruits[r]];
if (cnt.size() > k) {
--cnt[fruits[l]];
if (cnt[fruits[l]] == 0) cnt.erase(fruits[l]);
++l;
}
}
return n - l;
}
int totalFruit(vector<int>& fruits) {
return totalFruit_k(fruits, 2);
}
求最短窗口
枚举右端口，滑动左端口至不满足条件，比较答案。
/**
* 209. 长度最小的子数组
* 求nums中 和>=target的最短子数组
*/
int minSubArrayLen(int target, vector<int>& nums) {
int n = (int) nums.size();
if (target == 0 or std::reduce(nums.begin(), nums.end()) < target) {
return 0;
}
int l = 0, r = 0, minLen = INT_MAX;
ll s = 0;
// 枚举右窗口
while (r < n) {
s += nums[r++];
// 尝试弹出左端口
while (l <= r and s >= target) { // 【注意】这时候比较运算符要取到=，因为r已经是下一个窗口右端口了
myPrintln(l, r)
s -= nums[l++]; // 【注意】这时候是像弹出左端口，再比较答案。
minLen = min(r - l + 1, minLen); // 在满足条件的情况下比较答案
}
}
return minLen;
}
int minSubArrayLen(int target, vector<int>& nums) {
int n = (int) nums.size();
if (target == 0 or std::reduce(nums.begin(), nums.end()) < target) {
return 0;
}
int l = 0, r = 0, minLen = INT_MAX;
ll s = 0;
// 枚举右窗口
while (r < n) {
s += nums[r++];
// 尝试弹出左端口
while (l <= r and s >= target) { // 注意这时候比较运算符要取到=，因为r已经是下一个窗口右端口了
minLen = min(r - l, minLen); // 在满足条件的情况下比较答案
s -= nums[l++];
}
// r++;
}
return minLen;
}
也可以用for循环的风格
int minSubArrayLen(int target, vector<int>& nums) {
int n = (int) nums.size();
if (target == 0 or std::reduce(nums.begin(), nums.end()) < target) {
return 0;
}
int l = 0, r = 0, minLen = INT_MAX;
ll s = 0;
// 枚举右窗口
while (r < n) {
s += nums[r];
// 尝试弹出左端口
while (l <= r and s >= target) { // 注意这时候比较运算符要取到=，因为r已经是下一个窗口右端口了
minLen = min(r - l + 1, minLen); // 在满足条件的情况下比较答案
s -= nums[l++];
}
r++;
}
return minLen;
}
/**
* 2904. 最短且字典序最小的美丽子字符串
* 求s中 '1'的个数==k的最短子数组中 字典序最小的那个子数组
* @param s
* @param k
* @return
**/
string shortestBeautifulSubstring(const string &s, int k) {
if (ranges::count(s, '1') < k) return "";
int n = (int) s.size(), n1 = 0;
string ans = s;
int l = 0, r = 0;
while (r < n) {
n1 += s[r++] == '1';
while (l <= r and n1 >= k) {
n1 -= s[l++] == '1';
// dbg( s.substr(l-1, r - l + 1))
string substr = s.substr(l-1, r - l + 1);
if (ans.size() > r - l + 1) {
ans = substr;
} elif (ans.size() == r - l + 1 and ans > substr) {
ans = substr;
}
}
}
return ans;
}
求值为k的窗口有多少个
可以用差值法来解决，
值为k的窗口有多少个 = 值>=k的窗口有多少个 - 值>=k+1的窗口有多少个
/**
* 求和>=k的非空子数组有多少个
* @param nums
* @param k
* @return
* */
int numSubarraysWithSum_moreThan(vector<int>& nums, int k) {
ll ans = 0, summ = 0;
int n = (int) nums.size();
int l = 0, r = -1;
summ += nums[++r];
while (l < n and r < n) {
if (summ >= k and l <= r) {
ans += n - r;
summ -= nums[l++];
} else {
summ += nums[++r];
}
}
return ans;
}
/**
* 930. 和相同的二元子数组
* 求和为goal的非空子数组有多少个
* @param nums * @param goal * @return */int numSubarraysWithSum(vector<int>& nums, int goal) {
return numSubarraysWithSum_moreThan(nums, goal) - numSubarraysWithSum_moreThan(nums, goal+1);
}
双指针
/**
* 反转
* @param s
* */
void reverseString(vector<char>& s) {
int l = 0, r = (int) s.size() - 1;
while (l < r) {
swap(s[l++], s[r--]);
}
}
/**
* 验证回文串
* @param s
* @return
* */
bool isPalindrome(const string &s) {
int l = 0, r = (int) s.size() - 1;
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
同向双指针
/**
* 611. 有效三角形的个数
* 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
* @param nums
* @return
* */
int triangleNumber(vector<int>& nums) {
ranges::sort(nums);
int ans = 0, n = (int) nums.size();
for (int k = 2; k < n; ++k) {
int c = nums[k];
int i = 0; // a=nums[i]
int j = k - 1; // b=nums[j]
while (i < j) {
if (nums[i] + nums[j] > c) {
// 说明组合{nums[i ~ j-1], nums[j], nums[k]} 都是合法的
ans += j - i;
--j;
} else {
++i;
}
}
}
return ans;
}
/**
* 1574. 删除最短的子数组使剩余数组有序
* @param arr
* @return
* */
int findLengthOfShortestSubarray(vector<int>& arr) {
/*
* 枚举左端点（l），移动右端点（r）。
* 即考虑移除arr[l..r]
*/
int n = (int) arr.size(), r = n - 1;
// 找到递增后缀。即计算初始时l=0时 r的位置
while (r > 0 and arr[r - 1] <= arr[r]) {
--r;
}
if (r == 0) return 0;
int ans = r; // 可以删除掉前缀 （删除 0 到 r - 1）
for (int l = 0; l == 0 or arr[l-1] <= arr[l] ; ++l) {
while (r < n and arr[r] < arr[l]) ++r; // 计算最左的可以满足条件的r
ans = min(ans, r - l - 1);
}
return ans;
}
单调栈
/**
* 739. 每日温度
* @param temperatures
* @return
* */
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = (int) temperatures.size();
vector ans(n, 0);
stack<int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() and temperatures[i] > temperatures[stk.top()]) {
int j = stk.top();
stk.pop();
ans[j] = i - j;
}
stk.push(i);
}
return ans;
}
位运算
求二进制数中1的个数
int n1 = __builtin_popcount(num);
或
popcount((unsigned) num);
实现查询数组：求二进制数中1的个数
for (int i = 1; i <= mm; ++i) {
cnt1[i] = cnt1[i >> 1] + (i & 1);
}
求一个数的二进制位数
bit_width((unsigned) num);
对一个数字二进制取反，但是不取反符号位
return ~num & ((1 << bit_width((unsigned )num)) - 1);
bitset<num>
通过一个数字初始化为位数组。
取反
auto x = bitset<18>(7);
x = ~x;
dbg(x);// to_string的时候是从高位往低位的。
或
auto x = bitset<18>(7);
int mask = (1 << 18) - 1;
x ^= mask;
dbg(x);
数据结构
并查集
class UnionFind {
/**
* 不带秩并查集
*/
public:
vector<int> parent;
public:
UnionFind(size_t n) {
parent.resize(n + 1);
iota(parent.begin(), parent.end(), 0); // need #include <numeric>
}
int find(int index) {
if (index == parent[index]) {
return index;
}
parent[index] = find(parent[index]);
return parent[index];
}
void merge(int index1, int index2) {
parent[find(index1)] = find(index2);
}
bool connected(int index1, int index2) {
return find(index1) == find(index2);
}
};
class DisjointedSet {
/**
* 带秩并查集
*/
public:
vector<int> parent; // 存储父节点
vector<int> rank; // 存储树的秩（用于按秩合并）
public:
/**
* 初始化并查集。n为元素个数
*/
DisjointedSet(size_t n) {
parent.resize(n + 1);
rank.resize(n + 1, 0);
for (int i = 0; i <= n; ++i) {
parent[i] = i;
}
}
/**
* 查找操作，(带路径压缩)
*/
int find(int x) {
while (x != parent[x]) {
x = parent[x] = parent[parent[x]];
}
return x;
}
/**
* 合并操作，按秩合并.
* 按秩合并（Union by Rank）是一种优化并查集合并操作的方法，目的是让树尽可能地保持平衡，从而减少树的高度，提升查找操作的效率。
* 在并查集中，秩通常表示树的高度（或深度）的近似值。
* 并查集的每个节点都有一个秩值，初始时所有节点的秩为 0。
* 合并两个集合时，比较它们的秩。
* 将秩较小的树的根节点连接到秩较大的树的根节点上。
* 如果两棵树的秩相同，则任选一棵树作为新的根，并将其秩加 1。
*/
void merge(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX != rootY) {
if ((rank[rootX] < rank[rootY])) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
++rank[rootX];
}
}
}
/**
* 判断两个节点是否属于同一集合
*/
bool connected(int x, int y) {
return find(x) == find(y);
}
};
class UnionFind {
vector<int> fa; // 代表元
vector<int> sz; // 集合大小
public:
int cc; // 连通块个数
UnionFind(int n) : fa(n), sz(n, 1), cc(n) {
// 一开始有 n 个集合 {0}, {1}, ..., {n-1} // 集合 i 的代表元是自己，大小为 1 ranges::iota(fa, 0); // iota(fa.begin(), fa.end(), 0);
}
// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
int find(int x) {
// 如果 fa[x] == x，则表示 x 是代表元
if (fa[x] != x) {
fa[x] = find(fa[x]); // fa 改成代表元
}
return fa[x];
}
// 判断 x 和 y 是否在同一个集合
bool is_same(int x, int y) {
// 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
// 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
return find(x) == find(y);
}
// 把 from 所在集合合并到 to 所在集合中
// 返回是否合并成功
bool merge(int from, int to) {
int x = find(from), y = find(to);
if (x == y) { // from 和 to 在同一个集合，不做合并
return false;
}
fa[x] = y; // 合并集合。修改后就可以认为 from 和 to 在同一个集合了
sz[y] += sz[x]; // 更新集合大小（注意集合大小保存在代表元上）
// 无需更新 sz[x]，因为我们不用 sz[x] 而是用 sz[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 sz[x] cc--; // 成功合并，连通块个数减一
return true;
}
// 返回 x 所在集合的大小
int get_size(int x) {
return sz[find(x)]; // 集合大小保存在代表元上
}
};
class UnionFind:
def __init__(self, n: int):
# 一开始有 n 个集合 {0}, {1}, ..., {n-1} # 集合 i 的代表元是自己，大小为 1 self._fa = list(range(n)) # 代表元
self._size = [1] * n # 集合大小
self.cc = n # 连通块个数
# 返回 x 所在集合的代表元
# 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
def find(self, x: int) -> int:
# 如果 fa[x] == x，则表示 x 是代表元
if self._fa[x] != x:
self._fa[x] = self.find(self._fa[x]) # fa 改成代表元
return self._fa[x]
# 判断 x 和 y 是否在同一个集合
def is_same(self, x: int, y: int) -> bool:
# 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
# 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
return self.find(x) == self.find(y)
# 把 from 所在集合合并到 to 所在集合中
# 返回是否合并成功
def merge(self, from_: int, to: int) -> bool:
x, y = self.find(from_), self.find(to)
if x == y: # from 和 to 在同一个集合，不做合并
return False
self._fa[x] = y # 合并集合。修改后就可以认为 from 和 to 在同一个集合了
self._size[y] += self._size[x] # 更新集合大小（注意集合大小保存在代表元上）
# 无需更新 _size[x]，因为我们不用 _size[x] 而是用 _size[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 _size[x] self.cc -= 1 # 成功合并，连通块个数减一
return True
# 返回 x 所在集合的大小
def get_size(self, x: int) -> int:
return self._size[self.find(x)] # 集合大小保存在代表元上
树状数组
功能：
- 初始化：支持
N个元素的树状数组。 - 单点更新：在索引
idx处增加一个值val。 - 前缀和查询：查询
[1, idx]区间的前缀和。 - 区间和查询：查询
[l, r]的区间和（利用sum(r) - sum(l-1)计算）。
#include <iostream>
class FenwickTree {
private:
int *bit; // 树状数组
int size; // 数组大小
// 计算最低位的1
int lowbit(int x) {
return x & (-x);
}
public:
// 构造函数
FenwickTree(int n) {
size = n;
bit = new int[n + 1]; // 1-based index
for (int i = 0; i <= n; i++) {
bit[i] = 0;
}
}
// 析构函数
~FenwickTree() {
delete[] bit;
}
// 单点更新：在 idx 位置增加 val
void update(int idx, int val) {
while (idx <= size) {
bit[idx] += val;
idx += lowbit(idx);
}
}
// 前缀和查询：求 [1, idx] 的和
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= lowbit(idx);
}
return sum;
}
// 区间和查询：求 [l, r] 的和
int rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
};
// 测试代码
int main() {
int n = 10;
FenwickTree ft(n);
// 初始化一些值
ft.update(1, 5);
ft.update(2, 3);
ft.update(3, 7);
ft.update(4, 9);
ft.update(5, 6);
std::cout << "前缀和 query(5): " << ft.query(5) << std::endl; // 5+3+7+9+6 = 30
std::cout << "区间和 rangeQuery(2, 4): " << ft.rangeQuery(2, 4) << std::endl; // 3+7+9 = 19
return 0;
}
代码解析
lowbit(x)计算x的最低位1，即x & (-x)。update(idx, val)更新idx位置的值，并向上级节点传播更新。query(idx)计算[1, idx]的前缀和，通过回溯累加所有相关bit数组的值。rangeQuery(l, r)计算[l, r]的区间和，利用query(r) - query(l-1)快速计算。
时间复杂度
- 单点更新：
O(log N) - 前缀和查询：
O(log N) - 区间查询：
O(log N)
class FenwickTree {
private:
std::vector<int> bit;
std::vector<int> arr;
int n;
public:
FenwickTree(int size) : n(size), bit(size + 1, 0), arr(size + 1, 0) {}
FenwickTree(const std::vector<int>& inputArr) : n(inputArr.size()), bit(inputArr.size() + 1, 0), arr(inputArr.size() + 1, 0) {
for (int i = 1; i <= n; i++) {
set(i, inputArr[i - 1]);
}
}
FenwickTree(){}
// 单点更新，在 idx 位置增加 delta void update(int idx, int delta) {
while (idx <= n) {
bit[idx] += delta;
idx += idx & -idx; // 低位操作
}
}
// 查询前缀和 [1, idx] int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & -idx;
}
return sum;
}
// 查询区间 [l, r] 的和
int rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
// 将第 i 个元素改为 x void set(int idx, int x) {
int delta = x - arr[idx];
arr[idx] = x;
update(idx, delta);
}
// 获取第 i 个元素的值
int get(int idx) {
return arr[idx];
}
};
线段树 -- 单点更新，区间查询 --V1
#include <iostream>
#include <vector>
#include <climits> // 用于INT_MAX
using namespace std;
class SegmentTree {
private:
vector<int> arr; // 原始数组
vector<int> segTree; // 线段树数组
int n; // 数组大小
void build(int index, int left, int right) {
if (left == right) {
segTree[index] = arr[left];
return;
}
int mid = (left + right) / 2;
build(2 * index, left, mid);
build(2 * index + 1, mid + 1, right);
segTree[index] = min(segTree[2 * index], segTree[2 * index + 1]);
}
void update(int index, int left, int right, int pos, int value) {
if (left == right) {
segTree[index] = value;
return;
}
int mid = (left + right) / 2;
if (pos <= mid) {
update(2 * index, left, mid, pos, value);
} else {
update(2 * index + 1, mid + 1, right, pos, value);
}
segTree[index] = min(segTree[2 * index], segTree[2 * index + 1]);
}
int query(int index, int left, int right, int ql, int qr) {
if (ql > right || qr < left) return INT_MAX; // 超出查询范围
if (ql <= left && qr >= right) return segTree[index]; // 完全包含
int mid = (left + right) / 2;
return min(query(2 * index, left, mid, ql, qr), query(2 * index + 1, mid + 1, right, ql, qr));
}
public:
SegmentTree(const vector<int>& inputArr) {
n = inputArr.size();
arr = inputArr;
segTree.resize(4 * n, INT_MAX);
build(1, 0, n - 1);
}
void update(int pos, int value) {
update(1, 0, n - 1, pos, value);
}
int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
int main() {
int n, q;
cin >> n >> q; // 读取数组大小和查询次数
vector<int> inputArr(n);
for (int i = 0; i < n; i++) cin >> inputArr[i];
SegmentTree segTree(inputArr);
while (q--) {
char op;
cin >> op;
if (op == 'U') { // 更新操作 'U pos value'
int pos, value;
cin >> pos >> value;
segTree.update(pos, value);
} else if (op == 'Q') { // 查询操作 'Q l r'
int l, r;
cin >> l >> r;
cout << segTree.query(l, r) << "\n";
}
}
return 0;
}
线段树 -- 单点更新，区间查询 --V2
/**
* 线段树（单点更新，区间查询）
* 查询，更新的 数组下标从0开始
* 查询的区间是双端包含的（[l..r]）
*/
template<typename T>
class SegmentTree {
private:
vector<T> arr; // 原始数组
vector<T> segTree; // 线段树数组
int n; // 数组大小
function<T(T,T)> opr; // 运算方式，比如max，min，+，*, ^ 等
T initialNum;
/**
* 递归构建线段树。
* @param index 根结点在segTree中的索引。整棵线段树的根结点一般是1.
* @param left 当前结点代表的区间的左边界（起始位置）。
* @param right 当前结点代表的区间的右边界（结束位置）。
*/ void build(int index, int left, int right) {
if (left == right) {
segTree[index] = arr[left];
return;
}
int mid = (left + right) >> 1;
build(2 * index, left, mid); // 构建左子树
build(2 * index + 1, mid + 1, right); // 构建右子树
segTree[index] = opr(segTree[2 * index], segTree[2 * index + 1]); // (递归)计算当前结点的数据
}
/**
* 单点更新
* @param index 根结点
* @param left （线段树）区间左端点
* @param right （线段树）区间右端点
* @param pos 更新位置
* @param value 新值
*/ void update(int index, int left, int right, int pos, int value) {
if (left == right) {
segTree[index] = value;
return;
}
int mid = (left + right) >> 1;
if (pos <= mid) {
// 要跟新的点在左区间
update(2 * index, left, mid, pos, value);
} else {
// 要跟新的点在右区间
update(2 * index + 1, mid + 1, right, pos, value);
}
// 计算根结点的值
segTree[index] = opr(segTree[2 * index], segTree[2 * index + 1]);
}
/**
* 区间查询
* @param index 根结点
* @param left （线段树）区间左端点
* @param right （线段树）区间右端点
* @param ql 查询区间左端点
* @param qr 查询区间右端点
* @return 查询区间[ql..qr]
*/ int query(int index, int left, int right, int ql, int qr) {
if (ql > right || qr < left) return initialNum; // 超出查询范围
if (ql <= left && qr >= right) return segTree[index]; // 完全包含
int mid = (left + right) >> 1;
return opr(query(2 * index, left, mid, ql, qr), query(2 * index + 1, mid + 1, right, ql, qr));
}
public:
// 构建线段树。初始数组，运算方法。
SegmentTree(const vector<T>& inputArr, const string &operateMethod) {
if (operateMethod == "min") {
this->opr = (function<T(T,T)>) [&](T a, T b) {return min(a, b);};
this->initialNum = INT_MAX;
} else if (operateMethod == "max") {
this->opr = (function<T(T,T)>) [&](T a, T b){return max(a,b);};
this->initialNum = INT_MIN;
} else if (operateMethod == "+") {
this->opr = (function<T(T,T)>) [&](T a, T b) {return a + b;};
this->initialNum = 0;
} else if (operateMethod == "*") {
this->opr = (function<T(T,T)>) [&](T a, T b) {return a * b;};
this->initialNum = 1;
} else {
throw error_code();
}
n = inputArr.size();
arr = inputArr;
segTree.resize(4 * n, initialNum);
build(1, 0, n - 1);
}
/**
* 单点更新
* @param pos 位置下标（从0开始）
* @param value 更新为新值
*/ void update(int pos, int value) {
this->update(1, 0, n - 1, pos, value);
}
/**
* 区间查询
* @param l 区间左端点（包含）
* @param r 区间右端点（包含）
* @return 查询区间[l..r]
*/ int query(int l, int r) {
return this->query(1, 0, n - 1, l, r);
}
/**
* 二分查询第一个满足条件：query(begin, r) > val 的 r * @param val * @return */ int firstSatisfied(int begin, T val) {
int l = 0, r = arr.size();
while (l < r) {
int mid = (l + r) >> 1;
if (query(begin, mid) > val) r = mid;
else l = mid + 1;
}
return l < arr.size() ? l : -1;
}
/**
* 二分查询最后一个满足条件：query(l, ..) > val 的 l * @param val * @return */ int lastSatisfied(int end, T val) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (query(mid, r) > val) l = mid;
else r = mid - 1;
}
return l <= arr.size() ? l : -1;
}
};
二分线段树 -- 单点更新，区间查询
/**
* 线段树（单点更新，区间查询）
* 查询、更新数组下标从0开始，区间查询为闭区间 [l, r]
*/
template<typename T>
class SegmentTree {
private:
vector<T> arr; // 原始数组
vector<T> segTree; // 线段树数组，1-indexed
int n; // 数组大小
function<T(T,T)> opr; // 运算方式，例如 min, max, +, *
T initialNum; // 初始值
void build(int index, int left, int right) {
if (left == right) {
segTree[index] = arr[left];
return;
}
int mid = (left + right) >> 1;
build(2 * index, left, mid);
build(2 * index + 1, mid + 1, right);
segTree[index] = opr(segTree[2 * index], segTree[2 * index + 1]);
}
void update(int index, int left, int right, int pos, int value) {
if (left == right) {
segTree[index] = value;
return;
}
int mid = (left + right) >> 1;
if (pos <= mid)
update(2 * index, left, mid, pos, value);
else
update(2 * index + 1, mid + 1, right, pos, value);
segTree[index] = opr(segTree[2 * index], segTree[2 * index + 1]);
}
int query(int index, int left, int right, int ql, int qr) {
if (qr < left || ql > right)
return initialNum;
if (ql <= left && right <= qr)
return segTree[index];
int mid = (left + right) >> 1;
return opr(query(2 * index, left, mid, ql, qr),
query(2 * index + 1, mid + 1, right, ql, qr));
}
// 内部函数：利用线段树结构，在区间 [ql, qr] 内，给定当前累积值 current，
// 查找第一个位置 i，使得 opr(current, seg[ql...i]) > val。
// current 作为引用传入，搜索过程中更新累积值。
int query_first(int idx, int L, int R, int ql, int qr, T ¤t, T val) {
// 当前区间与查询区间没有交集
if (R < ql || L > qr) return -1;
// 当前区间完全包含在查询区间内
if (ql <= L && R <= qr) {
T combined = opr(current, segTree[idx]);
// 如果整块区间累积后仍不满足条件，直接更新 current 并返回 -1
if (combined <= val) {
current = combined;
return -1;
}
// 否则，这一块内必存在满足条件的位置
// 当区间退化为叶子时，直接返回该位置
while (L < R) {
int mid = (L + R) >> 1;
int leftIdx = 2 * idx, rightIdx = 2 * idx + 1;
T leftCombined = opr(current, segTree[leftIdx]);
if (leftCombined > val) {
// 满足条件，则在左子树中继续查找
idx = leftIdx;
R = mid;
} else {
// 左子树不满足，累积左子树的结果后转向右子树
current = leftCombined;
idx = rightIdx;
L = mid + 1;
}
}
return L;
}
int mid = (L + R) >> 1;
int leftAns = query_first(2 * idx, L, mid, ql, qr, current, val);
if (leftAns != -1)
return leftAns;
return query_first(2 * idx + 1, mid + 1, R, ql, qr, current, val);
}
// 内部函数：利用线段树结构，在区间 [ql, qr] 内，给定当前累积值 current，
// 查找最后一个位置 i，使得 opr( seg[i...qr], current ) > val。
// 这里我们“反向”累积，即从右侧开始查找。为了简化实现，我们将查询区间反转思路。
int query_last(int idx, int L, int R, int ql, int qr, T ¤t, T val) {
if (R < ql || L > qr) return -1;
if (ql <= L && R <= qr) {
T combined = opr(segTree[idx], current);
if (combined <= val) {
current = combined;
return -1;
}
while (L < R) {
int mid = (L + R) >> 1;
int leftIdx = 2 * idx, rightIdx = 2 * idx + 1;
// 优先检查右子树，因为我们要找到最大的下标
T rightCombined = opr(segTree[rightIdx], current);
if (rightCombined > val) {
idx = rightIdx;
L = mid + 1;
} else {
current = opr(segTree[rightIdx], current);
idx = leftIdx;
R = mid;
}
}
return L;
}
int mid = (L + R) >> 1;
int rightAns = query_last(2 * idx + 1, mid + 1, R, ql, qr, current, val);
if (rightAns != -1)
return rightAns;
return query_last(2 * idx, L, mid, ql, qr, current, val);
}
public:
// 构造函数：根据初始数组和运算方式构造线段树
SegmentTree(const vector<T>& inputArr, const string &operateMethod) {
if (operateMethod == "min") {
this->opr = [&](T a, T b) { return min(a, b); };
this->initialNum = numeric_limits<T>::max();
} else if (operateMethod == "max") {
this->opr = [&](T a, T b) { return max(a, b); };
this->initialNum = numeric_limits<T>::min();
} else if (operateMethod == "+") {
this->opr = [&](T a, T b) { return a + b; };
this->initialNum = 0;
} else if (operateMethod == "*") {
this->opr = [&](T a, T b) { return a * b; };
this->initialNum = 1;
} else {
throw runtime_error("Unsupported operation");
}
n = inputArr.size();
arr = inputArr;
segTree.resize(4 * n, initialNum);
build(1, 0, n - 1);
}
// 单点更新：更新下标 pos 为新值 value
void update(int pos, int value) {
update(1, 0, n - 1, pos, value);
}
// 区间查询：[l, r]（两端闭区间）
int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
/**
* 利用线段树内部结构查找第一个满足条件的位置：
* 找到最小的 r，使得 query(begin, r) > val
* 若不存在，则返回 -1
*/
int firstSatisfied(int begin, T val) {
if (begin < 0 || begin >= n) return -1;
// 若整个区间 [begin, n-1] 都不满足，则直接返回 -1
if (query(begin, n - 1) <= val)
return -1;
T current = initialNum;
return query_first(1, 0, n - 1, begin, n - 1, current, val);
}
/**
* 利用线段树内部结构查找最后一个满足条件的位置：
* 找到最大的 l，使得 query(l, end) > val
* 若不存在，则返回 -1
*/
int lastSatisfied(int end, T val) {
if (end < 0 || end >= n) return -1;
// 若整个区间 [0, end] 都不满足，则直接返回 -1
if (query(0, end) <= val)
return -1;
T current = initialNum;
return query_last(1, 0, n - 1, 0, end, current, val);
}
};
离散结构
树
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
// 二叉树节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉树类
class BinaryTree {
private:
TreeNode* root; // 根节点
int maxDiameter; // 记录最大直径
unordered_map<int, int> inorderIndex; // 记录中序遍历索引，便于快速查找
int postIndex; // 后序遍历当前索引（从后向前遍历）
// 递归构建二叉树
TreeNode* buildTreeHelper(const vector<int>& preorder, const vector<int>& inorder, int inLeft, int inRight) {
if (inLeft > inRight) return nullptr;
int rootVal = preorder[preIndex++]; // 当前前序遍历的根节点
TreeNode* node = new TreeNode(rootVal);
int inIndex = inorderIndex[rootVal]; // 在中序遍历中的索引
// 先构建左子树，再构建右子树
node->left = buildTreeHelper(preorder, inorder, inLeft, inIndex - 1);
node->right = buildTreeHelper(preorder, inorder, inIndex + 1, inRight);
return node;
}
// 递归构建二叉树
TreeNode* buildTreeHelper(const vector<int>& inorder, const vector<int>& postorder, int inLeft, int inRight) {
if (inLeft > inRight) return nullptr;
int rootVal = postorder[postIndex--]; // 当前后序遍历的根节点
TreeNode* node = new TreeNode(rootVal);
int inIndex = inorderIndex[rootVal]; // 在中序遍历中的索引
// 先构建右子树，再构建左子树（因为 postIndex 从右往左遍历）
node->right = buildTreeHelper(inorder, postorder, inIndex + 1, inRight);
node->left = buildTreeHelper(inorder, postorder, inLeft, inIndex - 1);
return node;
}
// 递归构建二叉树
TreeNode* buildTreeHelper(const vector<int>& preorder, const vector<int>& postorder, int postLeft, int postRight) {
if (postLeft > postRight) return nullptr;
int rootVal = preorder[preIndex++]; // 当前前序遍历的根节点
TreeNode* node = new TreeNode(rootVal);
// 叶子节点，直接返回
if (postLeft == postRight) return node;
// 前序遍历的下一个节点是左子树的根
int leftRootVal = preorder[preIndex];
int leftRootIndex = postorderIndex[leftRootVal]; // 找到左子树根在后序遍历中的索引
// 递归构建左子树和右子树
node->left = buildTreeHelper(preorder, postorder, postLeft, leftRootIndex);
node->right = buildTreeHelper(preorder, postorder, leftRootIndex + 1, postRight - 1);
return node;
}
// 计算以当前节点为根的子树深度，并更新最大直径
int depth(TreeNode* node) {
if (!node) return 0;
int leftDepth = depth(node->left);
int rightDepth = depth(node->right);
// 更新全局最大直径
maxDiameter = max(maxDiameter, leftDepth + rightDepth);
// 返回当前节点的深度
return max(leftDepth, rightDepth) + 1;
}
// 获取左视图（BFS 层序遍历）
vector<int> getLeftView(TreeNode* root) {
vector<int> leftView;
if (!root) return leftView;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
leftView.push_back(q.front()->val); // 记录每层第一个节点
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return leftView;
}
// 获取右视图（BFS 层序遍历）
vector<int> getRightView(TreeNode* root) {
vector<int> rightView;
if (!root) return rightView;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
rightView.push_back(q.back()->val); // 记录每层最后一个节点
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return rightView;
}
public:
// 构造函数。通过中序序列，后续序列构建二叉树
BinaryTree(const vector<int>& inorder, const vector<int>& postorder) {
postIndex = postorder.size() - 1;
for (int i = 0; i < inorder.size(); i++) {
inorderIndex[inorder[i]] = i; // 预处理中序索引
}
root = buildTreeHelper(inorder, postorder, 0, inorder.size() - 1);
}
// 构造函数。通过前、中序
BinaryTree(const vector<int>& preorder, const vector<int>& inorder) {
preIndex = 0;
for (int i = 0; i < inorder.size(); i++) {
inorderIndex[inorder[i]] = i; // 预处理中序索引
}
root = buildTreeHelper(preorder, inorder, 0, inorder.size() - 1);
}
// 构造函数。前序、后序
BinaryTree(const vector<int>& preorder, const vector<int>& postorder) {
preIndex = 0;
for (int i = 0; i < postorder.size(); i++) {
postorderIndex[postorder[i]] = i; // 预处理后序索引
}
root = buildTreeHelper(preorder, postorder, 0, postorder.size() - 1);
}
// 计算并返回二叉树的直径
int getDiameter() {
depth(root);
return maxDiameter;
}
// 打印左视图
void printLeftView() {
vector<int> leftView = getLeftView(root);
cout << "L:";
for (int val : leftView) {
cout << " " << val;
}
cout << endl;
}
// 打印右视图
void printRightView() {
vector<int> rightView = getRightView(root);
cout << "R:";
for (int val : rightView) {
cout << " " << val;
}
cout << endl;
}
// 析构函数，递归删除所有节点
~BinaryTree() {
destroyTree(root);
}
private:
void destroyTree(TreeNode* node) {
if (!node) return;
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
};
DP
背包问题
01背包问题
/**
* 01-背包问题
* @param W 背包容量（背包最多能装多重的物品）
* @param weights 每个物品的重量
* @param values 每个物品的价值
* @return 背包所装物品的最大价值
*/ int knapsack_01(int W, const vector<int>& weights, const vector<int>& values) {
int n = (int) weights.size();
// dp[i][w]表示前i个物品，总重量不超过w时的最大价值
// 实际上就是取一个物品的子序列，求子序列的最大权值和
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 动态规划过程
for (int i = 1; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (weights[i - 1] <= w) {
// 物品i可以放
// i不放：dp[i][w] = dp[i-1][w]
// i放：dp[i][w] = dp[i-1][w - w[i]] + v[i]
// 因为weights和values下标是从0开始的，而dp下标是从1开始的，因此第i个物品的下标是i-1
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i-1]);
} else {
// 物品i放不下
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
void testKnapsack_01() {
/*4 10
3 4 2 3 4 5 5 7*/ int n, W;
// cout << "请输入物品个数和背包容量: ";
cin >> n >> W;
vector<int> weights(n), values(n);
// cout << "请输入每个物品的重量和价值: " << endl;
for (int i = 0; i < n; ++i) {
cin >> weights[i] >> values[i];
}
int result = knapsack_01(W, weights, values);
// cout << "最大总价值是: " << result << endl;
cout << result << endl;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, W;
cout << "Enter number of items and capacity of the knapsack: ";
cin >> n >> W;
vector<int> weights(n), values(n);
cout << "Enter the weights of the items: ";
for (int i = 0; i < n; ++i) {
cin >> weights[i];
}
cout << "Enter the values of the items: ";
for (int i = 0; i < n; ++i) {
cin >> values[i];
}
// 创建一个一维dp数组，用于存储背包容量为w时的最大价值
vector<int> dp(W + 1, 0);
/*
这里采用方向遍历法，防止过分累加
*/
// 动态规划过程
for (int i = 0; i < n; ++i) {
// 从后往前遍历，确保每次使用的dp值是上一轮的结果
for (int w = W; w >= weights[i]; --w) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
// 输出结果
cout << "Maximum value in knapsack of capacity " << W << " is: " << dp[W] << endl;
return 0;
}
最长公共子序列（LCS）
/**
* 1143. 最长公共子序列
* @param text1 * @param text2 * @return text1 和 text2 的最长公共子序列的长度
*/
int longestCommonSubsequence(const string &text1, const string &text2) {
/*
* 这个过程实际上类似于网格DP
*/ size_t n1 = text1.length(), n2 = text2.length();
// 假设text1，text2下标都是从1开始的
vector dp(n1 + 1, vector(n2 + 1, (size_t) 0)); // dp[i][j]表示text1[0..i]和text2[0..j]中最长公共子序列
/*
* 遍历两个字符串
*/
for (int i = 1; i <= n1; ++i) {
for (int j = 1; j <= n2; ++j) {
if (text1[i - 1] == text2[j - 1]) {
// 如果这两个字符相等
// dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 如果这两个字符不相等，取大的情况
// 这个过程有点像区间DP中的区间合并
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return (int) dp[n1][n2];
}
最长递增子序列（LIS）
/**
* 300. 最长递增子序列
* @param nums * @return */ int lengthOfLIS(vector<int>& nums) {
// 元素迭代法
map<int, int> f; // f[i] 表示以i结尾的最长公共子序列的长度
for (int num: nums) {
if (!f.contains(num)) { // 以i为结尾的子序列长度至少为1
f[num] = 1;
}
// 遍历之前的子序列，看能否接在末尾
for (auto &[k,v]: f) {
if (num > k) {
f[num] = max(f[num], v + 1);
}
}
}
int ans = 1;
for (auto &[k, v]: f) {
ans = max(ans, v);
}
return ans;
}
void test_lengthOfLIS() {
vecI v = {10,9,2,5,3,7,101,18};
// vecI v = {10,9,2,5,3};
// vecI v = {3,2,1, 2,3};
auto
res = lengthOfLIS(v);
dbg(res)
}
int lengthOfLIS1(vector<int>& nums) {
// 腾讯面试题（2025年03月04日）
// 做法2：二分，是一个思路题。思考 7891234 这个例子，维护一个 数组，把 nums[i] 插入到 arr[i - 1] < nums[i] 的位置（严格递增），替代 arr[i] /* * 元素迭代法 + 贪心优先法：
* 我们应该尽量使子序列的末尾最小，这样才能有更大的扩展空间。
*/ vector<int> arr;
for (int num : nums) {
// 如果要求严格递增的最长子序列长度，用lower_bound。如果非严格递增，用upper_bound。如果求递减，将元素每个数字变为相反数即可。
int id = (int) (std::lower_bound(arr.begin(), arr.end(), num) - arr.begin());
// id 是 nums[i] 应该被插入的位置。
if (id < arr.size()) {
arr[id] = num;
}
else {
arr.push_back(num);
}
}
return (int)arr.size();
}
划分型DP
/**
* 139. 单词拆分
* 求是否可以将s拆分成wordDict元素组成的集
* @param s
* @param wordDict
* @return
* */
bool wordBreak(string s, vector<string>& wordDict) {
set<string> ws(wordDict.begin(), wordDict.end());
vecI wordLengths; // 每个word的长度
for (auto &ss: ws) {
wordLengths.push_back((int)ss.length());
}
int n = (int) s.length();
vector canPartition(n+1, false);
canPartition[0] = true;
// 枚举右端点，判断它的右侧是否可以划分
for (int i = 0; i < n; ++i) {
int l;
for (int len: wordLengths) {
l = i + 1 - len;
if (l >= 0 and canPartition[l] and ws.contains(s.substr(l, len))){
canPartition[i+1] = true;
break;
}
}
}
return canPartition[n];
}
void test_wordBreak() {
vector<string>
v1 = {"cats","dog","sand","and","cat"};
auto
res = this->wordBreak("catsandog", v1);
dbg(res)
}
状态机DP
/**
* 121. 买卖股票的最佳时机 交易一次
* 找到 $i<j$ 使 $prices[j] - prices[i]$ 最大
* @param prices * @return */int maxProfit_1(vector<int>& prices) {
int ans = 0;
int minPrice = prices[0]; // prices的前缀最小
for (int p: prices) {
ans = max(ans, p - minPrice);
minPrice = min(minPrice, p);
}
return ans;
}
/**
* 122. 买卖股票的最佳时机 II * 交易次数不限
* 相当于求一个离散数列的所有上升差分值和
* @param prices * @return */int maxProfit_2_1(vector<int>& prices) {
int ans = 0;
for (int i = 1; i < prices.size(); ++i) {
int d = prices[i] - prices[i-1];
ans += d > 0 ? d :0;
}
return ans;
}
/**
* 122. 买卖股票的最佳时机 II * 交易次数不限
* 状态机DP解法
* @param prices * @return */int maxProfit_2_2(vector<int>& prices) {
// prices[i]表示第i天的股价，i从0开始
// 这里的股票，把它看成是一件物品更好理解。如果你以5块钱买下这件物品，明天以8块钱卖出，那么你就赚了3块钱。
int f0 = 0, f1 = INT_MIN; // f0表示【不持有】这件物品，此时你的利润。f1表示【持有】这件物品，此时你的利润
// 为了考虑边界情况，我们让第-1天的股价为inf
// 这里也是采用元素迭代法，迭代每日的价格，更新f0,f1。
for (int p: prices) {
int pre_f0 = f0, pre_f1 = f1;
/*
* 考虑今天是否要继续持有这件物品。
* - 不持有：
* - 昨天也不持有：f0 = pre_f0
* - 昨天持有（今天卖出）：f0 = pre_f1 + p
* 两者取max
* - 持有：
* - 昨天不持有（买入）：f1 = pre_f0 - p
* - 昨天持有：f1 = pre_f1
* 两者还是取max
*/ f0 = max(pre_f0, pre_f1 + p),
f1 = max(pre_f0 - p, pre_f1);
}
return f0;
}
/**
* 188. 买卖股票的最佳时机 IV * @param k 最多交易k笔
* @param prices 每日价格
* @return 最大利润
*/int maxProfit(int k, vector<int>& prices) {
// 【注意】买入+卖出算一笔交易。
int n = prices.size();
if (n == 0 || k == 0) return 0;
// 特殊情况：如果 k >= n/2，相当于无限次交易
if (k >= n/2) return maxProfit(prices);
vector<array<int, 2> > f(k+2, {INT_MIN / 2, INT_MIN / 2}); // f[j][0/1] 表示第j笔交易，不持有（卖出）/持有（买入）可以获得的最大利润(积累的最大财富)
// 初始，将每笔交易，卖出状态的利润设为0，买入状态的理论设为-inf（和之前一样，假设第0天的市场价是inf，这时候最优的选择是第0天不买入）
for (int j = 1; j <= k+1; ++j) {
f[j][0] = 0;
}
// 还是用元素迭代法，迭代每日价格，更新利润
for (int p: prices) {
// 采用倒序遍历
// 这里是因为同一天之内进行一次买入卖出，因此采用倒序遍历法防止过分累加
for (int j = k + 1; j > 0; --j) {
// 第j笔交易，卖出的利润就是 $当天的价格 - 上一次买入的价格$ => $第j笔买入时积累的财富 + p$， 即 $f[j][1] + p$。
// 第j笔交易，买入，这时候积累的财富就是 $上笔交易卖出时积累的财富 - 当天的价格$ => $第j-1笔买出时积累的财富 - p$， 即 $f[j-1][0] - p$。
// 每次迭代更新都要自比较一次
f[j][0] = max(f[j][0], f[j][1] + p); // 卖出
f[j][1] = max(f[j][1], f[j-1][0] - p); // 买入
}
}
return f[k+1][0];
}
区间DP
方法一：梅丽DP枚举法：枚举一个端点，通过枚举另一个端点得到这个端点内所有的子区间，扩展区间从而实现全部枚举。
/**
* 516. 最长回文子序列 的长度
* @param s
* @return
* */
int longestPalindromeSubseq(string s) {
int n = (int) s.size();
vector f(n, vector(n, 0));
// 倒序枚举区间左端点
for (int i = n-1; i >= 0; --i) {
f[i][i] = 1;
// 枚举区间右端点
for (int j = i + 1; j < n; ++j) {
// 合并区间
f[i][j] = (s[i] == s[j] ? f[i+1][j-1] + 2 : max(f[i+1][j], f[i][j-1]));
}
}
// 为什么要倒序枚举？因为我们要求区间长度为len的答案时，必须求他它的所有区间长度为len-1的答案。
// 因此其实也可以用：枚举右端点j -> 枚举左端点[0..j-1]
return f[0][n-1];
}
或
方法二：克罗多枚举法：枚举区间长度，扩展区间长度，从而实现全部枚举。
int longestPalindromeSubseq(const string &s) {
int n = s.length();
int dp[n][n];
memset(dp, 0, sizeof(dp));
// 单个字符本身就是回文
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 逐步扩展子串长度
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1]; // 求整个字符串的最长回文子序列
}
图论
拓扑排序
vector<int> topologicalSort(const vector<vector<bool>> &adjMatrix/*邻接矩阵*/) {
size_t n = adjMatrix.size();
vector<int> inDegree(n, 0);
vector<int> result;
// 计算每个节点的入度
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (adjMatrix[i][j] != 0) {
++inDegree[j];
}
}
}
// 使用队列存储入度为0的节点
queue<int> zeroInDegree;
for (int i = 0; i < n; ++i) {
if (inDegree[i] == 0) zeroInDegree.push(i);
}
// 开始拓扑排序
while (!zeroInDegree.empty()) {
int node = zeroInDegree.front();
zeroInDegree.pop();
result.push_back(node);
// 遍历当前节点的所有邻居
for (int j= 0; j < n; ++j) {
// 断开和邻居的边
if (adjMatrix[node][j] != 0) {
--inDegree[j];
// 将入度为0的邻居添加到队列中。
if (inDegree[j] == 0) zeroInDegree.push(j);
}
}
}
// 如果排序结果的大小不等于节点数，说明图中存在环，无法拓扑排序
if (result.size() != n) {
dbg("ring!")
return {};
}
return result;
}
/**
* 拓扑排序
* @param edges 边合集
* @param numNodes * @return
*/
std::vector<int> topologicalSort(const std::vector<std::vector<int>>& edges, int numNodes) {
// 构建邻接表和入度表
std::vector<std::vector<int>> adjList(numNodes);
std::vector<int> inDegree(numNodes, 0);
for (const auto& edge : edges) {
int u = edge[0];
int v = edge[1];
adjList[u].push_back(v);
inDegree[v]++;
}
// 使用队列存储入度为 0 的节点
std::queue<int> zeroInDegree;
for (int i = 0; i < numNodes; ++i) {
if (inDegree[i] == 0) {
zeroInDegree.push(i);
}
}
// 结果存储拓扑排序
std::vector<int> topoOrder;
while (!zeroInDegree.empty()) {
int node = zeroInDegree.front();
zeroInDegree.pop();
topoOrder.push_back(node);
// 遍历邻居节点，减少入度
for (int neighbor : adjList[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
zeroInDegree.push(neighbor);
}
}
}
// 如果结果中的节点数不等于图中的节点数，说明有环
if (topoOrder.size() != numNodes) {
throw std::runtime_error("The graph contains a cycle and cannot be topologically sorted.");
}
return topoOrder;
}
Dijkstra算法函数
/**
* Dijkstra算法函数
* @param adjList 邻接表
* @param start 起点
*/
void dijkstra(const vector<vector<pII>>& adjList, int start) {
/*
* dijkstra算法本质上就是一个 最短距离（离起点最近的节点）优先搜索算法。
*/
int vertices = (int)adjList.size(); // @param vertices 顶点数
vecI dist(vertices, INT_MAX);
dist[start] = 0; // 起点到起点的距离是0
// 优先队列（最小堆），按距离从小到大排序。
priority_queue<pII, vector<pII>, greater<> > pq; // @element {a,b} 表示b点到起点的最短距离为a。
pq.emplace(0, start); //添加起点到搜索队列
while (!pq.empty()) {
// 取出当前距离最小的点x，以及它到起点的距离d
int x = pq.top().second, d = pq.top().first;
pq.pop();
if (d > dist[x]) continue;
for (auto &edge: adjList[x]) { // 遍历x的邻居
int y = edge.first, distXY = edge.second;
if (dist[x] + distXY < dist[y]) { // 如果通过x点和这条边edge到达y点，比之前到达y点的方法距离更短，则更新
dist[y] = dist[x] + distXY;
pq.emplace(dist[y], y);
}
}
}
// 输出每个点的最短距离
for (int i = 0; i < vertices; i++) {
if (dist[i] == INT_MAX) {
cout << "从点 " << start << " 到点 " << i << " 无法到达" << endl;
} else {
cout << "从点 " << start << " 到点 " << i << " 的最短距离为: " << dist[i] << endl;
}
}
}
int _test_dijkstra() {
int vertices, edges;
cout << "请输入图的顶点数和边数: ";
cin >> vertices >> edges;
// 邻接表表示图
vector<vector<pII> > adjList(vertices);
cout << "请输入每条边的信息 (起点, 终点, 权重):" << endl;
for (int i = 0; i < edges; i++) {
int u, v, w;
cin >> u >> v >> w;
adjList[u].push_back({v, w});
adjList[v].push_back({u, w}); // 无向图，注释掉这行用于有向图
}
int start;
cout << "请输入起始顶点: ";
cin >> start;
dijkstra(adjList, start);
return status.OK;
}
Floyd-Warshall
/**
* Floyd-Warshall算法
* @param n 结点数（结点从0开始）
* @param dist 带权邻接矩阵，也是最终结果查询数组。这里是原地修改。
*/void floydWarshall(const int n, vector<vector<int> > &dist) {
const int INF = INT_MAX >> 1;
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// 如果通过k能使i到j的路径更短，则更新dist[i][j]
if (dist[i][k] != INF and dist[k][j] != INF and dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
cout << "最短路径矩阵:" << endl;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][j] == INF) {
cout << "INF ";
} else {
cout << dist[i][j] << " ";
}
}
cout << endl;
}
}
最小生成树之Kruskal 算法（一般用于稀疏图）
Kruskal 算法是一种用于求解最小生成树（MST, Minimum Spanning Tree）的问题的经典算法，它采用贪心策略，基本思想是每次选择权重最小的边，并且该边不会形成回路。算法使用并查集（Union-Find）数据结构来检测是否会形成回路。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边结构体
struct Edge {
int u, v, weight;
// 重载运算符，按边的权重排序
bool operator<(const Edge &e) const {
return weight < e.weight;
}
};
// 并查集结构体
struct DisjointSet {
vector<int> parent, rank;
DisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找根节点，路径压缩
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个集合，按秩合并
bool unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
};
// Kruskal 算法
int kruskal(int n, vector<Edge> &edges) {
// 1. 对所有边按权重进行排序
sort(edges.begin(), edges.end());
DisjointSet ds(n);
int mstWeight = 0;
// 2. 遍历所有边，选择不形成回路的边
for (const Edge &e : edges) {
if (ds.unionSets(e.u, e.v)) {
mstWeight += e.weight; // 加入到最小生成树
}
}
return mstWeight;
}
int main() {
int n, m;
cout << "Enter number of nodes and edges: ";
cin >> n >> m;
vector<Edge> edges(m);
cout << "Enter the edges (u, v, weight):\n";
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].weight;
}
int mstWeight = kruskal(n, edges);
cout << "Weight of Minimum Spanning Tree: " << mstWeight << endl;
return 0;
}
Enter number of nodes and edges: 4 5
Enter the edges (u, v, weight):
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4
Weight of Minimum Spanning Tree: 19
最小生成数之 Prim 算法（一般用于稠密图）
Prim 算法也是求解最小生成树（MST）的经典算法之一。与 Kruskal 算法不同，Prim 算法是从一个起始点出发，逐步扩展生成树的边，每次选择权重最小的边，将该边加入到生成树中，并连接新的顶点。它使用优先队列（通常是最小堆）来高效地选择最小权重的边。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 边结构体
struct Edge {
int to, weight;
// 构造函数
Edge(int t, int w) : to(t), weight(w) {}
// 重载运算符，用于优先队列按边的权重排序
bool operator>(const Edge& e) const {
return weight > e.weight;
}
};
// Prim 算法
int prim(int n, const vector<vector<Edge>>& graph) {
vector<bool> inMST(n, false); // 记录每个节点是否已被加入生成树
priority_queue<Edge, vector<Edge>, greater<Edge>> pq; // 最小堆，按边权重升序排列
int mstWeight = 0;
// 从第一个节点开始
pq.push(Edge(0, 0)); // 初始节点的权重为 0
while (!pq.empty()) {
Edge e = pq.top();
pq.pop();
int u = e.to;
// 如果节点 u 已在生成树中，跳过
if (inMST[u]) continue;
// 将节点 u 加入生成树
inMST[u] = true;
mstWeight += e.weight;
// 遍历 u 的邻接边
for (const Edge& next : graph[u]) {
if (!inMST[next.to]) { // 如果邻接点不在生成树中，加入优先队列
pq.push(next);
}
}
}
return mstWeight;
}
int main() {
int n, m;
cout << "Enter number of nodes and edges: ";
cin >> n >> m;
// 邻接表表示图
vector<vector<Edge>> graph(n);
cout << "Enter the edges (u, v, weight):\n";
for (int i = 0; i < m; i++) {
int u, v, weight;
cin >> u >> v >> weight;
graph[u].push_back(Edge(v, weight));
graph[v].push_back(Edge(u, weight)); // 无向图，双向加边
}
int mstWeight = prim(n, graph);
cout << "Weight of Minimum Spanning Tree: " << mstWeight << endl;
return 0;
}
欧拉路径
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class EulerianPath {
private:
int V; // 顶点数
vector<vector<int>> adj; // 邻接表
vector<int> degree; // 记录度数
vector<vector<bool>> visited; // 记录边是否被访问
public:
EulerianPath(int vertices) : V(vertices), adj(vertices), degree(vertices, 0), visited(vertices, vector<bool>(vertices, false)) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
degree[u]++;
degree[v]++;
}
bool isEulerianPath() {
int oddCount = 0;
for (int i = 0; i < V; i++) {
if (degree[i] % 2 == 1) oddCount++;
}
return (oddCount == 0 || oddCount == 2);
}
void findEulerianPath() {
if (!isEulerianPath()) {
cout << "此图无欧拉路径！" << endl;
return;
}
int start = 0;
for (int i = 0; i < V; i++) {
if (degree[i] % 2 == 1) { // 找到奇度点作为起点
start = i;
break;
}
}
stack<int> stk;
vector<int> path;
stk.push(start);
while (!stk.empty()) {
int u = stk.top();
bool found = false;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (!visited[u][v]) {
visited[u][v] = visited[v][u] = true;
stk.push(v);
found = true;
break;
}
}
if (!found) {
path.push_back(u);
stk.pop();
}
}
cout << "欧拉路径：";
for (int i = path.size() - 1; i >= 0; i--) {
cout << path[i] << (i == 0 ? "\n" : " -> ");
}
}
};
int main() {
EulerianPath graph(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(1, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 1);
graph.findEulerianPath();
return 0;
}
欧拉密码字典
class ODic {
private:
unordered_set<int> seen;
string ans;
ll highest;
int k;
public:
void dfs(int node) {
for (int x = 0; x < k; ++x) {
int nei = node * 26 + x;
if (!seen.count(nei)) {
seen.insert(nei);
dfs(nei % highest);
ans += (x + 'a');
}
}
}
string gen(int n, int k) {
highest = pow(26, n - 1);
this->k = k;
dfs(0);
ans += string(n - 1, 'a');
return ans;
}
};
class Solution {
private:
unordered_set<int> seen;
string ans;
int highest;
int k;
public:
void dfs(int node) {
for (int x = 0; x < k; ++x) {
int nei = node * 10 + x;
if (!seen.count(nei)) {
seen.insert(nei);
dfs(nei % highest);
ans += (x + '0');
}
}
}
string crackSafe(int n, int k) {
highest = pow(10, n - 1);
this->k = k;
dfs(0);
ans += string(n - 1, '0');
return ans;
}
};
数论
bool is_prime(int n) {
if (n == 2) return true;
if (!(n&1)) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
return false;
}
}
return n > 2;
}
快速幂
#include <iostream>
long long qpow_iterative(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2) result = (result * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return result;
}
int main() {
long long base = 2, exp = 10, mod = 1000000007;
std::cout << "2^10 % 1000000007 = " << qpow_iterative(base, exp, mod) << std::endl;
return 0;
}
埃拉托斯特尼筛法
// 埃拉托斯特尼筛法，生成所有不超过 n 的素数
vector<int> getPrimes(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if(isPrime[i])
for (int j = i * i; j <= n; j += i)
isPrime[j] = false;
}
vector<int> primes;
for (int i = 2; i <= n; i++) {
if(isPrime[i]) {
primes.push_back(i);
}
}
return primes;
}
const int MX = 1e6;
vector<int> primes;
int init = []() {
bool np[MX + 1]{};
for (int i = 2; i <= MX; ++i) {
if (!np[i]) primes.push_back(i);
for (int p: primes) {
if (i * p > MX) break;
np[i * p] = true;
if (i % p == 0) break;
}
}
primes.push_back(MX + 1);
primes.push_back(MX + 1); // 保证下面下标不会越界
return 0;
}();
回文素数库
nums=[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001, 1008001, 1022201, 1028201, 1035301, 1043401, 1055501, 1062601, 1065601, 1074701, 1082801, 1085801, 1092901, 1093901, 1114111, 1117111, 1120211, 1123211, 1126211, 1129211, 1134311, 1145411, 1150511, 1153511, 1160611, 1163611, 1175711, 1177711, 1178711, 1180811, 1183811, 1186811, 1190911, 1193911, 1196911, 1201021, 1208021, 1212121, 1215121, 1218121, 1221221, 1235321, 1242421, 1243421, 1245421, 1250521, 1253521, 1257521, 1262621, 1268621, 1273721, 1276721, 1278721, 1280821, 1281821, 1286821, 1287821, 1300031, 1303031, 1311131, 1317131, 1327231, 1328231, 1333331, 1335331, 1338331, 1343431, 1360631, 1362631, 1363631, 1371731, 1374731, 1390931, 1407041, 1409041, 1411141, 1412141, 1422241, 1437341, 1444441, 1447441, 1452541, 1456541, 1461641, 1463641, 1464641, 1469641, 1486841, 1489841, 1490941, 1496941, 1508051, 1513151, 1520251, 1532351, 1535351, 1542451, 1548451, 1550551, 1551551, 1556551, 1557551, 1565651, 1572751, 1579751, 1580851, 1583851, 1589851, 1594951, 1597951, 1598951, 1600061, 1609061, 1611161, 1616161, 1628261, 1630361, 1633361, 1640461, 1643461, 1646461, 1654561, 1657561, 1658561, 1660661, 1670761, 1684861, 1685861, 1688861, 1695961, 1703071, 1707071, 1712171, 1714171, 1730371, 1734371, 1737371, 1748471, 1755571, 1761671, 1764671, 1777771, 1793971, 1802081, 1805081, 1820281, 1823281, 1824281, 1826281, 1829281, 1831381, 1832381, 1842481, 1851581, 1853581, 1856581, 1865681, 1876781, 1878781, 1879781, 1880881, 1881881, 1883881, 1884881, 1895981, 1903091, 1908091, 1909091, 1917191, 1924291, 1930391, 1936391, 1941491, 1951591, 1952591, 1957591, 1958591, 1963691, 1968691, 1969691, 1970791, 1976791, 1981891, 1982891, 1984891, 1987891, 1988891, 1993991, 1995991, 1998991, 3001003, 3002003, 3007003, 3016103, 3026203, 3064603, 3065603, 3072703, 3073703, 3075703, 3083803, 3089803, 3091903, 3095903, 3103013, 3106013, 3127213, 3135313, 3140413, 3155513, 3158513, 3160613, 3166613, 3181813, 3187813, 3193913, 3196913, 3198913, 3211123, 3212123, 3218123, 3222223, 3223223, 3228223, 3233323, 3236323, 3241423, 3245423, 3252523, 3256523, 3258523, 3260623, 3267623, 3272723, 3283823, 3285823, 3286823, 3288823, 3291923, 3293923, 3304033, 3305033, 3307033, 3310133, 3315133, 3319133, 3321233, 3329233, 3331333, 3337333, 3343433, 3353533, 3362633, 3364633, 3365633, 3368633, 3380833, 3391933, 3392933, 3400043, 3411143, 3417143, 3424243, 3425243, 3427243, 3439343, 3441443, 3443443, 3444443, 3447443, 3449443, 3452543, 3460643, 3466643, 3470743, 3479743, 3485843, 3487843, 3503053, 3515153, 3517153, 3528253, 3541453, 3553553, 3558553, 3563653, 3569653, 3586853, 3589853, 3590953, 3591953, 3594953, 3601063, 3607063, 3618163, 3621263, 3627263, 3635363, 3643463, 3646463, 3670763, 3673763, 3680863, 3689863, 3698963, 3708073, 3709073, 3716173, 3717173, 3721273, 3722273, 3728273, 3732373, 3743473, 3746473, 3762673, 3763673, 3765673, 3768673, 3769673, 3773773, 3774773, 3781873, 3784873, 3792973, 3793973, 3799973, 3804083, 3806083, 3812183, 3814183, 3826283, 3829283, 3836383, 3842483, 3853583, 3858583, 3863683, 3864683, 3867683, 3869683, 3871783, 3878783, 3893983, 3899983, 3913193, 3916193, 3918193, 3924293, 3927293, 3931393, 3938393, 3942493, 3946493, 3948493, 3964693, 3970793, 3983893, 3991993, 3994993, 3997993, 3998993, 7014107, 7035307, 7036307, 7041407, 7046407, 7057507, 7065607, 7069607, 7073707, 7079707, 7082807, 7084807, 7087807, 7093907, 7096907, 7100017, 7114117, 7115117, 7118117, 7129217, 7134317, 7136317, 7141417, 7145417, 7155517, 7156517, 7158517, 7159517, 7177717, 7190917, 7194917, 7215127, 7226227, 7246427, 7249427, 7250527, 7256527, 7257527, 7261627, 7267627, 7276727, 7278727, 7291927, 7300037, 7302037, 7310137, 7314137, 7324237, 7327237, 7347437, 7352537, 7354537, 7362637, 7365637, 7381837, 7388837, 7392937, 7401047, 7403047, 7409047, 7415147, 7434347, 7436347, 7439347, 7452547, 7461647, 7466647, 7472747, 7475747, 7485847, 7486847, 7489847, 7493947, 7507057, 7508057, 7518157, 7519157, 7521257, 7527257, 7540457, 7562657, 7564657, 7576757, 7586857, 7592957, 7594957, 7600067, 7611167, 7619167, 7622267, 7630367, 7632367, 7644467, 7654567, 7662667, 7665667, 7666667, 7668667, 7669667, 7674767, 7681867, 7690967, 7693967, 7696967, 7715177, 7718177, 7722277, 7729277, 7733377, 7742477, 7747477, 7750577, 7758577, 7764677, 7772777, 7774777, 7778777, 7782877, 7783877, 7791977, 7794977, 7807087, 7819187, 7820287, 7821287, 7831387, 7832387, 7838387, 7843487, 7850587, 7856587, 7865687, 7867687, 7868687, 7873787, 7884887, 7891987, 7897987, 7913197, 7916197, 7930397, 7933397, 7935397, 7938397, 7941497, 7943497, 7949497, 7957597, 7958597, 7960697, 7977797, 7984897, 7985897, 7987897, 7996997, 9002009, 9015109, 9024209, 9037309, 9042409, 9043409, 9045409, 9046409, 9049409, 9067609, 9073709, 9076709, 9078709, 9091909, 9095909, 9103019, 9109019, 9110119, 9127219, 9128219, 9136319, 9149419, 9169619, 9173719, 9174719, 9179719, 9185819, 9196919, 9199919, 9200029, 9209029, 9212129, 9217129, 9222229, 9223229, 9230329, 9231329, 9255529, 9269629, 9271729, 9277729, 9280829, 9286829, 9289829, 9318139, 9320239, 9324239, 9329239, 9332339, 9338339, 9351539, 9357539, 9375739, 9384839, 9397939, 9400049, 9414149, 9419149, 9433349, 9439349, 9440449, 9446449, 9451549, 9470749, 9477749, 9492949, 9493949, 9495949, 9504059, 9514159, 9526259, 9529259, 9547459, 9556559, 9558559, 9561659, 9577759, 9583859, 9585859, 9586859, 9601069, 9602069, 9604069, 9610169, 9620269, 9624269, 9626269, 9632369, 9634369, 9645469, 9650569, 9657569, 9670769, 9686869, 9700079, 9709079, 9711179, 9714179, 9724279, 9727279, 9732379, 9733379, 9743479, 9749479, 9752579, 9754579, 9758579, 9762679, 9770779, 9776779, 9779779, 9781879, 9782879, 9787879, 9788879, 9795979, 9801089, 9807089, 9809089, 9817189, 9818189, 9820289, 9822289, 9836389, 9837389, 9845489, 9852589, 9871789, 9888889, 9889889, 9896989, 9902099, 9907099, 9908099, 9916199, 9918199, 9919199, 9921299, 9923299, 9926299, 9927299, 9931399, 9932399, 9935399, 9938399, 9957599, 9965699, 9978799, 9980899, 9981899, 9989899, 100030001, 100050001, 100060001, 100111001, 100131001, 100161001, 100404001, 100656001, 100707001, 100767001, 100888001, 100999001, 101030101, 101060101, 101141101, 101171101, 101282101, 101292101, 101343101, 101373101, 101414101, 101424101, 101474101, 101595101, 101616101, 101717101, 101777101, 101838101, 101898101, 101919101, 101949101, 101999101, 102040201, 102070201, 102202201, 102232201, 102272201, 102343201, 102383201, 102454201, 102484201, 102515201, 102676201, 102686201, 102707201, 102808201, 102838201, 103000301, 103060301, 103161301, 103212301, 103282301, 103303301, 103323301, 103333301, 103363301, 103464301, 103515301, 103575301, 103696301, 103777301, 103818301, 103828301, 103909301, 103939301, 104000401, 104030401, 104040401, 104111401, 104222401, 104282401, 104333401, 104585401, 104616401, 104787401, 104838401, 104919401, 104949401, 105121501, 105191501, 105202501, 105262501, 105272501, 105313501, 105323501, 105343501, 105575501, 105616501, 105656501, 105757501, 105818501, 105868501, 105929501, 106060601, 106111601, 106131601]
gcd()
C++自带的gcd
#include <numeric>
using namespace std;
gcd(a,b);
递归写法的cgd
int my_gcd(int a, int b) {
if (!b) return a;
if (a % b) return my_gcd(b, a % b);
return b;
}
非递归
int my_gcd(int a, int b) {
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
扩展gcd()
#include <iostream>
// 扩展欧几里得算法
// 计算 ax + by = gcd(a, b) 的解 (x, y)
int extended_gcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a; // gcd(a, 0) = a
}
int x1, y1;
int gcd = extended_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return gcd;
}
int main() {
int a, b, x, y;
std::cout << "输入两个整数 a 和 b: ";
std::cin >> a >> b;
int gcd = extended_gcd(a, b, x, y);
std::cout << "gcd(" << a << ", " << b << ") = " << gcd << std::endl;
std::cout << "系数 x = " << x << ", y = " << y << std::endl;
return 0;
}
Lucas定理
#include <iostream>
#include <vector>
using namespace std;
// 扩展欧几里得算法，求模逆元
int mod_inverse(int a, int m) {
int m0 = m, t, q;
int x0 = 0, x1 = 1;
if (m == 1) return 0;
while (a > 1) {
// q是商，t是余数
q = a / m;
t = m;
// m是余数
m = a % m;
a = t;
// 更新x0和x1
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
// 使得x1成为正数
if (x1 < 0) x1 += m0;
return x1;
}
// 计算n! % p
int factorial_mod(int n, int p) {
int result = 1;
for (int i = 2; i <= n; ++i) {
result = (result * i) % p;
}
return result;
}
// 计算C(n, k) % p
int binomial_mod(int n, int k, int p) {
if (k > n) return 0;
// 计算n! % p, k! % p 和 (n-k)! % p
int numerator = factorial_mod(n, p);
int denominator = (factorial_mod(k, p) * factorial_mod(n - k, p)) % p;
// 使用模逆元
int denominator_inv = mod_inverse(denominator, p);
return (numerator * denominator_inv) % p;
}
// 根据卢卡斯定理计算C(n, k) % p
int lucas_theorem(int n, int k, int p) {
int result = 1;
// 使用卢卡斯定理：将n和k表示成p进制
while (n > 0 || k > 0) {
int n_i = n % p;
int k_i = k % p;
// 计算 C(n_i, k_i) % p
result = (result * binomial_mod(n_i, k_i, p)) % p;
// 更新n和k
n /= p;
k /= p;
}
return result;
}
int main() {
int n, k, p;
cout << "Enter n, k, and p (prime): ";
cin >> n >> k >> p;
int result = lucas_theorem(n, k, p);
cout << "C(" << n << ", " << k << ") mod " << p << " = " << result << endl;
return 0;
}
费马定理
求1的逆元
在模 ppp 意义下求整数 aaa 的逆元（即找到 x 使得 $a \times x ≡ 1 (mod .p)$），通常有两种方法：
- 扩展欧几里得算法（适用于一般模数）
- 费马小定理（适用于模数是质数的情况）
方法 1：扩展欧几里得算法求逆元
适用于任意模 p，但要求 a 与 p 互质（即 $gcd(a,p)=1$）。
#include <iostream>
// 扩展欧几里得算法
long long exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
long long x1, y1;
long long g = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
// 求 a 在 mod p 下的逆元
long long mod_inv(long long a, long long p) {
long long x, y;
long long g = exgcd(a, p, x, y);
if (g != 1) {
std::cerr << "无解，逆元不存在\n";
return -1;
}
return (x % p + p) % p; // 确保结果非负
}
int main() {
long long a, p;
std::cout << "输入 a 和 p (p 需要是一个正整数): ";
std::cin >> a >> p;
long long inv = mod_inv(a, p);
if (inv != -1)
std::cout << "逆元: " << inv << std::endl;
return 0;
}
方法 2：费马小定理
适用于模 p 为 质数 的情况，根据费马小定理：
#include <iostream>
// 快速幂计算 (a^b) % mod
long long fast_pow(long long a, long long b, long long mod) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
// 费马小定理求逆元 (仅适用于 p 为质数)
long long mod_inv(long long a, long long p) {
return fast_pow(a, p - 2, p);
}
int main() {
long long a, p;
std::cout << "输入 a 和 p (p 必须是质数): ";
std::cin >> a >> p;
std::cout << "逆元: " << mod_inv(a, p) << std::endl;
return 0;
}
求 $\frac{b}{a}%m$
#include <iostream>
// 扩展欧几里得算法求 ax + by = gcd(a, b) 的整数解 (x, y)
long long exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
long long x1, y1;
long long g = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
// 求解 ax ≡ b (mod p)
bool solve_mod_equation(long long a, long long b, long long p, long long &x) {
long long x0, y;
long long g = exgcd(a, p, x0, y); // 求 a 关于 p 的逆元
if (b % g != 0) { // 若 b 不是 gcd(a, p) 的倍数，则无解
return false;
}
// 计算 x0 * (b / g) 模 (p / g)
x = ((x0 * (b / g)) % (p / g) + (p / g)) % (p / g);
return true;
}
int main() {
long long a, b, p, x;
std::cout << "输入 a, b, p: ";
std::cin >> a >> b >> p;
if (solve_mod_equation(a, b, p, x)) {
std::cout << "方程的最小正整数解: " << x << std::endl;
} else {
std::cout << "无解\n";
}
return 0;
}
当模数 ppp 为质数且 gcd(a,p)=1时，可以使用费马小定理结合快速幂来求解方程：
#include <iostream>
// 快速幂计算 (a^b) % mod
long long fast_pow(long long a, long long b, long long mod) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod; // 如果当前位为1
a = a * a % mod; // 平方底数
b >>= 1; // 移位
}
return res;
}
// 使用快速幂求解 ax ≡ b (mod p)
long long solve_mod_equation(long long a, long long b, long long p) {
long long inv_a = fast_pow(a, p - 2, p); // 计算 a^(-1) mod p
return (b * inv_a) % p; // 计算 x ≡ b * a^(-1) (mod p)
}
int main() {
long long a, b, p;
std::cout << "输入 a, b, p (p 必须是质数): ";
std::cin >> a >> b >> p;
if (std::__gcd(a, p) != 1) { // 确保 a 在 mod p 下有逆元
std::cout << "无解（a 和 p 不是互质的）\n";
return 0;
}
long long x = solve_mod_equation(a, b, p);
std::cout << "方程的最小正整数解: " << x << std::endl;
return 0;
}
串
KMP
KMP算法用于在一个文本中寻找一个模式串的位置。它通过预处理模式串来避免匹配失败时的回溯，从而提升搜索效率。
#include <iostream>
#include <vector>
#include <string>
// 计算部分匹配表（也叫前缀表）
std::vector<int> computePrefixFunction(const std::string& pattern) {
int m = pattern.length();
std::vector<int> prefix(m, 0);
int j = 0; // 记录前缀的长度
for (int i = 1; i < m; ++i) {
// 匹配失败时回溯
while (j > 0 && pattern[i] != pattern[j]) {
j = prefix[j - 1];
}
if (pattern[i] == pattern[j]) {
++j;
}
prefix[i] = j;
}
return prefix;
}
// KMP算法进行模式匹配
int KMP(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
if (m == 0) return 0; // 空模式串的特殊情况
std::vector<int> prefix = computePrefixFunction(pattern);
int j = 0; // 用于模式串的匹配
for (int i = 0; i < n; ++i) {
// 匹配失败时回溯
while (j > 0 && text[i] != pattern[j]) {
j = prefix[j - 1];
}
if (text[i] == pattern[j]) {
++j;
}
// 完全匹配时返回匹配的起始位置
if (j == m) {
return i - m + 1; // 匹配成功，返回起始位置
}
}
return -1; // 匹配失败
}
int main() {
std::string text, pattern;
std::cout << "Enter the text: ";
std::cin >> text;
std::cout << "Enter the pattern: ";
std::cin >> pattern;
int position = KMP(text, pattern);
if (position != -1) {
std::cout << "Pattern found at index " << position << std::endl;
} else {
std::cout << "Pattern not found" << std::endl;
}
return 0;
}
/**
* KMP算法
* @param text 文本字符串
* @param pattern 要匹配的字符串
* @return 下标位置
*/
int kmp(const string &text, const string &pattern) {
int m = (int) pattern.length();
if (m == 0) return 0; // 空模式串的特殊情况
/*
* 计算部分匹配表（前缀表）
* 即首先需要获取一个查询数组prefix，代表pattern前i个字符组成的字符串它的最长相同前后缀 的长度。
* 例如 pattern="ABXABM"，那么prefix[3]=1, prefix[4]=2。
* 这个过程其实直接暴力计算也无妨，但是这里还是做了小优化。这里用的是对称映射法。
* j是前缀的长度，在这里可以作为最长相同前后缀下标，也可以作为最长相同前后缀的长度。
* 规定：对于像pattern="AAAA", prefix = [0,1,2,3]，此时j=3。因为规定这里的前后缀是不包括本身的。
* 如果"AAAAB"，此时patter[i] != pattern[j]，考虑前一个前缀（即前缀长度减一），...，最终prefix = [0,1,2,0]
* 如果"AAAABA"，上一个最长前后缀长度是0，这个字符如果和patter[0]相等，那么这里的最长前缀长度为0+1=1，
* 也就是说如果上一个最长前后缀长度是r，其实只要看这个字符串和pattern[r]是否相等就可以了。因为我们是要计算的是前后缀，不是回文，像"ABCXABC",patter[6]=3
*/
vecI prefix(m, 0); // 计算部分匹配表（前缀表）
int j = 0; // 记录前缀的长度
for (int i = 1; i < m; ++i) {
// 匹配失败时回溯
while (j > 0 and pattern[i] != pattern[j]) j = prefix[j - 1];
// 匹配相等长度是上一个+1
if (pattern[i] == pattern[j]) prefix[i] = ++j;
}
// prefix;
/* * KMP算法进行模式匹配
*/ int n = (int)text.length();
j = 0; // 匹配相等的长度
for (int i = 0; i < n; ++i) {
/*
* 匹配失败时回溯
* 这时候pattern的最长相等前后缀查询数组就可以用于跳过pattern中的下标
* 例如text="XXABCDABXXXX", pattern="ABCDABD",当匹配到text[8]!=pattern[6]时，发现prefix[5]=2,于是就可以从text[9]?=pattern[2]开始比较
* */ while (j > 0 && text[i] != pattern[j]) j = prefix[j - 1];
if (text[i] == pattern[j]) ++j;
if (j == m) return i - m + 1;
}
return -1; // 匹配失败
}
Z函数
Z[i]表示字符串 S 的后缀 S[i:]与 S 的最长公共前缀（LCP）的长度。
示例
字符串： S = "abacaba"
| 索引 i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
S[i] | a | b | a | c | a | b | a |
Z[i] | 7 | 0 | 1 | 0 | 3 | 0 | 1 |
vector<ll> compute_z(const string &s) {
size_t n = s.length();
vector<ll> z(n);
for (int i = 0, l = 0, r = 0; i < n; ++i) {
z[i] = max(min(z[i - l], r - i + 1ll), 0ll);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
l = i;
r = i + z[i];
++z[i];
}
}
return z;
}
回文子串
实现回文字串 查询数组
vector cost(n, vector(n, 0)); // cost[i][j] 表示将s[i..j]变为回文子串所需的操作次数，这里取的s下标是从0开始
for (int span = 2; span <= n; ++span) {
for (int i = 0; i <= n - span; ++i) {
int j = i + span - 1;
cost[i][j] = cost[i + 1][j - 1] + (s[i] != s[j]);
}
}
如果要查询s[i..j]是否是回文子串，只需cost[i][j] == 0
Manacher算法
Manacher 算法可以计算以 s[i]（或者s[i] 和 s[i+1]）为回文中心的最长回文子串的长度。
// 预处理字符串，插入分隔符 '#'，避免奇偶分类
string preprocess(const string &s) {
string t = "#";
for (char c : s) {
t += c;
t += "#";
}
return t;
}
// Manacher 算法求最长回文子串长度
int manacher(const string &s) {
string t = preprocess(s); // "babad" => "#b#a#b#a#d#"
int len = t.size();
vector<int> p(len, 0); // $p[i]+1$ 表示以 t[i] 为中心的回文半径
int center = 0, right = 0, maxLen = 0;
for (int i = 0; i < len; i++) {
int mirr = 2 * center - i; // i 关于 center 的对称点
if (i < right) {
p[i] = min(p[mirr], right - i);
}
// 尝试扩展回文
while (i - p[i] >= 0 && i + p[i] < len && t[i - p[i]] == t[i + p[i]]) {
p[i]++;
}
// 更新 center 和 right
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 记录最大回文长度
maxLen = max(maxLen, p[i] - 1);
}
return maxLen;
}
最长回文子序列（LPS）
#include <iostream>
#include <vector>
#include <string>
int longestPalindromeSubseq(const std::string& s) {
int n = s.size();
if (n == 0) return 0;
// dp[i][j] 表示 s[i...j] 的最长回文子序列长度
std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
// 初始化：单个字符的最长回文子序列长度为 1
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
}
// 逐步扩大子串长度
for (int len = 2; len <= n; ++len) { // len 是子串的长度
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = std::max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1]; // 整个字符串的最长回文子序列长度
}
int main() {
std::string s = "bbbab";
std::cout << "最长回文子序列长度: " << longestPalindromeSubseq(s) << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <string>
int longestPalindromeSubseq(const std::string& s) {
int n = s.size();
if (n == 0) return 0;
std::vector<int> prev(n, 0), curr(n, 0);
for (int i = n - 1; i >= 0; --i) {
curr[i] = 1; // 单个字符的回文子序列长度为 1
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
curr[j] = prev[j - 1] + 2;
} else {
curr[j] = std::max(prev[j], curr[j - 1]);
}
}
prev = curr; // 更新滚动数组
}
return curr[n - 1];
}
int main() {
std::string s = "bbbab";
std::cout << "最长回文子序列长度: " << longestPalindromeSubseq(s) << std::endl;
return 0;
}
字符串哈希
/**
* 长度为k的子串哈希
* @param s 字符串
* @param k 子串长度
* @return 所有长度为k的子串的哈希
*/vector<long long> getSubstrHash(const string& s, long long k) {
/*
* 这里使用的是 Rabin-Karp 滚动哈希 法 （基于定长滑动窗口法）
*/ const long long base = 13331; // or131 选择一个大质数作为哈希基数
const long long mod = 1e9 + 7; // 选择一个大素数取模，减少哈希冲突
vector<long long> substrHash;
long long hash = 0, power = 1;
if (s.size() < k) return substrHash; // 如果字符串长度小于 k，返回空数组
// 计算第一个长度为 k 的子串哈希值
for (long long i = 0; i < k; ++i) {
hash = (hash * base + s[i]) % mod;
if (i > 0) power = (power * base) % mod; // 预计算 base^(k-1) }
substrHash.push_back(hash);
// 滚动哈希计算后续子串的哈希值
for (long long i = k; i < s.size(); ++i) {
hash = (hash - s[i - k] * power % mod + mod) % mod; // 移除旧字符
hash = (hash * base + s[i]) % mod; // 添加新字符
substrHash.push_back(hash);
}
return substrHash;
}
int main() {
string s = "abcdefg";
long long k = 3;
vector<long long> hashes = getSubstrHash(s, k);
cout << "所有长度为 " << k << " 的子串哈希值:" << endl;
for (long long h : hashes) {
cout << h << " ";
}
cout << endl;
return 0;
}
/**
* 字符串哈希也是迭代哈希的一种。
* 对于字符串s其哈希迭代公式是:
* 首先需要给定一个哈希系数p和一个模值m。
* $sum(s[i] * (p ** i)) % m$ 。（p**i）是p的i次方
**/
class Solution {
public:
/**
* 2156. 查找给定哈希值的子串
* 找出s中第一个 长度为k，哈希值是hashValue的子串。
* 对于s[i]: 'a' = 1, 'b'=2, ...。i从0开始
* @param s * @param power 哈希系数p（幂次方系数）
* @param modulo 模值
* @param k * @param hashValue * @return */ string subStrHash(string s, int power, int modulo, int k, int hashValue) {
int n = (int) s.size();
// s[n-k..] 的哈希值，和 power ** k ll h = 0, pk = 1;
for (int i = n - k; i < n; ++i) {
h = (h + (s[i] - 'a' + 1) * pk) % modulo;
pk = pk * power % modulo;
}
int ans = h == hashValue ? n - k : -1;
// 向左滑窗
for (int i = n - k - 1; i >= 0; --i) {
// 细节：pk * (s[i + k] - 'a' + 1) 可能很大，超过模值，因此需要取模一下。
// 由于C++模是含符号的，因此就算是`(- pk * (s[i + k] - 'a' + 1)) % modulo`也是负数，需要使用补模法：$(x + modulo) % modulo$
// 这里的modulo < max_ll / 2 ,可以直接补模。如果不是的话要加一个if判断。
/*h = (h * power + (s[i] - 'a' + 1) - pk * (s[i + k] - 'a' + 1) % modulo);
h = (h < 0 ? h + modulo : h) % modulo;*/ h = (h * power + (s[i] - 'a' + 1) - pk * (s[i + k] - 'a' + 1) % modulo + modulo) % modulo;
if (h == hashValue) ans = i;
}
if (ans != -1) return s.substr(ans, k);
return "";
}
};
Trie
#include <iostream>
using namespace std;
struct TrieNode {
TrieNode* children[26]; // 假设只存储小写字母
bool isEndOfWord;
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
public:
Trie() { root = new TrieNode(); }
// 插入单词
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
// 查找单词
bool search(const string& word) {
TrieNode* node = findNode(word);
return node && node->isEndOfWord;
}
// 前缀匹配
// 和查询类似，但不要求匹配到单词结束标志，只需要匹配到前缀即可。
bool startsWith(const string& prefix) {
return findNode(prefix) != nullptr;
}
private:
TrieNode* root;
TrieNode* findNode(const string& prefix) {
TrieNode* node = root;
for (char c : prefix) {
int index = c - 'a';
if (!node->children[index]) return nullptr;
node = node->children[index];
}
return node;
}
};
int main() {
Trie trie;
trie.insert("apple");
cout << trie.search("apple") << endl; // 输出 1（存在）
cout << trie.search("app") << endl; // 输出 0（不存在）
cout << trie.startsWith("app") << endl; // 输出 1（前缀匹配成功）
trie.insert("app");
cout << trie.search("app") << endl; // 输出 1（插入后存在）
return 0;
}
高精度
大数 乘 小数
vector<int> mul(const vector<int> &v, int n) {
int _ = 0;
vector<int> ret;
for (int i : v) {
_ += i * n;
ret.push_back(_ % 10);
_ /= 10;
}
if (_ != 0) ret.push_back(_);
return ret;
}
自定义宏
struct PRINT {
PRINT operator, (const vector<int> &vec) {
cout << '[';
for (int i = 0; i < vec.size() - 1; ++i) {
cout << vec[i] << ' ';
}
cout << vec.back() << ']';
return *this;
}
PRINT operator, (auto n){
cout << n << ' ';
return *this;
}
}pt;
#define myPrintln(...) pt, ##__VA_ARGS__;cout << endl;
#define myPrint pt,
#define myPrintln(...) myPrint __VA_ARGS__,'\n';
using namespace std;
class PRINT{
private:
string sep = " ";
public:
PRINT operator, (int n){
cout << n << sep;
return *this;
}
PRINT operator, (char c){
cout << c << sep;
return *this;
}
PRINT operator, (const string &s){
cout << s << sep;
return *this;
}
PRINT operator, (double f){
cout << f << sep;
return *this;
}
}pt;
int main(){
int a=100;
double b = 500.165;
myPrintln(100, 10, 15, a, b)
// 100 10 15 100 500.165
return 0;
}
// #define int long long
#ifndef MOD
#define MOD 1e9+7
class Num {
private:
static const int mod = MOD;
int val = 0;
protected:
static inline int norm(int x) {
if (x < 0) {
int cnt = abs(x)/mod + 1;
x += mod*cnt;
}
return x%mod;
}
static int binPow(int base, int expo, int p) {
if (expo == 0) { // 防止 mod 1
return 1 % p;
}
base %= p;
int half = binPow(base, expo>>1, p);
if (expo & 1) {
return half*half%p * base%p;
} else {
return half*half%p;
}
}
public:
Num() {}
Num(int val):val(norm(val)) {}
Num(const Num& num) {
this->val = num.val;
}
~Num() {}
int getVal() {
return this->val;
}
void setVal(const int val) {
this->val = norm(val);
}
int& operator()() {
return this->val;
}
public:
friend std::istream& operator>>(std::istream& cin, Num& num) {
cin >> num.val;
num.val = num.norm(num.val);
return cin;
}
friend std::ostream& operator<<(std::ostream& cout, Num& num) {
cout << num.val;
return cout;
}
friend std::ostream& operator<<(std::ostream& cout, Num&& num) {
cout << num.val;
return cout;
}
public:
Num& operator+=(const Num& rhs) {
val = norm(val + rhs.val);
return *this;
}
Num& operator-=(const Num& rhs) {
val = norm(val - rhs.val);
return *this;
}
Num& operator*=(const Num& rhs) {
val = norm(val * rhs.val);
return *this;
}
Num& operator/=(const Num& rhs) {
int inverseElement = binPow(rhs.val, mod-2, mod);
val = norm(val * inverseElement);
return *this;
}
public:
Num operator+() {
Num tmp = val;
return tmp;
}
Num operator-() {
Num tmp = -val;
return tmp;
}
friend Num operator+(const Num& lhs, const Num& rhs) {
Num tmp = lhs;
tmp += rhs;
return tmp;
}
friend Num operator-(const Num& lhs, const Num& rhs) {
Num tmp = lhs;
tmp -= rhs;
return tmp;
}
friend Num operator*(const Num& lhs, const Num& rhs) {
Num tmp = lhs;
tmp *= rhs;
return tmp;
}
friend Num operator/(const Num& lhs, const Num& rhs) {
Num tmp = lhs;
tmp /= rhs;
return tmp;
}
public:
Num operator++(signed) { // 后置
Num tmp = *this;
val = norm(val+1);
return tmp;
}
Num operator--(signed) { // 后置
Num tmp = *this;
val = norm(val-1);
return tmp;
}
Num& operator++() { // 前置
val = norm(val+1);
return *this;
}
Num& operator--() { // 前置
val = norm(val-1);
return *this;
}
public:
bool operator!() const {
return val == 0;
}
bool operator==(const Num& rhs) const {
return val == rhs.val;
}
bool operator!=(const Num& rhs) const {
return val != rhs.val;
}
bool operator>(const Num& rhs) const {
return val > rhs.val;
}
bool operator>=(const Num& rhs) const {
return val >= rhs.val;
}
bool operator<(const Num& rhs) const {
return val < rhs.val;
}
bool operator<=(const Num& rhs) const {
return val <= rhs.val;
}
bool operator&&(const Num& rhs) const {
return val && rhs.val;
}
bool operator||(const Num& rhs) const {
return val || rhs.val;
}
};
#endif // MOD
