Educational Codeforces Round 127 (Rated for Div. 2) 题解A-E
2022/4/23 6:16:04
本文主要是介绍Educational Codeforces Round 127 (Rated for Div. 2) 题解A-E,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A. String Building
长度为\(2\)和\(3\)的可以构造出任何长度大于等于\(2\)的,所以将原序列分割成多段字符相同的极大子串,如果存在长度为1的则无解,反之有解。
B. Consecutive Points Segment
枚举第一个元素,然后就可以贪心了,具体就是\(x_{i - 1}\)确定了,那么把\(x_{i}\)搞成\(x_{i - 1} + 1\)会是最优的。
这样每次线性check是否可行就可以了。
C. Dolce Vita
肯定是贪心买便宜的更优,然后由于价钱会上涨,所以购买的顺序应该是零或多次买\(n\)个物品,零或多次买\(n - 1\)个物品,以此类推。
然后就模拟一下,朴素模拟肯定会TLE,把多次购买相同数量物品的操作,合并成一次就可以\(O(n)\)搞了。
D. Insert a Progression
不插入的初始代价遍历一遍就能算出来。
如果原序列中存在两个相邻元素,其中较小的为\(l\),较大的为\(r\),那么\([l, r]\)就可以不花费代价插入这两个元素之间。
假设全局最小元素为\(mi\),全局最大元素为\(ma\),易得现在只剩下\([1, mi)\)和\((ma, x]\)没有插入了,前者其实相当于在序列中插入\(1\),后者相当于在序列中插入\(x\),因为其余元素都可以在插入这两个元素之后不花费代价的插入。
分别线性枚举然后算最小代价增量,最后再加到答案上即可。
E. Preorder
在原树中自底向上DP。
叶子节点\(x\)的方案数\(dp_x = 1\)。
对于非叶子节点\(x\),如果\(f(l_x) = f(r_x)\),则\(dp_x = dp_{l_x} * dp_{r_x}\),否则\(dp_x = 2 * dp_{l_x} * dp_{r_x}\)。
写了个\(O(n \log n)\)的代码就过了。
F. Permutation Counting
TBA。
这篇关于Educational Codeforces Round 127 (Rated for Div. 2) 题解A-E的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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自动完成!