牛客练习赛121

BrotherCall · 2024-01-27 12:56:09 · 个人记录

i这场本来打算养生打的，结果发现了自身的一些问题。

[A] 小念吹气球

拿桶存一手是否是第一次出现来计算答案。

[B] You Brought Me A Gentle Breeze on the Field

直觉告诉我能多操作一次的人可以通过 “拉扯” 实现必胜。

所以特判一下 A 上来就输，以及 A 取一次让 B 直接输的情况就行了。

[C] 氧气少年的水滴 2

很普通的小模拟，但我没想明白就开写，导致磨了很久，深刻反思！！！

[D] 氧气少年的 LCM

一眼就找到思路了，因为前两天打了 CF1922E 。

由于 \text{lcm} 一定是 \gcd 的若干倍，所以我们直接拿 \gcd 倍增就行了，非常板不多说了。

[E] 氧气少年逛超市 3

也是非常之没有难度。

不难发现一定是最贵的 x+y 个商品用券，而且一定是商品从贵到便宜，按折扣券数值从小到大，立减券数值从大到小，来用券。

设 f_{i,j} 代表 前 i 贵的商品中用了 j 个折扣券的最小代价。这么设状态隐藏了一个条件就是立减券用了 (i - j) 个。