欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

简要版

这场参与的人数不是很多，可能和8:30开始有点关系。跟着榜单打的，有几题的题面还是来不及看。

非出题人，单纯从 做题人 的视角，简单写下流水账题解。

A. 鸭鸭

目标值要么为全0，要么为全1，求最小操作数

这题的难点在于，负数的原码

其实就是 负数的绝对值，然后额外高位置1

令 f(x)为 x二进制表示下1的个数

• 非负数， min(f(x), 32 - f(x))

• 负数， min(f(-x) + 1, 31 - f(-x))

B. 鸭鸭拆快递

完全背包板子题

C. 鸭鸭多分切片

这场唯一的意难平，看了题，但是不会做， T_T.

D. 鸭鸭好朋友Hunter的智慧数(easy version)

好不容易看懂题

= 1 (mod m), 根据裴蜀定理，gcd(i, m) = 1

因为m的质因子不超过8个

在2~m-1范围内，用容斥定律求解。

E. 鸭鸭好朋友Hunter的智慧数(hard version)

没看懂后面部分，真的太绕了。

F. 鸭鸭集

这题的关键是 长度不同

不同长度的方案数， 而不是不同方案总数

令A和B的交集E，A和B的并集F

那么 E <= S <= F

那S可能长度范围为[|E|, |F|]

即 |F| - |E| + 1

G. 鸭鸭解方程

这题的突破口，在于f(x)

因为f(x)为各个位数的累加和

以18位长度的整数为例， 最多18 * 9 = 162

因此枚举f(x)的可能值域

方程左侧 = x，最后验证一下x的f(x) 是否等于 e

考察一个逆向思维，正难则反

H. 鸭鸭の机关立方

关键词: 一维，区间操作

经典的差分应用题

这边可以归一化，顺时针+1, 逆时针+3,180度为+2

最后差分还原，判断一下是否为模4等于1

I. 鸭鸭完成作业

来不及看题

J. 鸭鸭语

数学题

分类讨论即可

• p = 0

  

• p = 100

  

• 0 < p < 100

  

K. 鸭鸭语录入

线性的状态机DP

令 opt[n][s], n为前n项，s为0,1表示

这边需要注意

这题的转移需要考虑当前要打的字母类型（数字，小写，大写）

大写锁定键关闭时，打大写字母，

• 可以 先按 大写锁定键，再按字母，
• 也可以 按 Shift

而大写锁定键打开时，打大写字母

• 可以直接打字母
• 也可以先关闭大写锁定键，再shift

打小写字母时，亦是如此。

这个状态转移挺绕的。

L. 鸭鸭与前辈的另一件遗留之物

灵光一现

因为整体gcd为1，但是两数彼此非互质

这样每个数必然是2个不同质数的乘积，可以反证证明

可以简单构造

a(i) = 2 * 3 * i

b(i) = 2 * 5 * i

c(i) = 3 * 5 * i

这3个序列（需要小于20000）

但是n=6000，这三个序列去重后数量不及6000。

那怎么办呢？

在n>=5000时，可以引入更多的质数

a(i)=2 * 3 * i

b(i)=2 * 5 * i

c(i)=2 * 7 * i

d(i)=2 * 11 * i

e(i)=2 * 13 * i

f(i)= 3 * 5 * 7 * 11 * 13 * i

这6组序列，这样的话在20000范围内存在6000+的数

需要保证这6个数一定要在构造的序列里。

M. 鸭鸭做活动

限定条件下的最小值

一般用二分，因为验证比构造简单。

写在最后