STL例子

• 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 << " ";
}