28 行代码C++算法模板
二分答案模板
二分答案竞赛模板,提供左边界(求最小可行解)与右边界(求最大可行解)两种写法
// 假设 check(mid) 在答案范围内具有单调性:
int l = 1, r = maxLen;
// 右边界型二分
while (l < r) {
int mid = (l + r + 1) / 2; // +1 防止死循环(当 l+1==r 时 mid==r)#二分#二分答案
二分答案竞赛模板,提供左边界(求最小可行解)与右边界(求最大可行解)两种写法
// 假设 check(mid) 在答案范围内具有单调性:
int l = 1, r = maxLen;
// 右边界型二分
while (l < r) {
int mid = (l + r + 1) / 2; // +1 防止死循环(当 l+1==r 时 mid==r)手动实现二分查找,在升序数组 a[1..n] 中查找 x 最后一次出现的位置,时间复杂度 O(log n)
// 若找到,返回下标(1‑based);否则返回 -1
int binarySearchRight(int a[], int n, int x) {
if (n <= 0) return -1;
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) / 2;手动实现二分查找,在升序数组 a[1..n] 中查找 x 第一次出现的位置,时间复杂度 O(log n)
// 若找到,返回下标(1‑based);否则返回 -1
int binarySearchLeft(int a[], int n, int x) {
if (n <= 0) return -1;
int l = 1, r = n;
while (l < r) {
int mid = (l + r) / 2;线性筛法,筛出 1 ~ N 中所有的质数,时间复杂度 O(N)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
bool f[N+5];
int prime[N], cnt = 0;
埃氏筛法,筛出 1 ~ N 中所有的质数,时间复杂度 O(N log log N)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
bool f[N+5];
int prime[N], cnt = 0;
BFS 搜索无权图中从起点到终点的最短路径长度(邻接矩阵)
#include <bits/stdc++.h>
using namespace std;
const int N = 105; // 根据题目点的数量范围调整
int g[N][N]; // 邻接矩阵,g[u][v] = 1 表示有边
bool vis[N];