讲解视频在b站。

试题H：修改数组

#include <cstdio>

using namespace std;

const int N = 100010, M = 1100010;

int n;
int p[M];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i < M; i ++ ) p[i] = i;

    for (int i = 1; i <= n; i ++ )
    {
        int a;
        scanf("%d", &a);
        a = find(a);
        printf("%d ", a);
        p[a] = a + 1;
    }

    return 0;
}

试题I：糖果

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100, M = 20;

int n, m, k;
int package[N], f[1 << M];
vector<int> candy[M];
bool st[M];

int h(int state)
{
    int res = 0;
    for (int s = (1 << m) - 1 - state; s; s -= s & -s)
    {
        int i = f[s & -s];
        res ++ ;
        for (auto p : candy[i])
            s &= ~package[p];
    }
    return res;
}

bool dfs(int u, int state)
{
    if (!u || u < h(state))
    {
        if (state == (1 << m) - 1) return true;
        return false;
    }

    int c = -1;
    for (int s = (1 << m) - 1 - state; s; s -= s & -s)
    {
        int i = f[s & -s];
        if (c == -1 || candy[c].size() > candy[i].size())
            c = i;
    }

    for (auto p : candy[c])
        if (dfs(u - 1, state | package[p]))
            return true;

    return false;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i ++ ) f[1 << i] = i;
    for (int i = 0; i < n; i ++ )
    {
        memset(st, false, sizeof st);
        for (int j = 0, t; j < k; j ++ )
        {
            cin >> t;
            st[t - 1] = true;
        }
        for (int j = 0; j < m; j ++ )
            if (st[j])
            {
                package[i] += 1 << j;
                candy[j].push_back(i);
            }
    }

    int t;
    for (t = 0; t <= m; t ++ )
        if (dfs(t, 0))
            break;

    if (t > m) t = -1;
    cout << t << endl;

    return 0;
}