当前位置: 首页 > news >正文

AT_abc200_e [ABC200E] Patisserie ABC 2 题解

(麦口乐在跑步的时候随手就把这道题切了,吓哭了%%%)

直接按题意排序显然会因为蛋糕数量爆多而gg,注意到蛋糕排序的第一关键字是三个维度的总和,而这个总和的范围是相对小的,考虑对每个总和分别计算蛋糕的方案数量。

假设 \(i+j+k=s\),我们可以简单使用插板法 \(\large \binom{s-1}{2}\)\(s\) 分成三个数,但 \(i,j,k \leq n\) 的限制没有被满足。

考虑容斥,强制一个、两个、三个维度的条件不被满足,再做插板,设总和为 \(s\) 的蛋糕数量为 \(f[s]\)

\[f[s]=\binom{s-1}{2}-3\times \binom{s-n-1}{2}+3\times \binom{s-2n-1}{2}-3\times \binom{s-3n-1}{2} \]

依次枚举维度总和,用其蛋糕数量和 \(x\) 比较,这样就能找出第 \(x\) 个蛋糕的维度和是多少,再进一步去确定 \(i,j,k\) 分别是多少即可,我们可以枚举 \(i\),此时 \(j\) 的取值处在 \([\max(1,s-i-n),\min(n,ans-i-1)]\) 的区间里,原因可以考虑 \(k\) 取到最大和最小的情况。有了 \(j\) 的区间其实也就是知道了此时蛋糕的数量,再和 \(x\) 进行比较,最终确定位置即可。

点击查看代码
const int N=1e6+5;
int f[N*3];
int n,k,ans_sum,ansi,ansj,ansk;
int c(int x){if(x<=2) return 0;return (x-1)*(x-2)/2;
}
void xpigeon(){rd(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);}for(int i=3;i<=3*n;i++){if(k>f[i]) k-=f[i];else{ans_sum=i;break;}}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;}}cout<<ansi<<" "<<ansj<<" "<<ansk<<'\n';
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);xpigeon();return 0;
}
http://www.hskmm.com/?act=detail&tid=13747

相关文章:

  • 日总结 5
  • Linux驱动开发(1)概念、环境与代码框架 - 实践
  • Diffutoon下载介绍:真人视频转动漫工具,轻松获得上千点赞
  • 9月22号
  • 0.5*8 边形 != 式
  • 题解:AT_agc052_c [AGC052C] Nondivisible Prefix Sums
  • 寻路算法
  • 2025年9月22日 - 20243867孙堃2405
  • day 1
  • [Paper Reading] METAGPT: META PROGRAMMING FOR A MULTI-AGENT COLLABORATIVE FRAMEWORK
  • 二进制 - 20243867孙堃2405
  • 学习问题日记-1
  • 记一次生产环境内存溢出记录
  • 四舍六入五成双
  • 借助 Apache Phoenix,使用标准 SQL 和 JDBC 接口来操作 HBase
  • 学生信息管理系统
  • 如何让AI生成多页面APP原型图?AI原型设计实用指南
  • 代码随想录算法训练营第五天 | leetcode 242 349 202 1
  • CF2146 Codeforces Round 1052 (Div. 2) 游记
  • 原码补码反码与位操作
  • 接口
  • 特殊句式
  • 9月22日
  • 20250922
  • 易路斩获招聘、薪酬两大重磅人力资源奖项,尽显行业领军风范!
  • 作业
  • RAG系统嵌入模型怎么选?选型策略和踩坑指南
  • (应该写的比较清晰)D2. Max Sum OR (Hard Version)
  • Linux运维
  • day001