ABC081B - Shift only - 题目列表

题意

$N$ 个正整数，每次操作将所有偶数除以 2。求最大操作次数。

思路

对每个数计算能除以 2 的次数（即二进制末尾 0 的个数， $\nu_2$ ），取最小值即为答案。

代码

haskell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20{-
 Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 rainboy的学习导航网站: https://idx.roj.ac.cn
 create_at: 2026-07-10 10:24
 update_at: 2026-07-10 10:24
-}

-- 二进制末尾0的数量 : lowbit
--

-- 递归函数

calc2 n = if even n then 1 + calc2 (n `div` 2) else 0

main = do
    n <- getLine
    str <- getLine
    let x = map read . words $ str :: [Int]
    print $ minimum $ map calc2 x

另一种写法，使用 getContents 一次读完输入：

haskell

1
2
3
4
5
6
7
8
9
10
11
12
13
14{-
 Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 rainboy的学习导航网站: https://idx.roj.ac.cn
 create_at: 2026-07-10 10:09
 update_at: 2026-07-10 10:09
-}
calc2 0 = 0
calc2 n = if even n then 1 + calc2 (n `div` 2) else 0

main = do
    input <- getContents
    let xs = map read (words input) :: [Int]
    print $ minimum $ map calc2 (tail xs)

复杂度

时间复杂度 $O(N \log A_{\max})$ ，空间复杂度 $O(1)$ 。

总结

$\nu_2$ 递归计算 + minimum 取最小值。两种输入方式：getLine 逐行读或 getContents 一次读完。

ABC081B - Shift only

目录

题意

思路

代码

复杂度

总结