ABC200 E 题解

ktq_cpp · 2023-01-01 18:12:38 · 题解

Problem E

对于这道题目，我们可以先算出第 k 个蛋糕是在和为多少的序列中，然后再算出是在美丽值的值，最后确定美味程度。

我们可以令 dp[i][j] 表示在和为 i 的情况下确定 j 个元素的方案数，不难想出，我们要确定第 k 个蛋糕所在的三元组之和，要找到的就是第一个 sum 使得 \sum_{i=1}^{sum}dp[i][3]>k 第一个数等后面的同理。

这道题目整个的思路都是顺其自然的，写代码时需要注意些细节即可。

#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int dp[3000005][4];
int sum[3000005][4];
int n,k,num,fi,se;
signed main(){
    n=read(),k=read();
    rep(i,n)dp[i][1]=1,sum[i][1]=i;
    repe(i,2,2*n){
        dp[i][2]=sum[min(i-1,n)][1]-sum[max(i-n,1ll)-1][1];
        sum[i][2]=sum[i-1][2]+dp[i][2];
    }
    repe(i,3,3*n){
        dp[i][3]=sum[min(i-1,2*n)][2]-sum[max(i-n,2ll)-1][2];
        sum[i][3]=sum[i-1][3]+dp[i][3];
    }
    for(num=3;num<=3*n;num++){
        if(k>dp[num][3])k-=dp[num][3];
        else break;
    }
    for(fi=1;fi<=num-2;fi++){
        if(k>dp[num-fi][2])k-=dp[num-fi][2];
        else break;
    }
    for(se=1;se<=num-1-fi;se++){
        if(num-fi-se>=1&&num-fi-se<=n&&k)--k;
        if(!k)break;
    }
    cout<<fi<<' '<<se<<' '<<num-fi-se<<endl;
    return 0;
}