题解：P12256 [蓝桥杯 2024 国 Java B] 数据库

· · 题解

简化题意

共有 N 次 INSERT 和 DELETE 操作，保证 INSERT 一定在 DELETE 前，且有 DELETE 必定有 INSERT，而 INSERT 可以单独存在。求合法方案的顺序数。

思路

将这 N 次操作分成两类。一类有完整插入和删除操作，另一类仅有插入操作。

首先看插入和删除操作完整的一类。设有 m 组完整操作配对。尝试将这 m 组操作一组组插入。

插入第 1 组，方案显然只有 1 种。

插入第 2 组，相当于在 4 个位置中，选择 2 个插入第二组的两个操作，方案数为 \binom{4}{2}。

插入第 3 组，同理，相当于在 6 个位置，认为另 4 个顺序固定，选择 2 个插入，方案数为 \binom{6}{2}。\binom{6}{2} 是仅考虑第 3 组有几种插入方式，再乘上另 4 个位置的组合，即前 2 组的组合数，即得插入到第 3 组时的总方案数。

于是，这 m 组操作的总方案数为：

\prod_{i=1}^m \binom{2i}{2}

再看仅有插入操作的一类。设该类操作有 k 个。考虑在计算完第一类操作的情况下，插入这 k 个操作。其中 2m+k=N。

与第一类相似，这 k 个操作可以看做在 n 个位置中，固定第一类 2m 个操作的次序，选择 k 个插入。由于这 k 个操作不需要考虑任何顺序。因此，该类操作的方案数为：\mathrm{A}_n^k。

两类操作方案相乘即得最终答案。

Code

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

const int N = 1e6 + 10;
const int MOD = 1e9 + 7;
unordered_map<int,int> mp;
long long sum[N];
long long C[N][10]; //组合数

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //组合数递推
    for (int i = 0 ; i <= 1e6 ; i++) C[i][0] = 1;
    for (int i = 1 ; i <= 1e6 ; i++)
    {
        for (int j = 1 ; j <= min(2,i) ; j++)
        {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] %= MOD;
        }
    }

    int n;
    cin >> n;
    int m = 0; //完整操作组数
    for (int i = 1 ; i <= n ; i++)
    {
        string type;
        cin >> type;
        if (type == "INSERT")
        {
            int x,y;
            cin >> x >> y;
            mp[x]++;
        }
        else
        {
            int x;
            cin >> x;
            mp[x]--;
            m++;
        }
    }

    long long ans = 1;
    int k = 2;

    //计算完整操作的组合数
    for (int i = 1 ; i <= m ; i++)
    {
        ans *= C[k][2];
        k += 2;
        ans %= MOD;
    }

    //计算insert的排列数
    for (int i = 2*m+1 ; i <= n ; i++)
    {
        ans *= i;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}