[ABC200E] Patisserie ABC 2 题解

huangweiliang / 2024-10-16 / 原文

题目传送门

题目大意：

每个蛋糕有三个属性[$i$,$j$,$k$]，每个属性取值范围在[$1$,$n$]，以三个属性和为第一关键字，$i$ 为第二关键字，$j$ 为第三关键字排序，问第 $x$ 个蛋糕是啥？

解题思路：

大致思路是逐个确定其属性。

首先我们确定第 $x$ 个蛋糕的和是啥，我们记 $f_{i}$ 表示和为 $i$ 的蛋糕个数，怎么算 $f_{i}$ 呢？

可以想到插板法，但是注意到每个属性有取值范围，这就不能直接插板法，那么怎么处理呢，我们考虑容斥。

那么 $f_{i}$ 就等于全部的方案，减去有一个属性超出 $n$ 的方案数，加上有两个属性超出 $n$ 的方案数，减去三个属性都超出的方案数。

$f_{i}=C_{i-1}^{2}-C_{3}^{1}\times C_{i-n-1}^{2}+C_{3}^{2}\times C_{i-2\times n-1}^{2}-C_{i-3\times n-2}^{2}$

$\text{Tips:}$ 这里三个属性不可能都超出，所以可以不用减去三个属性都超出的方案数。

那么我们确定了第 $x$ 个蛋糕的和 $sum$，我们确定 $i$ 属性的值。

思考对于每个 $i$ 值，$j$ 的取值范围是多少？

因为 $i$ 值确定，$k$ 的取值范围是 $1 \leq j \leq n$，那么 $j$ 的取值范围不就是 $max(1,sum-i-n)\leq j \leq min(n,sum-i-1)$。

那么我们就能够确定 $i$ 值，$j$ 值，这时候 $k$ 值是唯一的。

所以就解决了。

代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e6 + 10;
ll f[N];
ll C(ll n, ll m){//因为m永远是2所以可以化简
    if(n < m) return 0;
    return n * (n - 1) / m;
}
int main(){
    // freopen("cake.in", "r", stdin);
    // freopen("cakxe.out", "w", stdout);
    ll n, x;
    cin >> n >> x;
    for(int i = 1; i <= 3 * n; i++)//对上述式子有所化简
        f[i] = C(i - 1, 2) - 3 * C(i - n - 1, 2) + 3 * C(i - 2 * n - 1, 2);
    ll sum = 0;
    for(int i = 1; i <= 3 * n; i++){
        if(x <= f[i]){
            sum = i;
            break;
        }
        x -= f[i];
    }
    for(ll i = 1; i <= n; i++){
        ll l = max(1ll, sum - i - n), r = min(n, sum - i - 1ll);
        if(l > r)
            continue;
        else{
            if(x <= r - l + 1){//这里确定了i和j，k就能直接算出来
                cout << i << " " << l + x - 1 << " " << sum - i - l - x + 1 << endl;
                break;
            }
            x -= r - l + 1;
        }
    }
    return 0;
}