概述

	A. 约瑟夫问题	B. 宝藏勘探	C. 记忆游戏	D. 组合扑克
涉及知识点	模拟，链表	前缀和，枚举	数据结构，线段树，平衡树	记忆化搜索，动态规划

题解报告

tips:如果有不懂的地方可以在评论区留言.

A. 约瑟夫问题

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> next(n + 1), pre(n + 1);
    for(int i = 1; i <= n; i ++)
    {
        next[i] = i + 1;
        if(next[i] == n + 1) next[i] = 1;
        pre[i] = i - 1;
        if(pre[i] == 0) pre[i] = n;
    }
    int p = 0;
    next[0] = 1;
    while(next[p] != p)
    {
        for(int i = 0; i < m; i ++) p = next[p];
        next[pre[p]] = next[p];
        pre[next[p]] = pre[p];
        cout << p << ' ';
    }
}

B. 宝藏勘探

我们注意到，中间一定有 $k$ 个点无法探测，我们钦定 $p \sim p+k-1$ 为没有探测到的区间，那么我们本次探测的答案即为：

$$f(p) = \max(\max_{i=1}^{p-1}a_i, \max_{i=p+k+1}^{n}a_i) - \min(\min_{i=1}^{p-1}a_i, \min_{i=p+k+1}^{n}a_i)$$

那么答案即为：

$$ans = \min_{i=1}^{n-k+1}f(i)$$

同时，对于快速求解 $f(i)$，我们可以预处理出前缀最小值和前缀最大值以及后缀最大值和后缀最小值即可 $O(1)$ 求解，那么最后总的复杂度极为 $O(n)$。

signed main()
{
    IOS;
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), premax(n + 1), premin(n + 1), sufmax(n + 2), sufmin(n + 2);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    premin[0] = 1e9;
    premax[0] = -1e9;
    for(int i = 1; i <= n; i ++)
    {
        premin[i] = min(a[i], premin[i - 1]);
        premax[i] = max(a[i], premax[i - 1]);
    }
    sufmax[n + 1] = -1e9;
    sufmin[n + 1] = 1e9;
    for(int i = n; i >= 1; i --)
    {
        sufmax[i] = max(a[i], sufmax[i + 1]);
        sufmin[i] = min(a[i], sufmin[i + 1]);
    }
    int ans = 1e9;
    for(int i = 1; i + k + 1 <= n; i ++)
    {
        int mx = max(premax[i], sufmax[i + k + 1]);
        int mi = min(premin[i], sufmin[i + k + 1]);
        ans = min(ans, mx - mi);
    }
    cout << ans << '\n';
    return 0;
}

C. 记忆游戏

乍眼一看，本题似乎是一个线段树的板子题，但是实际上考虑用线段树维护的时候，发现要维护的tag非常多，而且在做tagunion的时候，需要考虑很多情况（超级大分讨）。因此我们换个角度思考，打破思维定势。

这里我们可以考虑采用平衡树来维护，因为平衡树可以方便的维护区间信息，而且可以方便的查询区间信息。我们以序列作为平衡树的中序遍历，维护两颗平衡树，一颗维护所有的奇数，一颗维护所有的偶数。

考虑维护区间修改，我们钦定这里是对区间内所有奇数修改(偶数只需要做镜像操作即可)，我们每次给区间 $[l,r]$ 中所有的奇数加上一个值 $d$，假设 $d$ 是偶数，那么区间内所有数的奇偶性不会发生改变，我们只需要将 $[l,r]$ 给split出来，给分裂出的子树的根打上tag即可。最后再merge回去就好了。重点在于，倘若 $d$ 为奇数，这样区间中所有数的奇偶性就会发生改变，这也是线段树维护的最大难点，但是平衡树可以很好的解决这个问题，假设 $d$ 为奇数，那么前面的操作都完全一致，直到将 $[l,r]$ split出来之后，我们直接合并奇数平衡树剩下的两个子树，然后只需要将 $[l,r]$ 合并到偶数平衡树即可。这样做最大的优点在于，我们规避了奇偶性对区间修改带来的影响，因此最后只需要维护一个add的tag即可。

那么查询就很简单了，每次查询 $[l,r]$，只需要同时将 $[l,r]$ 从奇数树和偶数树split出来，然后两者的sum相加即可。

本题还有一点难点就是在split和merge的时候，需要注意处理标记信息，及时pushup和pushdown。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int N = 5e5 + 10;

random_device rd;
mt19937 rng(rd());

struct Node
{
    int l, r;
    int pos, siz;
    unsigned key;
    i64 sum, val, tag;
}tr[N];

int n, m;
int root_odd, root_eve;

void create(int pos)
{
    Node &rt = tr[pos];
    rt.l = rt.r = rt.val = 0;
    rt.sum = rt.tag = 0;
    rt.siz = 1;
    rt.pos = pos;
    rt.key = rng();
}

void pushup(int p)
{
    tr[p].siz = tr[tr[p].l].siz + tr[tr[p].r].siz + 1;
    tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum + tr[p].val;
}

void tagunion(int p, i64 d)
{
    tr[p].sum += tr[p].siz * d;
    tr[p].val += d;
    tr[p].tag += d;
}

void pushdown(int p)
{
    if (tr[p].tag)
    {
        tagunion(tr[p].l, tr[p].tag);
        tagunion(tr[p].r, tr[p].tag);
        tr[p].tag = 0;
    }
}

void split(int u, int p, int &x, int &y)
{
    if (u == 0)
    {
        x = 0, y = 0;
        return;
    }
    pushdown(u);
    if (tr[u].pos <= p)
    {
        x = u;
        split(tr[u].r, p, tr[u].r, y);
    }
    else
    {
        y = u;
        split(tr[u].l, p, x, tr[u].l);
    }
    pushup(u);
}

// 相同树 左右子树的合并
int merge(int x, int y)
{
    if (x == 0 || y == 0)
    {
        return x + y;
    }
    if (tr[x].key < tr[y].key)
    {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else
    {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

// 不同树的merge
int mergeTree(int x, int y)
{
    if (x == 0 || y == 0)
    {
        return x + y;
    }
    if (tr[x].siz < tr[y].siz)
    {
        swap(x, y);
    }

    int l, r;
    split(y, tr[x].pos, l, r);
    pushdown(x);
    tr[x].l = mergeTree(tr[x].l, l);
    tr[x].r = mergeTree(tr[x].r, r);
    pushup(x);
    return x;
}

void modify(int l, int r, int o, i64 d)
{
    int x, y, z;
    if (o == 0)
    {
        split(root_eve, l - 1, x, y);
        split(y, r, y, z);
        tagunion(y, d);
        if (d & 1)
        {
            root_eve = merge(x, z);
            root_odd = mergeTree(root_odd, y);
        }
        else
        {
            y = merge(y, z);
            root_eve = merge(x, y);
        }
    }
    else
    {
        split(root_odd, l - 1, x, y);
        split(y, r, y, z);
        tagunion(y, d);
        if (d & 1)
        {
            root_odd = merge(x, z);
            root_eve = mergeTree(root_eve, y);
        }
        else
        {
            y = merge(y, z);
            root_odd = merge(x, y);
        }
    }
}

i64 query(int l, int r)
{
    int x, y, z;
    i64 ans = 0;
    split(root_odd, l - 1, x, y);
    split(y, r, y, z);
    ans += tr[y].sum;
    y = merge(y, z);
    root_odd = merge(x, y);
    split(root_eve, l - 1, x, y);
    split(y, r, y, z);
    ans += tr[y].sum;
    y = merge(y, z);
    root_eve = merge(x, y);
    return ans;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        create(i);
        root_eve = merge(root_eve, i);
    }
    int op, l, r, o, d;
    for (int i = 1; i <= m; i++)
    {
        cin >> op >> l >> r;
        if (op == 1)
        {
            cin >> o >> d;
            modify(l, r, o, d);
        }
        else
        {
            i64 ans = query(l, r);
            cout << ans << "\n";
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

D. 组合扑克

注意到一些事实：

• 花色对本题没有任何影响。因此，我们只需要考虑牌面数字。
• 由于存在对子和飞机，因此根据裴蜀定理，我们可以凑出的数字 $n$ 满足 $2x + 3y = k \gcd(2,3)$，同时对子和飞机数不能为负数，因此还要满足 $x,y \ge 0$，因此，实际上，得出一个重要结论：所有牌只有在单张的时候才无法被组合。这也是顺子的意义：凑掉对子和飞机无法组合的单张，且最重要的是，每个顺子只需要凑一次，只有第一次是有意义的。
• 本题只需要计算点数小于 $A$ 的牌的剩余数量。因此可以引申出如下几个结论：
• • 大王小王根本没意义，直接舍弃
• • 在凑顺子时，由于 $A$ 可以看作 $1$ 和 $n + 1$，因此我们应该分开讨论这些情况。
• • 最后对答案的统计实际上就是计算小于点数 $A$ 且数量刚好等于 $1$ 的牌的数量。

那么实际上，本题就变成了，求出所有可以凑的顺子，然后搜索他们凑和不凑的情况，每次更新答案即可。这样的做法是 $O(2^n)$ 的，显然会超时。只能过 $50\%$ 的样例。

50分的代码：

int main()
{
    int n, m;
    cin >> n >> m;
    string s;
    getchar();
    while (getline(cin, s))
    {
        mp.clear();
        int num = 0;
        stringstream ss(s);
        string suit, val;
        while(ss >> suit >> val)
        {
            if(val == "A") mp[n + 1]++;
            else mp[stoi(val)]++;
        }
        auto check = [&](int x)
        {
            if(x + 4 > n + 1) return 0;
            int res = 1;
            for(int i = 0; i < 5; i ++) res &= (mp[x + i] > 0);
            return res;
        };
        int ans = 1e9;
        auto dfs = [&](auto &&self, int u) -> void
        {
            if(u > n)
            {
                int sum = 0;
                for(int i = 3; i <= n; i ++)
                {
                    sum += (mp[i] == 1);
                }
                ans = min(ans, sum);
                return;
            }
            if(check(u)) 
            {
                for(int i = 0; i < 5; i ++) mp[u + i] --;
                self(self, u + 1);
                for(int i = 0; i < 5; i ++) mp[u + i] ++;
            }
            self(self, u + 1);
        };
        dfs(dfs, 2);
        if(mp[n + 1] > 0)
        {
            mp[n + 1] --;
            mp[1] ++;
            dfs(dfs, 1);
        }
        cout << ans << '\n';
    }
    return 0;
}

那么既然dfs已经出来了，我们考虑优化。注意到，我们假设选了点数 $p$ 开头的顺子，那么实际上他会影响到 $p+1,p+2,p+3,p+4$ 这四种点数牌的数量，因此，我们可以记 $dp[i][j_4][j_3][j_2][j_1][j_0]$ 表示在点数为 $i$ 状态为 $[j_k]$ 剩余牌的数量，其中，$j_k \in \{0,1\}$，表示是否打出了 $p + k + 4$ 的顺子。这里我们采用状态压缩来表示后面的 5个 表示状态的维度，即$(j_4 \ j_3 \ j_2 \ j_1 \ j_0)_2$，其中 $j_k = 1$ 表示打出了 $[i + k, i + k + 1, i + k + 2, i + k + 3, i + k + 4]$ 的顺子，$j_k = 0$ 表示没有打出。那么转移方程为：

假设当前当前点数 $i$ 的数量为 $n$，状态为 $status$，其状态中含有 $1$ 的数量为 $cnt$:

• $dp[i][status] = \min(dp[i-1][status / 2], dp[i-1][status / 2 + 16]) + 1$，当 $n - cnt = 1$。
• $dp[i][status] = \inf$，当 $n - cnt < 0$
• $dp[i][status] = \min(dp[i-1][status/2], dp[i-1][status/2 + 16])$，当 $n - cnt > 1$

最后，由于 $A$ 既可以当 $1$ 又可以当 $n + 1$，而且他们组合的顺子都是唯一的，我们直接做两次dp即可，分别取一张 $A$ 作为 $1$ 或者 $n + 1$，最后答案就是两次dp的答案取最小值。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int dp[N][32]; // dp[n][0/1][0/1][0/1][0/1][0/1]
map<int, int> mp;

int solve(int n)
{
    for (int j = 0; j < 32; j++)
        dp[n + 2][j] = 0;
    for (int i = n + 1; i >= 1; i--)
        for (int j = 0; j < 32; j++)
        {
            int tmp = j, cnt = 0;
            while (tmp)
            {
                if (tmp & 1)
                    cnt++;
                tmp /= 2;
            }
            if (mp[i] - cnt < 0 || j >= (1 << min(n + 2 - i, 5)))
                dp[i][j] = 1e9;
            else if (i != n + 1 && i != 2 && i != 1 && mp[i] - cnt == 1)
                dp[i][j] = min(dp[i + 1][j / 2], dp[i + 1][j / 2 + 16]) + 1;
            else
                dp[i][j] = min(dp[i + 1][j / 2], dp[i + 1][j / 2 + 16]);
        }
    return min(dp[1][0], dp[1][16]);
}

int main()
{
    int n, m;
    cin >> n >> m;
    string s;
    getchar();
    while (m--)
    {
        getline(cin, s);
        mp.clear();
        int num = 0;
        stringstream ss(s);
        string suit, val;
        while(ss >> suit >> val)
        {
            if(suit == "R" or suit == "B") continue;
            if(val == "A") mp[n + 1]++;
            else mp[stoi(val)]++;
        }
        int ans = solve(n);
        if (mp[n + 1] >= 1)
        {
            mp[n + 1]--;
            mp[1]++;
            ans = min(ans, solve(n));
        }
        cout << ans << endl;
    }
    return 0;
}