题解：AT_abc200_e [ABC200E] Patisserie ABC 2

· · 题解

AT_abc200_e 解题报告

前言

感觉不应该放在 E。有点困难其实。

思路分析

这种大范围查找题应该有一个固定的套路：逐个确定。

具体地，可以先计算出 i+j+k 的值，再依次计算出 i,j,k 的值。

计算 i+j+k

考虑怎样快速计算 i+j+k 的值。

设 f_d 表示满足 i+j+k=d 的三元组 (i,j,k) 的个数。

只要能快速计算 f 的值，就可以在 O(n) 的复杂度内计算出任何一个三元组的 i+j+k 的值。扫一遍 f 就行。

考虑怎样快速计算 f。

先不考虑 i\le n,j\le n,k\le n 的限制，用插板法解决，答案显然为f_d=\binom{d-1}{2}。

再考虑限制，发现限制可以容斥解决。

具体地：

f_d=\binom{d-1}{2}-3 \cdot \binom{d-n-1}{2}+3 \cdot \binom{d-2n-1}{2}-\binom{d-3n-1}{2}

解释就是全集 - 有一个超出限制 + 有两个超出限制 - 有三个超出限制。

需要熟练应用插板法。

计算 i,j,k

仿照上例，可以枚举 i，统计合法三元组 (i,j,k) 的个数，这样做也是 O(n) 的。

对于每一个 i 和之前求出的 sum=i+j+k，有：

j\in [\max(1,sum-1-n),min(n,sum-1-i)]

都来切蓝了，应该会解不等式组吧。

然后对于每一个 i，三元组的数量就是合法的 j 的数量，因为 k 此时是唯一确定的。

然后就做完了。

整体复杂度为 O(n)。

代码实现

注意容斥时出现负数的情况，判掉就行。


#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,num,ans_sum,ansi,ansj,ansk; 
int f[3000005];
void get_sum(){
    for(int i=3;i<=3*n;i++){
        if(k>f[i]) k-=f[i];
        else{
            ans_sum=i;
            break;
        }
    }
}
void get_ijk(){
    for(int i=1;i<=ans_sum-2;i++){
        int l=max(1ll,ans_sum-i-n),r=min(n,ans_sum-i-1);
        if(l>r) continue;
        if(k>r-l+1){
            k-=r-l+1;
        }else{
            ansi=i;
            ansj=l+k-1;
            ansk=ans_sum-ansi-ansj;
            break;
        }
    }
}
int c(int x){
    if(x<=2) return 0;
    return (x-1)*(x-2)/2;
}
signed main(){
    cin>>n>>k;
    for(int i=3;i<=3*n;i++){
        f[i]=c(i)-3*c(i-n)+3*c(i-2*n)-3*c(i-3*n);
    }
    get_sum();
    get_ijk();
    cout<<ansi<<' '<<ansj<<' '<<ansk;
    return 0;
}