链接：https://codeforces.com/contest/2160

A. MEX Partition

算法：

    贪心。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        s.insert(x);
    }

    int now = 0;
    while (s.find(now) != s.end())
        ++now;

    cout << now << endl;
}

B. Distinct Elements

算法：

    贪心，数学。

思路：

    无。

关键代码：

void miyan()
{
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    for (ll i = 1; i <= n; ++i)
        cin >> a[i];

    ll cur = 1;
    vector<ll> ans(n + 1, 0);
    ans[1] = cur;
    for (ll i = 2; i <= n; ++i)
    {
        if ((a[i] - a[i - 1]) == i)
            ans[i] = ++cur;
        else
            ans[i] = ans[i - a[i] + a[i - 1]];
    }

    for (ll i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
}

C. Reverse XOR

算法：

    打表。

思路：

    要想满足二进制 \(1\) 的个数需要为偶数。

    二进制是回文串的必然可以。

    可以通过添加前导 \(0\) 变成回文串的也可以。

关键代码：

void miyan()
{
    ll n;
    cin >> n;

    ll x = n;
    string s;
    ll cnt = 0;
    while (x)
    {
        if (x % 2)
            ++cnt;
        s.push_back(x % 2 + '0');
        x /= 2;
    }

    reverse(all(s));

    if (cnt & 1)
    {
        cout << "NO" << endl;
        return;
    }

    string ans = s;
    while (s.back() == '0')
    {
        ans = '0' + ans;
        s.pop_back();
    }

    for (int i = 0, j = ans.size() - 1; i < j; ++i, --j)
    {
        if (ans[i] != ans[j])
        {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

D. MAD Interactive Problem

算法：

    交互。

思路：

    先用 \(2n\) 次询问问出来 \(n\) 个位置。

    怎么问。

    对 \(2n\) 个位置依次询问。对于当前询问的下标集合，其答案为 \(0\)，在加入下一个位置 \(p\) 后，其答案不为 \(0\)，说明 \(p\) 位置的答案就问询问返回的答案，此时将集合中移去 \(p\) 下标，继续询问，这样在询问 \(2n\) 次后，可以将每个数字第二次出现的位置确认。

    再逆序遍历对剩余 \(n\) 个位置询问即可。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    auto query = [&](vector<int> a) -> int
    {
        cout << "? " << a.size() << ' ';
        for (auto x : a)
            cout << x << ' ';
        cout << endl;

        int t;
        cin >> t;
        return t;
    };

    vector<int> ans(n + n + 1, 0);
    vector<int> res;
    for (int i = 1; i <= n + n; ++i)
    {
        res.push_back(i);
        int p = query(res);
        if (p)
        {
            ans[i] = p;
            res.pop_back();
        }
    }

    res.clear();

    for (int i = n + n; i >= 1; --i)
    {
        res.push_back(i);

        if (ans[i])
            continue;

        int p = query(res);
        if (p)
        {
            ans[i] = p;
            res.pop_back();
        }
    }

    cout << "! ";
    for (int i = 1; i <= n + n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
}

E. Rectangles

    还没补。