题解 | #2023年安徽大学ACM实验室新生赛 题解报告#
鸭鸭
https://ac.nowcoder.com/acm/contest/70500/A
欢迎关注
简要版
这场参与的人数不是很多，可能和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. 鸭鸭做活动
限定条件下的最小值
一般用二分，因为验证比构造简单。
美的集团公司福利 135人发布