CF587A Duff and Weight Lifting
2022/1/5 23:35:51
本文主要是介绍CF587A Duff and Weight Lifting,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
洛谷题面
较为简单,但还是因为细节问题挂了几发。
题目大意
有 \(n\) 个数 \(w_1,w_2,\cdots,w_{n-1},w_n\),若有 \(k\) 个 \(w\) 值满足存在一个数 \(x\) 使得 \(2^x\) 为这 \(k\) 个 \(2^w\) 的和,则这一组合是合法的,我们希望找到最小的组数 \(m\),使这 \(n\) 个 \(w\) 组成 \(m\) 个合法组合。
给出 \(n\) 和 \(w_i\),输出最小的 \(m\)。
题目分析
我们可以一步一步从低次幂向高次幂合并,\(k(k=2r \texttt{且 r 为整数})\) 个 \(2^x\) 可以合并为 \(\dfrac{k}{2}\) 个 \(2^{x+1}\)。
思路就出来了:
我们用一个桶 \(t_x\) 来记录每个数值 \(x\) 的个数。
但是如何记录答案呢?
我们发现上面只讨论了 \(k\) 为偶数的情况,所以若 \(k\) 为奇数,则取出 \(\left\lfloor\dfrac{k}{2}\right\rfloor\) 个 \(2^x\),剩下的 \(1\) 个则保留。
坑点:
-
因为更新是 \(t[i+1]\gets t[i+1]+\dfrac{t[i]}{2}\),所以可能会一直向上迭代更新,边界不一定是 \(i\le \max_w\)。
-
桶的大小要开到 \(10^6+50\),我最初习惯性开成了 \(10^6+5\),会 \(\frak{Wrong~Answer~On~Test~36}\)。
这是因为我们在向上时迭代时可能会不停向上更新,开到这儿就合适了。
代码
//2022/1/5const int ma=1e6+50; int t[ma]; int n; int ans,maxx; int main(void) { n=read(); for(register int i=1;i<=n;i++) { int x=read(); t[x]++; maxx=max(maxx,x); } for(register int i=0;i<=maxx || t[i]!=0;i++) { if(t[i]!=0) { t[i+1]+=t[i]/2; if(t[i]%2==1) { ans++; } } } printf("%d\n",ans); return 0; }
这篇关于CF587A Duff and Weight Lifting的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!