C++ 算法竞赛STL以及常见模板

目录

STL

/*═══════════════ Vector ═══════════════*/

/*════════════════ Pair ════════════════*/

/*══════════════ String ════════════════*/

/*══════════════ Queue ═════════════════*/

/*═════════ Priority Queue ════════════*/

/*═══════════════ Stack ════════════════*/

/*════════════════ Set ═════════════════*/

/*════════════════ Map ═════════════════*/

/*════════════ Algorithm ══════════════*/

/*═════════════ 竞赛技巧 ═══════════════*/

其他算法

DFS BFS

试除法求所有约数

快速排序算法模板

Dp

高精度除以低精度

埃氏筛

并查集

试除法求所有约数

位运算

 gcd() / lcm()

---

STL

/*═══════════════ Vector ═══════════════*/

● size(): v.size()          // 元素数量

● empty(): if (v.empty())    // 判空

● clear(): v.clear()        // 清空

● front / back: v.front() = 5; v.back() = 10;

● push_back / pop_back: v.pb(1); v.pop_back();

● []: v[0] = 5;            // 随机访问

● 迭代器: for (auto it = v.begin(); it != v.end(); ++it)

▲ 例子：

vector<int> v {1,2,3};     // 初始化

v.reserve(100);           // 预分配

v.pb(4);                  // 添加元素

sort(all(v));             // 排序

v.erase(unique(all(v)), v.end()); // 去重

--------------------------------------------------------------------

vector<int> ssr(10, 10086);//（长度，数值）

ssr.push_back(1);//开销大

ssr.pop_back();//删除尾部

ssr.clear();

ssr.empty();

ssr.size();//返回size_t,在相乘可能溢出

int num1=100;

ssr.resize(num1);//大补0，小就删

//一些如条件限制n*m的题目，用普通数组不好判断大小，就要使用vector限制

vector<vector<int> > ssr1(100, vector<int>());//行，列

for (auto& tonum : ssr)//auto

{

cout << tonum << endl;

}

/*════════════════ Pair ════════════════*/

● first / second: pair<int, string> p = { 1, "a" }; p.first++;

● 比较运算: if (p1 < p2) // 先比first后second

▲ 例子：

pair<int, int> a {3,4}, b

{ 3,5};

cout << (a < b); // 输出1（3相等，比较4<5）

--------------------------------------------------------------------

int num[10] = { 1,2,3,4,5,6,7,8,9,10 };

reverse(num, num + 10);

for (int tonum : num)

{

cout << tonum << endl;

}

pair<int, int> par1 = make_pair(1, 2);

pair<int, int> par2 = { 1,2 };

if (par1 == par2)

{

cout << "YES" << endl;

}

/*══════════════ String ════════════════*/

● substr(3, 2): s.substr(3, 2) // 从下标3取2字符

● c_str(): printf("%s", s.c_str());

● find: if (s.find("abc") != string::npos)

▲ 例子：

string s = "ABCDEF";

cout << s.substr(1, 3); // 输出"BCD"

s += to_string(123);   // 拼接字符串

--------------------------------------------------------------------

string s1(10, '0');//第一个个数，第二个赋值

string s2(10, '1');

s1[0] = '1';

string s3 = "12345678";

//out << s1 + s2 << endl;

cout << s3.substr(3,2) << endl;//第一个定位从下标3开始，第二个是子串长度，用来截取子串

if (s1.find("101")!=string::npos)

{

cout << "YES" << endl;

}

else

{

cout << "NO" << endl;

}

cout << (s1.find(100)) << endl;

s1.find(100);

int ssr = stoi(s1);

string s = to_string(ssr);

//注意，尾接字符串用+=

//find效率不高

/*══════════════ Queue ═════════════════*/

● push: q.push(1);

● front / back: int x = q.front();

● pop: q.pop();        // 弹出队头

▲ 例子：

queue<int> q;

q.push(1); q.push(2);

cout << q.front(); // 1

q.pop();           // 队列变[2]

--------------------------------------------------------------------

queue <int> quq;

quq.size();

quq.empty();

quq.push(11);

quq.push(22);

quq.push(33);

cout << quq.front() << " " << quq.back() << endl;

/*═════════ Priority Queue ════════════*/

● 大根堆: priority_queue<int> pq; pq.push(3);

● 小根堆: priority_queue<int, vector<int>, greater<>> pq;

● top / pop: int x = pq.top(); pq.pop();

▲ 例子：

pq.push(2); pq.push(1);

cout << pq.top(); // 大根堆输出2，小根堆输出1

--------------------------------------------------------------------

struct game

{

    int year;

    int money;

};

struct compare_outbig {

    bool operator()(const game& game1, const game& game2)

    {

        return game1.money < game2.money;//钱少的在堆下，多的在顶部，输出最大的

    }

};

struct compare_outsmall {

    bool operator()(const game& game1, const game& game2)

    {

        return game1.money > game2.money;//钱多的在堆下，少的在顶部，输出最小的

    }

};

int solve1() {

    priority_queue<int> out_big;

    priority_queue<int, vector<int>, greater<int> >out_small;

    priority_queue<game, vector<game>, compare_outbig> struct_out_big;

    priority_queue<game, vector<game>, compare_outsmall>struct_out_small;

    int n=1;

    while(n)

    {

        cin >> n;

        out_big.push(n);

        out_small.push(n);

    }

    cout << "out_big" << endl;

    while (!out_big.empty())

    {

        cout << out_big.top() << endl;

        out_big.pop();

    }

    cout << "out_small" << endl;

    while (!out_small.empty())

    {

        cout << out_small.top() << endl;

        out_small.pop();

    }

    int m = 1;

    while (m)

    {

        cin >> n >> m;

        game sample1;

        sample1.year = n;

        sample1.money = m;

        struct_out_big.push(sample1);

        struct_out_small.push(sample1);

    }

    cout << "struct_out_big" << endl;

    while (!struct_out_big.empty())

    {

        game sample1 = struct_out_big.top();

        cout <<"game_money:"<< sample1.money <<"game_:" <<sample1.year << endl;

        struct_out_big.pop();

    }

    cout << "struct_out_small" << endl;

    while (!struct_out_small.empty())

    {

        game sample1 = struct_out_small.top();

        cout << "game_money:" << sample1.money << "game_:" << sample1.year << endl;

        struct_out_small.pop();

    }

/*═══════════════ Stack ════════════════*/

● push: stk.push(10);

● top: int x = stk.top();

● pop: stk.pop();

▲ 例子：

stack<int> s;

s.push(1); s.push(2);

cout << s.top(); // 2

s.pop();         // 栈变[1]

--------------------------------------------------------------------

stack<int> stk;

//我用的比较少，不如直接用vector

stk.push(111);

stk.push(222);

stk.push(333);

cout << stk.size() << endl;

stk.empty();

/*for (auto& tonum : stk)   //不可以直接访问

cout << tonum <<endl;*/

cout<<stk.top();

stk.pop();

cout<<stk.top();

/*════════════════ Set ═════════════════*/

● insert: s.insert(3);

● find: if (s.find(3) != s.end())

● lower_bound: auto it = s.lower_bound(2);

▲ 例子：

set<int> s {3,1,2};

cout << *s.lower_bound(2); // 2

s.erase(2);                // 删除元素

--------------------------------------------------------------------

//一个集合,在找特别分散但是数量不多的数字特别好用

//set 一个元素要么在集合中，要么不在，出现一次，有序，默认从小到大

//multiset 一个元素要么在集合中，要么不在，可以出现多次，有序，默认从小到大

//unordered_set 一个元素要么在集合中，要么不在，出现一次，无序

set<int> st;

set<int, greater<int> >st1;//从大到小

//通用st.size();st.clear();st.empty();

st.insert(1);

st.insert(2);

st.insert(1);

for (auto& tonum : st)

{

cout << tonum << endl;

}

//for(set<int>::iterator it=st.begin();it!=st.end();++it)cout<<*it<<endl;

st.erase(1);

cout << st.count(1)<<endl;

cout << st.count(2) << endl;

auto so = st.find(2);//返回迭代器

cout << *so;

//unorder_set<int> st2 无序

//multiset_set<int> st3 多个数

/*════════════════ Map ═════════════════*/

● 插入: mp["key"] = 5; 或 mp.insert({ "key",5});

● 遍历: for (auto &[k, v] : mp)

▲ 例子：

map<string, int> mp;

mp["apple"] = 3;

if (mp.count("apple")) cout << mp["apple"]; // 3

---------------------------------------------------------------------------

//一个映射,

//map 一个元素仅出现一次，有序，默认从小到大

//multimap 一个元素可以出现多次，有序，默认从小到大

//unordered_map 一个元素仅出现一次，无序

map<string, int> mp1;

if (mp1.find("1") != mp1.end())

{

cout << "YES" << endl;

}

else

{

cout << "NO" << endl;

}

mp1.erase("1");

mp1.clear();

mp1["a"] = 1;

mp1["b"] = 2;

for (map<string, int>::iterator it = mp1.begin();it != mp1.end();it++)

{

cout << it->first << " " << it->second << endl;

}

for (auto &tonum : mp1)

{

cout << tonum.first << " " <<tonum.second<< endl;

}

/*════════════ Algorithm ══════════════*/

● sort: sort(all(v), greater<>()); // 降序

● reverse: reverse(all(v));

● unique: v.erase(unique(all(v)), v.end());

● lower_bound: int pos = lower_bound(all(v), 5) - v.begin();

▲ 例子：

vector<int> v {3,1,4,1};

sort(all(v));               // [1,1,3,4]

auto it = lower_bound(all(v), 2); // 指向3

/*═════════════ 竞赛技巧 ═══════════════*/

▲ 加速cin: ios::sync_with_stdio(0); cin.tie(0);

▲ 宏:

#define all(x) (x).begin(), (x).end()

▲ 位运算: cout << __builtin_ctz(8); // 3（末尾0个数）

其他算法

DFS BFS

/*═══════════════ DFS 核心模板 ═══════════════*/

// 递归式（适用：排列/组合/树遍历）

void dfs(当前状态)

{

    if (终止条件)

    {

        记录结果;

        return;

    }

    for (所有分支选择)

    {

        if (剪枝条件) continue;

        更新状态;

        dfs(下一状态);

        恢复状态; // 回溯

    }

}

// 示例：矩阵搜索

int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }; // 方向数组

void dfs(int x, int y, vector<vector<int>>& grid)

{

    if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0)

        return;

    grid[x][y] = 0; // 标记访问

    for (int i = 0; i < 4; ++i)

        dfs(x + dx[i], y + dy[i], grid);

}

/*═══════════════ BFS 核心模板 ═══════════════*/

// 标准层序（适用：最短路径/扩散问题）

int bfs(起始状态)

{

    queue<StateType> q;

    unordered_set<StateType> vis; // 或二维vis数组

    q.push(初始状态);

    vis.insert(初始状态);

    int step = 0;

    while (!q.empty())

    {

        int sz = q.size();

        for (int i = 0; i < sz; ++i)

        { // 层序遍历关键

            auto cur = q.front(); q.pop();

            if (终止条件) return step;

            for (所有扩展状态)

            {

                if (!vis.count(新状态))

                {

                    vis.insert(新状态);

                    q.push(新状态);

                }

            }

        }

        step++;

    }

    return -1; // 未找到

}

// 示例：二叉树层序遍历

vector<vector<int>> bfs(TreeNode* root)

{

    queue<TreeNode*> q;

    vector<vector<int>> res;

    if (root) q.push(root);

    while (!q.empty())

    {

        res.push_back({ });

for (int i = q.size(); i > 0; --i)

{

    auto node = q.front(); q.pop();

    res.back().push_back(node->val);

    if (node->left) q.push(node->left);

    if (node->right) q.push(node->right);

}

    }

    return res;

}

/*═══════════════ 高频变种与优化 ═══════════════*/

// 双向BFS模板（优化搜索空间）

int twoWayBFS(begin, end)

{

    unordered_set<State> q1{ begin}, q2{ end}, visited{ begin};

    int step = 0;

    while (!q1.empty() && !q2.empty())

    {

        if (q1.size() > q2.size()) swap(q1, q2); // 扩展较小队列

        unordered_set<State> temp;

        for (auto cur : q1) {

    for (新状态 : 生成下一状态(cur))

    {

        if (q2.count(新状态)) return step + 1; // 相遇

        if (!visited.count(新状态))

        {

            visited.insert(新状态);

            temp.insert(新状态);

        }

    }

}

q1 = temp;

step++;

    }

    return -1;

}

// 记忆化DFS（树形DP/剪枝）

vector<int> memo; // memo数组记录中间结果

int dfs(State s)

{

    if (终止条件) return 0;

    if (memo[s] != -1) return memo[s];

    int res = 初始值;

    for (所有子问题)

    {

        res = max / min(res, dfs(子状态) + 增量计算);

    }

    return memo[s] = res;

}

/*═══════════════ 参数说明与替换指南 ═══════════════*/

■ 状态表示：

   -矩阵问题：pair<int, int> 坐标 或 压缩为int编码

   - 树问题：TreeNode* 节点指针

   - 图问题：节点编号int

■ 终止条件：根据题意调整判断位置

   - 在BFS弹出时判断（保证最短路径）

   - 在DFS递归入口判断（允许完整路径记录）

■ 状态扩展：

   - 树：left/right子节点

   - 图：邻接表遍历

   - 矩阵：方向数组遍历

■ 记录路径：

   - BFS：使用pre数组记录前驱节点

   - DFS：用path数组记录当前路径

快速幂

求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)

{

    int res = 1 % p, t = m;

    while (k)

    {

        if (k&1) res = res * t % p;

        t = t * t % p;

        k >>= 1;

    }

    return res;

}

线性筛法求素数

int primes[N], cnt;     // primes[]存储所有素数

bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)

{

    for (int i = 2; i <= n; i ++ )

    {

        if (!st[i]) primes[cnt ++ ] = i;

        for (int j = 0; primes[j] <= n / i; j ++ )

        {

            st[primes[j] * i] = true;

            if (i % primes[j] == 0) break;

        }

    }

}

试除法求所有约数

vector<int> get_divisors(int x)

{

    vector<int> res;

    for (int i = 1; i <= x / i; i ++ )

        if (x % i == 0)

        {

            res.push_back(i);

            if (i != x / i) res.push_back(x / i);

        }

    sort(res.begin(), res.end());

    return res;

}

快速排序算法模板

void quick_sort(int q[], int l, int r)

{

    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];

    while (i < j)

    {

        do i ++ ; while (q[i] < x);

        do j -- ; while (q[j] > x);

        if (i < j) swap(q[i], q[j]);

    }

    quick_sort(q, l, j), quick_sort(q, j + 1, r);

}

Dp

/*════════════ 动态规划核心模板 ════════════*/

// === 一维线性DP ===

// 例：斐波那契/爬楼梯

vector<int> dp(n+1, 0);

dp[0] = 1; dp[1] = 1;

for (int i = 2; i <= n; ++i)

    dp[i] = dp[i - 1] + dp[i - 2];

// === 二维矩阵DP ===

// 例：最小路径和/最长公共子序列

vector<vector<int>> dp(m, vector<int>(n, 0));

for (int i = 0; i < m; ++i)

    for (int j = 0; j < n; ++j)

        dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);

// === 01背包问题 ===

vector<int> dp(cap+1, 0);

for (int i = 0; i < n; ++i)

    for (int j = cap; j >= w[i]; --j)

        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

// === 完全背包问题 ===

vector<int> dp(cap+1, 0);

for (int i = 0; i < n; ++i)

    for (int j = w[i]; j <= cap; ++j)

        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

// === 区间DP ===

// 例：最长回文子序列

vector<vector<int>> dp(n, vector<int>(n, 0));

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]);

    }

// === 状态压缩DP ===

// 例：TSP问题

vector<vector<int>> dp(1<<n, vector<int>(n, INF));

dp[1][0] = 0; // 从0号点出发

for (int mask = 1; mask < (1 << n); ++mask)

    for (int u = 0; u < n; ++u)

        if (mask & (1 << u))

            for (int v = 0; v < n; ++v)

                if (!(mask & (1 << v)))

                    dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + g[u][v]);

// === 树形DP（记忆化）===

// 例：打家劫舍III

unordered_map<TreeNode*, int> memo;

function < int(TreeNode *) > dfs = [&](TreeNode * root) {

    if (!root) return 0;

    if (memo.count(root)) return memo[root];

    int rob = root->val + dfs(root->left->left) + dfs(...);

    int not_rob = dfs(root->left) + dfs(root->right);

    return memo[root] = max(rob, not_rob);

};

/*═══════════ 优化技巧 ═══════════*/

// 空间优化：滚动数组（fib用prev,curr变量）

// 降维：背包问题压至一维（注意遍历顺序）

// 剪枝：提前终止无效状态

// 记忆化：unordered_map记录子问题

// 预处理：排序/前缀和加速状态转移

高精度除以低精度

// A / b = C ... r, A >= 0, b > 0

vector<int> 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;

}

埃氏筛

#include<bits/stdc++.h>

using namespace std;

bool is_prime[100005];

//true表示是质数

//false表示不是质数

int main()

{

    memset(is_prime, true, sizeof(is_prime));

    int n;

    cin >> n;

    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= sqrt(n); i++)

    {

        if (is_prime[i])

        {

            for (int j = 2; i * j <= n; j++)

            {

                is_prime[i * j] = false;

            }

        }

    }

    //x 是不是质数

    if (is_prime[n]) cout << "is_prime";

    else cout << "not_prime";

    return 0;

}

并查集

const int  N=1005 // 指定并查集所能包含元素的个数（由题意决定）

int pre[N];      // 存储每个结点的前驱结点

int rank[N];  /*非必要 */  // 树的高度

void init(int n)      // 初始化函数，对录入的 n 个结点进行初始化

{

    for(int i = 0; i < n; i++){

        pre[i] = i;      // 每个结点的上级都是自己

        rank[i] = 1;     // 每个结点构成的树的高度为 1

    }

}

int find(int x)      // 改进查找算法：完成路径压缩，将 x 的上级直接变为根结点，那么树的高度就会大大降低

{

    if(pre[x] == x) return x; // 递归出口：x 的上级为 x 本身，即 x 为根结点

    return pre[x] = find(pre[x]);   // 此代码相当于先找到根结点 rootx，然后 pre[x]=rootx

}

bool isSame(int x, int y)       // 判断两个结点是否连通

{

    return find(x) == find(y);   // 判断两个结点的根结点（即代表元）是否相同

}

bool join(int x,int y)

{

    x = find(x); // 寻找 x 的代表元

    y = find(y); // 寻找 y 的代表元

    if(x == y) return false; // 如果 x 和 y 的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑

    if(rank[x] > rank[y]) pre[y]=x; // 如果 x 的高度大于 y，则令 y 的上级为 x

    else // 否则

    {

        if(rank[x]==rank[y]) rank[y]++; // 如果 x 的高度和 y 的高度相同，则令 y 的高度加1

        pre[x]=y; // 让 x 的上级为 y

}

return true; // 返回 true，表示合并成功

}

试除法求所有约数

vector<int> get_divisors(int x)

{

    vector<int> res;

    for (int i = 1; i <= x / i; i ++ )

        if (x % i == 0)

        {

            res.push_back(i);

            if (i != x / i) res.push_back(x / i);

        }

    sort(res.begin(), res.end());

    return res;

}

位运算

求n的第k位数字: n >> k & 1

返回n的最后一位1：lowbit(n) = n & -n

 gcd() / lcm()

（C++17）返回最大公因数 / 最小公倍数

int x = gcd(8, 12); // 4int y = lcm(8, 12); // 24

• lower_bound(): 寻找 ≥ 的第一个元素的位置
• upper_bound(): 寻找 > 的第一个元素的位置

vector<int> arr {0, 1, 1, 1, 8, 9, 9};

idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4

idx = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4

idx = upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4

idx = upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 5

next_permutation(a,a+n)全排列函数，a为数组首地址，执行一次往下排列一次，不能排之后返回false。

优先队列priority_queue<int,vector<int>,greater<int> >p;//总是输出小的p.top()

priority_queue<int> p//总是输出大的p.top()输出方法

priority_queue<string,vector<string>,cmp> q;

struct cmp {

    bool operator()(const string& s1, const string& s2) {

        return s1 < s2; // 倒序排列

    }

};

无序集合unordered_set<int>(candyType.begin(),candyType.end()).size();//求candytype数组中数据种类

for (int i = 0; i < n; i++) {

if (intSet.find(arr[i]) == intSet.end())//如果find不到就返回end()

intSet.insert(arr[i]);

else

duplicate.insert(arr[i]);

}