STL例子

• STL容器库常用内容
• C++文档：容器库
• OIWiki：STL容器
• OIWiki：STL算法

明明的随机数

排序后枚举

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
const int MAXAI = 100000;
int n;
int a[MAXN + 5];
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int cnt = 1;
    for (int i = 2; i <= n; i++)
        if (a[i] != a[i - 1])
            cnt++;
    cout << cnt << "\n";
    cout << a[1] << " ";
    for (int i = 2; i <= n; i++)
        if (a[i] != a[i - 1])
            cout << a[i] << " ";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    work();
    return 0;
}

使用 unique 去重

int n;
int a[MAXN + 5];
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int nn = unique(a + 1, a + n + 1) - a - 1;
    cout << nn << "\n";
    for (int i = 1; i <= nn; i++)
        cout << a[i] << " ";
}

vector 排序后 unique 去重

int n;
vector<int> a;
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    int nn = unique(a.begin(), a.end()) - a.begin();
    cout << nn << "\n";
    for (int i = 0; i <= nn - 1; i++)
        cout << a[i] << " ";
}

vector 排序后迭代器枚举

int n;
vector<int> a;
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    // [a.begin(), R)
    vector<int>::iterator R = unique(a.begin(), a.end());
    cout << (R - a.begin()) << "\n";
    for (auto it = a.begin(); it != R; it++)
        cout << (*it) << " ";
}

计数排序

int n;
int a[MAXN + 5];
int cnt[MAXAI + 5];
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
        
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt[a[i]]++;
        if (cnt[a[i]] == 1)
            ans++;
    }
    cout << ans << "\n";
    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i] >= 1)
            cout << i << " ";
}

bitset 判断每个数是否出现

int n;
bitset<MAXAI + 1> cnt;
void work()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cnt.set(x);
    }
    cout << cnt.count() << "\n";
    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i])
            cout << i << " ";
}

合并果子

multiset

#include <bits/stdc++.h>
using namespace std;
int n;
int a[30000 + 5];
multiset<int> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s.insert(a[i]);
    }
    long long ans = 0;
    while (s.size() > 1)
    {
        int a = *s.begin();
        // 如果erase(a)，会删除所有 a，所以只删除迭代器的值
        s.erase(s.begin());
        int b = *s.begin();
        s.erase(s.begin());
        ans += (a + b);
        s.insert(a + b);
    }
    cout << ans;
    return 0;
}

map

#include <bits/stdc++.h>
using namespace std;
int n;
int a[30000 + 5];
map<int, int> m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        m[a[i]]++;
    }
    long long ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        auto it = m.begin();
        // 取 a
        int a = (*it).first;
        (*it).second--;
        if ((*it).second == 0)
            m.erase(it);
        // 取 b
        it = m.begin();
        int b = it->first;
        it->second--;
        if (it->second == 0)
            m.erase(it);
        // 合并
        ans += (a + b);
        m[a + b]++;
    }
    cout << ans;
    return 0;
}

priority_queue

传相反数实现小根堆

#include <bits/stdc++.h>
using namespace std;
int n;
int a[30000 + 5];
// q.push(x); // 把 x 放入优先队列（O(logSize)）
// q.top();   // 优先队列中最大的元素（O(1)）
// q.pop();   // 弹出（删除）最大的元素（O(logSize)）
priority_queue<int> q;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 都放到优先队列里
    for (int i = 1; i <= n; i++)
        q.push(-a[i]); // 存相反数，来实现最小堆
    int ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        int x = -q.top();
        q.pop();
        int y = -q.top();
        q.pop();
        ans += x + y;
        q.push(-(x + y));
    }
    cout << ans;
    return 0;
}

重载运算符的优先队列

#include <bits/stdc++.h>
using namespace std;
int n;
struct Guozi
{
    int daxiao;
};
Guozi a[30000 + 5];
// 把小于号用大于的规则定义，这样取出来的最大值就会使daxiao最小的
bool operator<(const Guozi &a, const Guozi &b)
{
    return a.daxiao > b.daxiao;
}
// q.push(x); // 把 x 放入优先队列（O(logSize)）
// q.top();   // 优先队列中最大的元素（O(1)）
// q.pop();   // 弹出（删除）最大的元素（O(logSize)）
priority_queue<Guozi> q;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].daxiao;
    // 都放到优先队列里
    for (int i = 1; i <= n; i++)
        q.push(a[i]);
    int ans = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        int x = q.top().daxiao;
        q.pop();
        int y = q.top().daxiao;
        q.pop();
        ans += x + y;
        q.push((Guozi){x + y});
    }
    cout << ans;
    return 0;
}

自己实现小根堆

#include <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 30000;
// 小根堆（越小越优先的优先队列）
struct PQ
{
    int tot;
    int t[MAXN + 5];
    void clear()
    {
        tot = 0;
    }
    int size()
    {
        return tot;
    }
    bool empty()
    {
        return tot == 0;
    }
    int top()
    {
        // 可以自己检测非法
        return t[1];
    }
    void push(int x)
    {
        tot++;
        t[tot] = x;
        int now = tot;
        // 不是根节点，并且父节点比自己大的时候往上走
        while (now != 1 && t[now / 2] > t[now])
        {
            swap(t[now / 2], t[now]);
            now /= 2;
        }
    }
    void pop()
    {
        swap(t[1], t[tot]);
        tot--;
        // 从根节点开始维护到合适位置
        int now = 1;
        while (1)
        {
            // 没有子节点
            if (now * 2 > tot)
                break;
            // 只有左子节点
            else if (now * 2 + 1 > tot)
            {
                if (t[now * 2] < t[now])
                {
                    swap(t[now * 2], t[now]);
                    now = now * 2;
                }
                else
                    break;
            }
            // 左右子节点都有
            else
            {
                // 自己最小
                if (t[now] <= t[now * 2] && t[now] <= t[now * 2 + 1])
                    break;
                // 左边最小
                else if (t[now * 2] <= t[now * 2 + 1])
                {
                    swap(t[now * 2], t[now]);
                    now = now * 2;
                }
                else
                {
                    swap(t[now * 2 + 1], t[now]);
                    now = now * 2 + 1;
                }
            }
        }
    }
};
PQ q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    q.clear();
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        q.push(x);
    }
    long long ans = 0;
    while (q.size() > 1)
    {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        // 合并
        ans += (a + b);
        q.push(a + b);
    }
    cout << ans;
    return 0;
}

全排列问题

next_permutation

如果已经是最后一个排列了，执行之后会变为第一个排列，并返回假，否则返回真。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        a[i] = i;
    while (1)
    {
        for (int i = 1; i <= n; i++)
            cout << "    " << a[i];
        cout << "\n";
        if (!next_permutation(a + 1, a + n + 1))
            break;
    }
    return 0;
}

求第 k 大数

nth_element

时间复杂度 [math]\displaystyle{ O(n) }[/math]，快排每次只排序 k 所在的那一部分。

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1000000 + 5];
bool cmp(int a, int b)
{
    return a > b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    nth_element(a + 1, a + k, a + n + 1, cmp);
    cout << a[k];
    return 0;
}

部落卫队

最基础的搜索

枚举方案，最后检查

#include <bits/stdc++.h>
using namespace std;
int n, m;
// e[i]: 存 i 的所有敌人
vector<int> e[105];
// ee[i][j] 存 i j 之间是1否0是敌人
bool ee[105][105];

// 考虑第 x 个人选不选
int ansCnt = 0;
int ans[105];
bool now[105];
void dfs(int x)
{
    // 前 n 个人考虑完了
    if (x > n)
    {
        // 计算有没有冲突
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (now[i] && now[j] && ee[i][j])
                    return;
        //  计算选了几个人
        int nowCnt = 0;
        for (int i = 1; i <= n; i++)
            nowCnt += now[i];
        // 尝试更新答案
        if (nowCnt > ansCnt)
        {
            ansCnt = nowCnt;
            for (int i = 1; i <= n; i++)
                ans[i] = now[i];
        }
        return;
    }
    // 考虑第 x 个人选还是不选
    now[x] = true;
    dfs(x + 1);
    now[x] = false;
    dfs(x + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        ee[u][v] = true;
        ee[v][u] = true;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1);
    cout << ansCnt << "\n";
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}

优化后的搜索

每次选择前保证合法。

#include <bits/stdc++.h>
using namespace std;
int n, m;
// e[i]: 存 i 的所有敌人
vector<int> e[105];
// ee[i][j] 存 i j 之间是1否0是敌人
bool ee[105][105];
// 最优方案
int ansCnt = 0;
int ans[105];
// 考虑第 x 个人选不选，之前已经选了 nowCnt 个人
bool now[105];
void dfs(int x, int nowCnt)
{
    // 前 n 个人考虑完了
    if (x > n)
    {
        // 尝试更新答案
        if (nowCnt > ansCnt)
        {
            ansCnt = nowCnt;
            for (int i = 1; i <= n; i++)
                ans[i] = now[i];
        }
        return;
    }
    // 考虑第 x 个人选还是不选
    // 看看可不可以选，检查x的敌人当前有没有被选
    bool flag = false; // 有没有敌人被选择
    for (int i = 0; i < e[x].size(); i++)
    {
        if (now[e[x][i]])
        {
            flag = true;
            break;
        }
    }
    if (!flag)
    {
        now[x] = true;
        dfs(x + 1, nowCnt + 1);
    }
    now[x] = false;
    dfs(x + 1, nowCnt);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        ee[u][v] = true;
        ee[v][u] = true;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    cout << ansCnt << "\n";
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}

bitset 加速搜索

52ms -> 14ms

#include <bits/stdc++.h>
using namespace std;
int n, m;
// ee[i][j] 存 i j 之间是1否0是敌人
bitset<101> ee[105];
// 记录答案
int ansCnt = 0;
bitset<101> ans;
// 考虑第 x 个人选不选
bitset<101> now;
void dfs(int x)
{
    // 前 n 个人考虑完了
    if (x > n)
    {
        if (now.count() > ans.count())
            ans = now;
        return;
    }
    // 考虑第 x 个人选还是不选
    if ((now & ee[x]).none())
    {
        now[x] = true;
        dfs(x + 1);
    }
    now[x] = false;
    dfs(x + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        ee[u][v] = true;
        ee[v][u] = true;
    }
    dfs(1);
    cout << ans.count() << "\n";
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}

shuffle 随机化贪心+basic_string 判断字典序

贪心的部分还能优化，懒得写了。

#include <bits/stdc++.h>
using namespace std;
int n, m;
// ee[i][j] 存 i j 之间是1否0是敌人
basic_string<bool> ee[105];
// 记录答案
int ansCnt;
basic_string<bool> ans;
// 贪心排列
mt19937 rnd(time(0));
int a[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        ee[i].resize(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        ee[u][v] = true;
        ee[v][u] = true;
    }

    ansCnt = 0;
    ans.resize(n + 1, false);
    for (int i = 1; i <= n; i++)
        a[i] = i;
    for (int i = 1; i <= 200000; i++)
    {
        shuffle(a + 1, a + n + 1, rnd);
        // 用 a 来生成一个选择方案
        int nowCnt = 0;
        basic_string<bool> now(n + 1, false);
        for (int i = 1; i <= n; i++)
        {
            // 尝试选择 a[i];
            bool flag = true;
            for (int j = 1; j < i; j++)
                if (now[a[j]] && ee[a[j]][a[i]])
                {
                    flag = false;
                    break;
                }
            if (flag)
            {
                now[a[i]] = true;
                nowCnt++;
            }
        }
        if (nowCnt > ansCnt ||
            nowCnt == ansCnt && now > ans)
        {
            ansCnt = nowCnt;
            ans = now;
        }
    }
    cout << ansCnt << "\n";
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}