📚 考场速抄的总模板：
#include <bits/stdc++.h>开头，typedef、方向数组、inf 一应俱全，往下是 30 级算法的模板代码，按注释分节。完整 .cpp 文件见本组 assets/template.cpp。无穷大取 0x3f3f3f3f 的原理见 04-刷题小贴士。
template
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long 蓝桥杯用不了signed main
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
//----------------------- 30 级算法模板 ----------------------
// dfs | bfs
//------------- dfs三种枚举 -------------
// 1、指数型枚举（子集枚举）
void dfs_subset(int u,int n,vector<int>& nums,vector<int>& st){
if(u==n){
for(int i=0;i<n;i++)
if(st[i]==1) cout<<nums[i]<<" ";
cout<<endl;
return;
}
st[u]=2;//不选
dfs_subset(u+1,n,nums,st);
st[u]=0;
st[u]=1;//选
dfs_subset(u+1,n,nums,st);
st[u]=0;
}
// 2、全排列枚举
void dfs_permutation(vector<int>& nums){
sort(nums.begin(), nums.end()); //（需預先排序）
do{
for(auto v:nums) cout<<v<<" ";
cout << endl;
}while(next_permutation(nums.begin(),nums.end()));
}
// 3、组合型枚举(C(n, m))
void dfs_combination(int u,int start,int n,int m,vector<int>& nums,vector<int>& way){
if(u+(n-start)<m) return;
if(u==m){
for(int i=0;i<m;i++) cout<<way[i]<<" ";
cout<<endl;
return;
}
for(int i=start;i<n;i++){
way[u]=nums[i];
dfs_combination(u+1,i+1,n,m,nums,way);
way[u]=0;
}
}
//----------------- 简单图 ----------------
//--------- 方向数组定义 -----------
const int dx4[] = {-1, 0, 1, 0}; // 上右下左
const int dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1,-1,0,1,1,1,0,-1}; // 8方向
const int dy8[] = {0,1,1,1,0,-1,-1,-1};
const int dxKnight[] = {-2,-1,1,2,2,1,-1,-2}; // 日字形
const int dyKnight[] = {1,2,2,1,-1,-2,-2,-1};
//----------- 合法性检查 -----------
template<int n, int m>
bool isValid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
// return x >= 1 && x <= n && y >= 1 && y <= m; // 1起
// return x >= 0 && x <= n+1 && y >= 0 && y <= m+1; //染色括一圈
}
//-------------- 读图 --------------
template<int N, int M>
void readGrid(int n,int m,char (&g)[N][M]) {
for(int i=0;i<n;++i) {
string s;cin>>s;
for(int j=0;j<m;++j)
g[i][j]=s[j];
}
}
template<int N, int M>
void readGridWithSpace(int n,int (&g)[N][M]) {
cin.ignore();
for(int i=0;i<n;++i){
string s; getline(cin,s);
for(int k=0,j=0;k<s.size();k++){
if(s[k]!=' '){
g[i][j++]=s[k]-'0';
}
}
}
}
//------------- DFS模板 -------------
template<int N, int M>
class DFSSolver {
char g[N][M];
bool vis[N][M];
int n, m;
void dfs(int x, int y) {
// 终止条件处理
// ...
for(int i=0;i<4;++i) {
int nx=x+dx4[i],ny=y+dy4[i];
if(isValid<N, M>(nx, ny) && !vis[nx][ny] && g[nx][ny] == '.') {
vis[nx][ny] = true;
dfs(nx,ny);
vis[nx][ny] = false; // 根据需求决定是否回溯
}
}
}
public:
void solve() {
cin>>n>>m;
readGrid(n, m, g);
memset(vis,0, sizeof vis);
vis[0][0]=true;
dfs(0,0);
}
};
//------------- BFS模板 -------------
template<int N, int M>
class BFSSolver {
int g[N][M], d[N][M], pre[N][M];
const char dirs[4] = {'U','R','D','L'};
int n,m;
void printPath(int x, int y) {
if(x==0 && y==0) return;
int p=pre[x][y];
int px=x-dx4[p],py=y-dy4[p];
printPath(px, py);
cout<<dirs[p];
}
public:
void solve() {
cin >> n >> m;
readGridWithSpace(n, g);
memset(d, -1, sizeof d);
queue<PII> q;
q.push({0, 0});
d[0][0] = 0;
while(!q.empty()) {
auto cur = q.front(); q.pop();
int x=cur.first,y=cur.second;
// if(x==targetx && y==targety){
// //dosomething
// }
for(int i = 0; i < 4; ++i) {
int nx=x+dx4[i],ny=y+dy4[i];
if(isValid<N, M>(nx, ny) && d[nx][ny] == -1 && g[nx][ny] == 0) {
d[nx][ny] = d[x][y] + 1;
pre[nx][ny] = i;
q.push({nx, ny});
}
}
}
printPath(n-1, m-1);
}
};
//---------- 洪水填充模板 ------------
template<int N, int M>
class FloodFill {
char g[N][M];
bool vis[N][M];
int n, m, cnt;
void dfs(int x, int y) {
for(int i = 0; i < 8; ++i) { // 8方向填充
int nx = x + dx8[i], ny = y + dy8[i];
if(isValid<N, M>(nx, ny) && !vis[nx][ny] && g[nx][ny] == '#') {
vis[nx][ny] = true;
dfs(nx, ny);
}
}
}
public:
void solve() {
cin >> n >> m;
readGrid(n, m, g);
cnt = 0;
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(g[i][j] == '#' && !vis[i][j]) {
vis[i][j] = true;
dfs(i, j);
++cnt;
}
cout << "连通块数量: " << cnt << endl;
}
};
//---------------------- 八皇后问题 -------------------------
/*
x,y
(0,0) (0,1) (0,2) (0,3) (0,4)
(1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
(3,0) (3,1) (3,2) (3,3) (3,4)
(4,0) (4,1) (4,2) (4,3) (4,4)
x+y
(0) (1) (2) (3) (4)
(1) (2) (3) (4) (5)
(2) (3) (4) (5) (6)
(3) (4) (5) (6) (7)
(4) (5) (6) (7) (8)
n-x+y
(5) (6) (7) (8) (9)
(4) (5) (6) (7) (8)
(3) (4) (5) (6) (7)
(2) (3) (4) (5) (6)
(1) (2) (3) (4) (5)
正对角线 x+y 反对角线： n-x+y或者x-y+n
*/
class NQueens {
static const int N = 20;
char g[N][N];
bool col[N], dg[2*N], udg[2*N];
int n;
void dfs(int u) {
if(u == n) {
for(int i = 0; i < n; ++i) puts(g[i]);
puts("");
return;
}
for(int i = 0; i < n; ++i) {
if(!col[i] && !dg[u+i] && !udg[n - u + i]) {
g[u][i] = 'Q';
col[i] = dg[u+i] = udg[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u+i] = udg[n - u + i] = false;
g[u][i] = '.';
}
}
}
public:
void solve() {
cin >> n;
for(int i = 0; i < n; ++i)
fill(g[i], g[i]+n, '.');
dfs(0);
}
};
/*
DFSSolver<100, 100>().solve();
BFSSolver<100, 100>().solve();
FloodFill<100, 100>().solve();
NQueens().solve();
*/
//------------------------ 100 级算法模板 ---------------------
// dp
// ----------------- 背包问题 -----------------
/*
01背包 逆序枚举体积 f[0]=0 每个物品选一次
完全背包 正序枚举体积 f[0]=0 物品无限选
多重背包 拆解后逆序枚举 f[0]=0 二进制拆分优化
二维费用 双逆序枚举 f[0][0]=0 双重限制条件
分组背包 组→体积→物品 f[0]=0 每组选一个
恰好装满(max) 常规顺序 f[0]=0, 其他-INF 确保状态合法性
恰好装满(count) 常规顺序 g[0]=1, 其他0 空包为唯一初始合法状态
至少装j(min) 常规顺序 f[0]=0, 其他INF 用max处理负数体积
*/
/*---------- 01背包 ------------
特点：每个物品选一次
状态转移：f[j] = max(f[j], f[j-v]+w) (逆序枚举)
int f[MAXV];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++)
for(int j=m; j>=v[i]; j--)
f[j] = max(f[j], f[j-v[i]]+w[i]);
*/
/*---------- 完全背包 ----------
特点：物品无限选
状态转移：f[j] = max(f[j], f[j-v]+w) (正序枚举)
int f[MAXV];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++)
for(int j=v[i]; j<=m; j++)
f[j] = max(f[j], f[j-v[i]]+w[i]);
*/
/*---------- 二维费用背包 ----------
限制条件：体积+重量双重限制 → 三维状态
int f[MAXV1][MAXV2];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++)
for(int j=m1; j>=v1[i]; j--)
for(int k=m2; k>=v2[i]; k--)
f[j][k] = max(f[j][k], f[j-v1[i]][k-v2[i]] + w[i]);
*/
/*---------- 分组背包 ----------
每组选一个 → 三重循环顺序：物品组→体积→组内物品
int f[MAXV], v[N][N], w[N][N], s[N];
memset(f, 0, sizeof f);
for(int i=1; i<=n; i++) // 枚举组
for(int j=m; j>=0; j--) // 枚举体积
for(int k=0; k<s[i]; k++) // 枚举组内物品
if(j >= v[i][k])
f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
*/
/*----------方案数统计 ----------
属性：count → 注意初始化和转移条件
int f[MAXV] = {0}, g[MAXV] = {0};
g[0] = 1; // 初始状态方案数为1
for(int i=1; i<=n; i++)
for(int j=m; j>=v[i]; j--){
int maxv = max(f[j], f[j-v[i]] + w[i]);
int cnt = 0;
if(maxv == f[j]) cnt += g[j];
if(maxv == f[j-v[i]] + w[i]) cnt += g[j-v[i]];
f[j] = maxv;
g[j] = cnt % MOD;
}
// 统计最大价值对应方案数
int res = 0, maxw = *max_element(f, f+m+1);
for(int j=0; j<=m; j++)
if(f[j] == maxw) res = (res + g[j]) % MOD;
*/
/*----------- 具体方案追踪 -----------
逆序推导路径 → 通过状态转移反推选择
bool selected[N] = {false};
for(int i=n, j=m; i>=1; i--)
if(j >= v[i] && f[i][j] == f[i-1][j-v[i]] + w[i]){
selected[i] = true;
j -= v[i];
}
*/
//----------- 初始化策略 -----------
/*恰好装满（最大值）
初始：f[0]=0，其他为-INF → 确保状态合法性
int f[MAXV];
memset(f, 0xcf, sizeof f); // -INF
f[0] = 0;
for(int i=1; i<=n; i++)
for(int j=m; j>=v[i]; j--)
f[j] = max(f[j], f[j-v[i]] + w[i]);
*/
/*恰好装满（方案数）
初始：g[0]=1，其他为0 → 仅空包为合法初始状态
int g[MAXV] = {0};
g[0] = 1;
for(int i=1; i<=n; i++)
for(int j=m; j>=v[i]; j--)
g[j] = (g[j] + g[j-v[i]]) % MOD;
*/
/*至少装j（最小值）
允许j-v为负数 → 用max(j-v,0)处理
int f[MAXV];
memset(f, 0x3f, sizeof f); // INF
f[0] = 0;
for(int i=1; i<=n; i++)
for(int j=m; j>=0; j--)
f[j] = min(f[j], f[max(j-v[i], 0)] + w[i]);
*/
// ----------------- 线性dp -----------------
/*
数字三角形 逆序递推，取max/min O(n2) 金字塔型路径规划
矩形单路径 二维DP，右/下转移 O(nm) 网格路径最优化
矩形双路径 三维状态压缩（步数k） O(n3) 资源重复利用问题
基本LIS 双重循环比较 O(n2) 序列特征分析
权值和LIS 在长度基础上累加权值 O(n2) 带权序列优化
双向LIS 正反两次DP求极值 O(n2) 山峰型序列分析
贪心优化LIS 维护单调队列+二分查找 O(nlogn) 大规模序列处理
最少划分上升子序列数 维护多个子序列的结尾值 O(nlogn) 任务调度问题
*/
/*-------- 正三角形路径最大值 --------
状态定义：f[i][j]表示从底边到(i,j)的最大路径和
转移方程：f[i][j] += max(左下值, 右下值)
for(int i = n-1; i >= 1; i--){ // 从底向上递推
for(int j = 1; j <= i; j++){
f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
}
cout << f[1][1]; // 顶点即为最大值
*/
/*----------- 矩形路径处理 -----------
特点：只能向右或向下移动
// 单路径最大值
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j];
}
}
cout << f[n][m];
// 双路径最大值（路径不重复）
int f[N*2][N][N]; // 使用步数k压缩状态
for(int k=2; k<=n+m; k++){ // 总步数从2开始（起点(1,1)算1步）
for(int i=1; i<k && i<=n; i++){ // 第一条路径行号
for(int j=1; j<k && j<=n; j++){ // 第二条路径行号
int val = w[i][k-i];
if(i != j) val += w[j][k-j]; // 非重复点才累加
f[k][i][j] = max({
f[k-1][i][j], // 都向右
f[k-1][i-1][j], // 路径1向下，路径2向右
f[k-1][i][j-1], // 路径1向右，路径2向下
f[k-1][i-1][j-1] // 都向下
}) + val;
}
}
}
cout << f[n+m][n][n]; // 终点状态
*/
/*----------- 基本LIS（长度） -----------
时间复杂度：O(n2) 朴素解法
int res = 0;
for(int i=1; i<=n; i++){
f[i] = 1; // 初始化为自身长度
for(int j=1; j<i; j++){
if(a[j] < a[i])
f[i] = max(f[i], f[j]+1);
}
res = max(res, f[i]);
}
cout << res;
*/
/*----------- 最大权和LIS -----------
状态定义：f[i]表示以a[i]结尾的最大子序列和
int res = 0;
for(int i=1; i<=n; i++){
f[i] = w[i]; // 初始为自身权值
for(int j=1; j<i; j++){
if(a[j] < a[i])
f[i] = max(f[i], f[j] + w[i]);
}
res = max(res, f[i]);
}
*/
/*---------- 双向LIS（山峰型） -----------
求：先上升后下降的最长子序列长度
// 正向LIS
for(int i=1; i<=n; i++){
f_up[i] = 1;
for(int j=1; j<i; j++)
if(a[j] < a[i])
f_up[i] = max(f_up[i], f_up[j]+1);
}
// 逆向LIS（处理下降部分）
for(int i=n; i>=1; i--){
f_down[i] = 1;
for(int j=n; j>i; j--)
if(a[j] < a[i])
f_down[i] = max(f_down[i], f_down[j]+1);
}
// 合并结果
int res = 0;
for(int i=1; i<=n; i++)
res = max(res, f_up[i] + f_down[i] - 1);
*/
/*---------- 贪心+二分优化LIS ----------
时间复杂度：O(nlogn)
int len = 0; // 当前最大长度
int q[N]; // 维护上升序列
for(int i=1; i<=n; i++){
int l=0, r=len;
while(l < r){ // 找第一个>=a[i]的位置
int mid = (l+r) >> 1;
if(q[mid] >= a[i]) r = mid;
else l = mid + 1;
}
q[r] = a[i]; // 替换或追加
if(r == len) len++;
}
cout << len;
*/
/*---------- 最少划分上升子序列数 ----------
贪心策略：维护多个上升子序列的结尾值
已有的单调栈只需要用一个栈顶元素表示 可以组成一个数组(单调)
每个数看能不能放在已有的栈里 且贪心的是栈顶离自己最近的
用二分找里自己最近的栈顶 若没有 就新开一个栈
最后看栈的数量 也就是数组的长度
int q[N],cnt;
for(int i=1;i<=n;i++){
int l=0,r=cnt;
while(l<r){
int mid=l+r>>1;
if(q[mid]>=w[i])
r=mid;
else
l=mid+1;
}
if(q[r]<w[i]){
r++;
}
cnt=max(cnt,r);
q[r]=w[i];
}
cout<<cnt;
*/
//----------------------- 1000 级算法模板 ----------------------
// dp ↑| 二分
//----- |----- 第一个 >= target 的位置 => lower_bound(nums.begin(), nums.end(), target)
int findLeft(vector<int>& nums,int target){
int l=0,r=nums.size();
while(l<r){
int mid=l+r>>1;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
return r;
}
//-----| ----- 最后一个 <= target 的元素位置 => upper_bound(nums.begin(), nums.end(), target) - 1
int findRight(vector<int>& nums,int target){
int l=0,r=nums.size();
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]<=target) l=mid;
else r=mid-1;
}
return r;
}
//------------------------ 1e5 级算法模板 -----------------------
// 贪心 | 排序 | set、map、heap | 二分 ↑
//------------- 排序与比较 -------------
// 单关键字
/*
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>());
priority_queue<int> maxheap;
priority_queue<int,vector<int>,greater<int>> minheap;
*/
// 多关键字
struct Task {
int priority; // 优先级（值越大越重要）
int duration; // 耗时（值越小越好）
string name;
// 方法1：重载运算符（固定排序规则）
// 默认排序规则：先按优先级降序，再按耗时升序
bool operator<(const Task& rhs) const {
if(priority != rhs.priority)
return priority > rhs.priority; // 降序
return duration < rhs.duration; // 升序
}
};
// 方法2：自定义比较器（灵活调整规则）
struct TaskComparator {
bool operator()(const Task& a, const Task& b) {
if(a.priority != b.priority)
return a.priority < b.priority; // 升序
return a.duration > b.duration; // 降序
}
};
/*
使用示例：
vector<Task> tasks;
// 使用重载运算符排序（默认规则）
sort(tasks.begin(), tasks.end());
// 使用自定义比较器排序（不同规则）
sort(tasks.begin(), tasks.end(), TaskComparator());
// 优先队列使用说明
priority_queue<Task> pq1; // 使用operator<，大顶堆（高优先级在前）
priority_queue<Task, vector<Task>, TaskComparator> pq2; // 使用自定义规则
*/
/*
.push();
.top();
.pop();
.size();
.empty();
while(!pq.empty()){
cout<<pq.top()<<" ";
pq.pop();
}
*/
//--------------------------哈希相关 STL容器特性对比 -------------------------
/*
| 容器 | 排序 | 唯一性 | 查找复杂度 | 适用场景 |
|----------------|------|--------|------------|------------------------------|
| set | 有序 | 唯一 | O(logn) | 需要有序且不重复的元素集合 |
| multiset | 有序 | 可重复 | O(logn) | 需要有序的可重复集合 |
| unordered_set | 无序 | 唯一 | O(1) | 快速查找且不关心顺序 |
| map | 有序 | 键唯一 | O(logn) | 键值对有序存储 |
| multimap | 有序 | 键重复 | O(logn) | 一键对应多值的有序存储 |
| unordered_map | 无序 | 键唯一 | O(1) | 快速键值查找 |
set:
// 基本用法：
set<int> s;
s.insert(3);
if(s.find(3) != s.end())
s.erase(3);
s.size();
s.empty();
for(auto c:s) cout<<c；
for(auto it = s.begin();it != s.end();it++) cout<<*it;
// 更改排序方式：
set<int, greater<int>> descending_set = {5, 2, 7, 1}; // {7,5,2,1}
struct Student {
string name;
int score;
// 重载 < 运算符（默认用于set排序）
bool operator<(const Student& rhs) const {
return score > rhs.score; // 分数降序排列
}
};
set<Student> student_set; // 自动使用operator<排序
student_set.insert({"Alice", 90});
student_set.insert({"Bob", 85});
// 快速去重并获取有序结果：
vector<int> nums = {5,3,5,1,3,7};
set<int> unique_sorted(nums.begin(), nums.end());
vector<int> result(unique_sorted.begin(), unique_sorted.end());
相当于：
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
//sort + unique + erase 的组合在性能上更优
// 范围查询：
set<int> data = {10,20,30,40,50};
// 查找 [25,45) 范围内的元素
auto low = data.lower_bound(25); // 第一个 >=25 的元素（30）
auto high = data.upper_bound(45); // 第一个 >45 的元素（50）
for (auto it = low; it != high; ++it) {
cout << *it << " "; // 30 40
}
unordered_map:
//基本用法：
unordered_map<string, int> age_map;
// 插入元素
age_map["Alice"] = 25;
age_map.insert({"Bob", 30});
// 访问元素（需注意键是否存在）
if(age_map.count("Alice")) {
cout << age_map.at("Alice");
// cout<< age_map["Alice"];
}
// 遍历所有键值对
for(auto& [name, age] : age_map) { //c++17 比赛应该用不了
cout << name << ": " << age << endl;
}
for(auto x : age_map){
cout << x.first << ": " << x.second << endl;
}
*/
//------------------------ 1e6 级算法模板 -----------------------
// 双指针 | 并查集 | hash | KMP × | bitset
//------------- 双指针模板 ----------------
// 1：同向双指针（滑动窗口）
int slidingWindow(vector<int>& nums, int k) {
unordered_map<int, int> freq;
int left = 0, max_len = 0;
for (int right = 0; right < nums.size(); ++right) {
freq[nums[right]]++;
while (freq.size() > k) {
if (--freq[nums[left]] == 0)
freq.erase(nums[left]);
left++;
}
max_len = max(max_len, right - left + 1);
}
return max_len;
}
// 2：对撞指针（两数之和）
bool twoSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.size()-1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return true;
if (sum < target) left++;
else right--;
}
return false;
}
// 3：序列匹配（判断子序列）
bool isSubsequence(string s, string t) {
int i = 0;
for (int j = 0; j < t.size() && i < s.size(); j++) {
if (s[i] == t[j]) i++;
}
return i == s.size();
}
//---------------- 并查集 ----------------
struct DSU{
vector<int> parent;
DSU(int n){
parent.resize(n+1);
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];
}
void unite(int x, int y) {
int fx = find(x);
int fy = find(y);
if(fx!=fy){
parent[fx]=fy;
}
}
bool connected(int x, int y) {
return find(x) == find(y);
}
};
/* 使用示例：
DSU dsu(n);
dsu.unite(a, b);
if (dsu.connected(x, y)) {...}
*/
//---------------- 字符串哈希 ---------------
const int N6 = 1e6+10;
const int P = 131;
class StringHash{
private:
ull h[N6];
ull p[N6];
int n;
public:
void init(const char* str ,int length){
n=length;
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=h[i-1]*P+str[i];
p[i]=p[i-1]*P;
}
}
ull get_hash(int l,int r) const {
if(l>r || l<1 || r>n) return 0;
return h[r]-h[l-1]*p[r-l+1];
}
};
/* 使用示例：
char s[N6];cin>>s+1;
int len=strlen(s+1);
StringHash hasher;
hasher.init(s,len);
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
bool match(hasher.get_hash(l1,r1) == hasher.get_hash(l2,r2));
cout<<(match?"Yes":"No")<<endl;
*/
//--------------- bitset ---------------
/*
* 基础用法：
* 把十进制数变成n位的二进制数 不足用0补位
* bitset<N> bs; // 初始化N位全0
* bitset<N> bs(val); // 用整型val初始化（十进制/十六进制）
* bitset<N> bs(str); // 用"0101"格式字符串初始化
*/
// 示例：8位bitset操作
void bitset_demo() {
const int N = 8;
bitset<N> bs1(0b11011010); // 二进制初始化
bitset<N> bs2(218); // 十进制初始化
bitset<N> bs3("11011010"); // 字符串初始化
// 位操作
bs1.set(0); // 第0位置1 (从右数)
bs1.reset(1); // 第1位置0
bs1.flip(2); // 第2位取反
bool bit = bs1.test(3); // 检查第3位
// 统计与转换
int cnt = bs1.count(); // 1的个数
string s = bs1.to_string(); // 转"01101011"格式
unsigned long num = bs1.to_ulong(); // 转数值
// 运算符重载
auto bs_and = bs1 & bs2; // 按位与
auto bs_or = bs1 | bs2; // 按位或
auto bs_xor = bs1 ^ bs2; // 按位异或
bs1 <<= 2; // 左移2位
bs1 >>= 1; // 右移1位
// 全量操作
bs1.set(); // 所有位置1
bs1.reset(); // 所有位置0
bs1.flip(); // 所有位取反
}
//------------------------ 1e7 级算法模板 -----------------------
// 双指针 ↑ | kmp ↑ | 筛法
//---------------- 线性筛 ---------------
const int N7=1e7+10;
int primes[N7];
bool st_isPrime[N7];
int primes_cnt=0;
void get_primes(int n){ // 获得n以内的所有素数
for(int i=2;i<=n;i++){
if(!st_isPrime[i]) primes[primes_cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st_isPrime[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
//------------------------ 1e9 级算法模板 -----------------------
// 判断质数 | 约数
bool is_prime(int n){ // 判断n是不是素数
if(n<2) return false;
for(int i=2;i<=n/i;i++){
if(n%i==0) return false;
}
return true;
}
set<int> divisors;
void get_divisors(int n){ //获得n的所有约数
divisors.clear();
for(int i=1;i<=n/i;i++){
if(n%i==0){
divisors.insert(i);
divisors.insert(n/i);
}
}
}
unordered_map<int,int> weight;
int calc_divisors_cnt(int n){ //计算n的约数个数 相当于divisors.size() 但适用于n非常大 甚至无法存的情况
weight.clear();
int res=1;
for(int i=2;i<=n/i;i++){
while(n%i==0){
weight[i]++;
n/=i;
}
}
if(n>1) weight[n]++;
for(auto x:weight) res=res*(x.second+1);
return res;
}
//------------------------ 1e18 级算法模板 -----------------------
// gcd | lcm | 快速幂
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a,b) * b;
}
ll gcd(ll a,ll b, ll c){
return gcd(gcd(a,b),c);
}
ll lcm(ll a,ll b,ll c){
return lcm(lcm(a,b),c);
}
ll qmi(ll a,ll k,ll p){ // 求 a^k mod p
ll res=1%p;
while(k){
if(k&1) res=res*a%p;
k>>=1;
a=a*a%p;
}
return res;
}
//------------------------ 1e18往上 级算法模板 -----------------------
// int_128 | 高精度模拟
// int->2e10 ll->9e19 int_128->1e38
bool big_cmp(const vector<int>& A,const vector<int>& B){
if(A.size()!=B.size()) return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--){
if(A[i]!=B[i]) return A[i]>B[i];
}
return true;
}
vector<int> big_add(vector<int> A,vector<int> B){
vector<int> C;
int t=0;
for(int i=0;i<A.size() || i<B.size();i++){
if(i<A.size()) t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(1);
return C;
}
// A>B if(big_cmp(A,B)) auto C=big_sub(A,B) else auto C=big_sub(B,A) 补充负号
vector<int> big_sub(vector<int> A,vector<int> B){
vector<int> C;
int t=0;
for(int i=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size()) t-=B[i];
C.push_back((t+10)%10);
t = t < 0 ? 1 : 0;
}
while(C.size()>1 && C.back()==0) C.pop_back();
return C;
}
vector<int> big_mul(vector<int> A,int b){
vector<int> C;
int t=0;
for(int i=0;i<A.size() || t;i++){
if(i<A.size()) t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1 && C.back()==0) C.pop_back();
return C;
}
vector<int> big_div(vector<int> A,int b,int& r){
vector<int> C;
r=0;
for(int i=A.size()-1;i>=0;i--){
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.size()>1 && C.back()==0) C.pop_back();
return C;
}
vector<int> big_mul_big(const vector<int>& A, const vector<int>& B) {
vector<int> C(A.size()+B.size(), 0);
for(int i = 0; i < A.size(); i++)
for(int j = 0; j < B.size(); j++)
C[i+j] += A[i] * B[j];
for(int i = 0, t = 0; i < C.size(); i++) {
t += C[i];
C[i] = t % 10;
t /= 10;
}
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
vector<int> str2big(const string& s){
vector<int> res;
for(int i=s.size()-1;i>=0;i--){
if(isdigit(s[i])) res.push_back(s[i]-'0');
else if(s[i]=='-' && i==0) break;
}
while(res.size()>1 && res.back()==0) res.pop_back();
return res;
}
string big2str(const vector<int>& A){
string res;
for(int i=A.size()-1;i>=0;i--)
res+=to_string(A[i]);
return res.empty()?"0":res;
}
//--------------------------- other --------------------------
//----------日期问题 ---------
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_leap(int y){
return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}
int get_days(int y,int m){
return days[m]+(m==2 && is_leap(y));
}
void next_day(int &y,int &m,int &d){
d++;
if(d>get_days(y,m)){
d=1;
m++;
if(m>12){
m=1;
y++;
}
}
}
bool check_date(int y,int m,int d){
if(m<1 || m>12) return false;
if(d<1 || d>get_days(y,m)) return false;
return true;
}
/*
while((curYear < targetYear) ||
(curYear == targetYear && curMonth < targetMonth) ||
(curYear == targetYear && curMonth == targetMonth && curDay < targetDay)){
dosomething();
next_day(curYear,curMonth,curDay);
}
char buffer[10];
sprintf(buffer,"%04d%02d%02d",curYear,curMonth,curDay);
string s(buffer);
*/
//---------- 前缀和与差分 -----------
/*
一维前缀和：
s[0] = 0;
for(int i=1; i<=n; i++)
s[i] = s[i-1] + a[i];
查询 [l,r]：s[r] - s[l-1]
二维前缀和：
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
查询 (x1,y1)-(x2,y2)：s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
一维差分：
void insert(int l, int r, int c) {
b[l] += c;
b[r+1] -= c;
}
初始化：for i insert(i,i,a[i])
区间加：insert(l,r,c)
求原数组：b[i] += b[i-1]
二维差分：
void insert(int x1,int y1,int x2,int y2,int c) {
b[x1][y1] += c;
b[x2+1][y1] -= c;
b[x1][y2+1] -= c;
b[x2+1][y2+1] += c;
}
初始化：for i,j insert(i,j,i,j,a[i][j])
区域加：insert(x1,y1,x2,y2,c)
求原数组：b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1]
*/
//---------------- 单调栈 ------------------
//-------- 最近问题 --------
/*
左侧最近的小于当前元素
遍历方向：左 →右
单调性：递增栈（栈顶最小）
操作：若当前元素≤栈顶，弹出栈顶，直到栈顶更小，此时栈顶为结果，入栈当前元素
int stk[N], tt = 0;
for (int i = 0; i < n; i++) {
while (tt && a[i] <= stk[tt]) tt--;
ans[i] = tt ? stk[tt] : -1; // 记录结果
stk[++tt] = a[i];
}
左侧最近的大于当前元素
遍历方向：左→右
单调性：递减栈（栈顶最大）
操作：类似上述，条件改为a[i] >= stk[tt]
int stk[N], tt = 0;
for (int i = 0; i < n; i++) {
while (tt && a[i] >= stk[tt]) tt--;
ans[i] = tt ? stk[tt] : -1;
stk[++tt] = a[i];
}
右侧最近的小于当前元素
遍历方向：右→左
单调性：递增栈
for (int i = n-1; i >=0; i--) {
while (tt && a[i] <= stk[tt]) tt--;
ans[i] = tt ? stk[tt] : -1;
stk[++tt] = a[i];
}
右侧最近的大于当前元素
遍历方向：右→左
单调性：递减栈
for (int i = n-1; i >=0; i--) {
while (tt && a[i] >= stk[tt]) tt--;
ans[i] = tt ? stk[tt] : -1;
stk[++tt] = a[i];
}
*/
//------ 最远问题（结合二分） ------
/*
左侧最远的大于当前元素
构造一个单调递增的序列
若这个新加的数能保持递增趋势 说明不存在比它更大的数 没必要去找了 直接加进去 供后面的数去找
如果不能保持递增趋势 就说明左边有一个比它更大的数 在这个已有的单调序列中二分找到
vector<int> stk;
//需要注意的一点是 stk存的是下标
for(int i=1;i<=n;i++){
//a[i]>a[stk.back()] 还是 a[i]>=a[stk.back()]
//加不加等号看题意
//找严格小于它的数的话 这里加等号 意味着找到它自己
//找前面小于等于它的数的话 这里不加等号
if(stk.empty() || a[i]>=a[stk.back()]){//发现该元素比栈顶元素还大（保持单调递增）
stk.push_back(i);//直接入栈
ans[i]=i;//记录答案 可能求长度等等
}
else{//发现该元素不是最大 那么原单调序列里肯定存在一些比他大的数 二分找到最远的那个
int l=1,r=stk.size()-1;
while(l<r){
int mid=l+r>>1;
if(a[stk[mid]]>a[i])
r=mid;
else
l=mid+1;
}
ans[i]=stk[r];
}
}
左边最远的小于当前元素
找最小的数 如果本身已经是最小了 就没必要找 直接加入单调栈保持单调性
如果自身不是最小 也不做什么踢出操作 直接在单调栈里找答案就行 只不过它也没必要加进去
vector<int> stk;
for(int i=1;i<=n;i++){
if(stk.empty() || a[i]<a[stk.back()]){//只要改两处
stk.push_back(i);
ans[i]=i;
}
else{
int l=0,r=stk.size()-1;
while(l<r){
int mid=l+r>>1;
if(a[stk[mid]]<a[i]) //只要改两处
r=mid;
else
l=mid+1;
}
ans[i]=stk[r];
}
}
右边 最远的 大于它的数
从右边开始枚举罢了 1-n变成n-1即可
找最远的大于 若该数是最大的 直接加入栈中 如果不是 再二分找一下
for(int i=n;i>=1;i--){//只需改循环
if(stk.empty() || a[i]>a[stk.back()]){
stk.push_back(i);
ans[i]=i;
}
else{
int l=0,r=stk.size()-1;
while(l<r){
int mid=l+r>>1;
if(a[stk[mid]]>a[i])
r=mid;
else
l=mid+1;
}
ans[i]=stk[r];
}
}
右边 最远的 小于它的数
n-1 最小 若该数为最小 直接加入 否则 二分找
for(int i=n;i>=1;i--){
if(stk.empty() || a[i]<a[stk.back()]){
stk.push_back(i);
ans[i]=i;
}
else{
int l=0,r=stk.size()-1;
while(l<r){
int mid=l+r>>1;
if(a[stk[mid]]<a[i])
r=mid;
else
l=mid+1;
}
ans[i]=stk[r];
}
}
*/
//---------------- 单调队列 ------------------
/*
窗口的最小值
deque<int> q;
vector<int> res;
for (int i = 0; i < n; i++) {
if (!q.empty() && i - q.front() >= k) q.pop_front();
while (!q.empty() && a[i] <= a[q.back()]) q.pop_back(); //求最小 递增区间 若出现向下 出队
q.push_back(i);
if (i >= k-1) res.push_back(a[q.front()]); //当前区间的最大值为队头
}
窗口最大值
while (!q.empty() && a[i] >= a[q.back()]) q.pop_back();
*/
//-------------- 区间合并 ---------------
/*
多次要对一个大区间的某些段做标记 可以暴力对每一段做标记 最后枚举整个区间 看是否有没标记过的
很多时候也可以用差分 某段处理后就在该段++ 不过我们要的结果不在乎具体是多少 只是有值就1 没值就0
然后对于暴力对每段做标记和差分的话 都会存在一个问题 有很多地方做了重复操作
这个时候就可以使用区间合并进行优化 把能合并的区间都合并起来 再对他们去做操作 就可以省去一些重复功
对于合并操作 得分析一个问题 题目中诸如：13 45 这样的能不能合并 如果能 模版处就改成ed+1<range.first
核心步骤
区间排序：按左端点升序排列。
遍历合并：依次判断当前区间是否可合并到当前维护区间中，否则开启新区间
typedef pair<int,int> PII;
PII range[N];
int cnt;
range[cnt++]={l,r};
sort(range,range+cnt);
vector<PII> merged; // 存储合并后的区间
if (cnt == 0) {
// 无区间处理
} else {
int st = range[0].first, ed = range[0].second;
for (int i = 1; i < cnt; i++) {
// 判断是否可合并（允许相邻区间合并）
if (range[i].first <= ed + 1) {
ed = max(ed, range[i].second);
} else {
merged.push_back({st, ed});
st = range[i].first;
ed = range[i].second;
}
}
merged.push_back({st, ed}); // 加入最后一个区间
}
*/
//----------------- 数学 ----------------
// 转double -> a*1.0/b
// 除法尽量变乘法
// 等差数列
// a_n = a_1 + (n-1)d
// s_n = (n/2)(a_1+a_n) = (n/2)(2a_1 + (n-1)d) = na_1 + n(n-1)/2d
// 等比数列
// a_n = a_1 * r^(n-1)
// s_n = a_1 * (1 - r^n) / 1-r (r!=1)
// 计算几何
// 点斜式：y-y1=k(x-x1)
// 截距式：y=kx+b
// double k = (double) (y2-y1) / (x2-x1);
// double b = (double) y1-k*x1
// double x = (double) (b2-b1) / (k1-k2);
// round() 四舍五入
// floor() 向下取整
// ceil() 向上取整
// pow() 指数幂 ldexp() 浮点数幂运算
// sqrt() 平方根
// log2() log10 对数
//----------------- 位运算 ----------------
// & 同真为真 其余为假 x&1相当于看x为多少
// if(x&1) 奇数 if((X&1)==0) 偶数
// | 同假为假 其余为真
// ^ 相同为0，不同为1 x^y^y等于什么都没做 若x==y 则x^y=0
// >> x>>=1 相当于 x/=2 x>>=n 相当于 x/=2^n
// << x<<y 相当于x*2^y 3<<5 相当于 3*2^5 1<<y 相当于 2^y
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
return 0;
}
⬅️ 01-根据时间复杂度选择算法 🏠 00-算法 ➡️ 00-项目筑基
💬 评论