題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

CF2173D Taiga’s Carry Chains

Problem Statement

題目簡述

給定一個正整數 $n$ 和操作次數 $k$ 。
每次操作你可以選擇一個非負整數 $\ell$ ，並執行 $n \leftarrow n + 2^{\ell}$ 。
定義單次操作的分數為加法過程中產生的二進位進位次數。
求 $k$ 次操作後的最大總分數。

Constraints

約束條件

$1 \le n < 2^{30}$
$0 \le k \le 10^9$

思路

1. 轉化問題目標

首先觀察二進位加法中進位次數與 Popcount（二進位中 1 的個數）的關係。
令 $S(x)$ 為 $x$ 的二進位中 1 的個數。對於加法 $A + B$ ，設進位次數為 $C$ ，則滿足：

S(A+B) = S(A) + S(B) - C

移項可得單次操作的進位數：

C = S(n_{old}) + S(2^{\ell}) - S(n_{new}) = S(n_{old}) + 1 - S(n_{new})

將 $k$ 次操作的總分累加：

\text{Total Score} = \sum_{i=1}^k (S(n_{i-1}) + 1 - S(n_i))

\text{Total Score} = S(n_{initial}) + k - S(n_{final})

因此，要最大化總分，等價於最小化最終數值 $n_{final}$ 的二進位 1 的個數 $S(n_{final})$ 。

2. 貪婪策略與特殊情況

我們的目標是構造一個增量 $M = \sum_{j=1}^k 2^{\ell_j}$ ，使得 $S(n+M)$ 最小。
由於 $n < 2^{30}$ ，二進位長度約為 30。

當 $k$ 足夠大時 ( $k \ge 32$ )：
我們擁有足夠的「預算」來填補 $n$ 二進位中的空隙並引發連鎖進位，最終可以將 $n$ 變成一個 $2$ 的冪次（即 $S(n_{final}) = 1$ ）。
此時最大得分為 $S(n) + k - 1$ 。

為什麼是 32？

因為 $n$ 最多 30 位，只要能湊出足夠的進位，就能不斷合併低位的 1，直到只剩下一個最高位的 1。32 次操作綽綽有餘。

3. 數位 DP (Digit DP)

當 $k$ 較小時，我們無法保證能將結果變成 $2$ 的冪次，此時使用數位 DP 來尋找最優解。
我們從低位到高位處理，決定每一位是否要分配一個 $2^i$ 的加法操作。

狀態定義：dfs(i, j, carry)

$i$ ：當前處理的位元位置（從 0 開始）。
$j$ ：剩餘可用的操作次數（預算）。
$carry$ ：來自低位的進位值。

轉移方程：
對於第 $i$ 位，設 $n$ 的第 $i$ 位為 $b$ 。我們有兩種選擇：

不在此位加 $2^i$ ：消耗 0 次操作。
- 當前位總和 tot = b + carry
在此位加 $2^i$ ：消耗 1 次操作（需 $j > 0$ $j > 0$ ）。
- 當前位總和 tot = b + carry + 1

計算該位留下的 bit (tot & 1) 與產生的新進位 (tot >> 1)，取兩者中能使後續 Popcount 最小的方案。

邊界條件 (Base Case)：
當 $n$ 的位元都處理完且沒有進位時 ((n >> i) == 0 and carry == 0)：
此時若還有剩餘預算 $j$ ，相當於我們還需要在更高的位元加上 $j$ 個 $2$ 的冪次。
由於我們已經超過了 $n$ 的最高位，能得到的最小 Popcount 發生在加上 $j$ 個 $2^i$ 時。
這個數值的 Popcount 即為 j.bit_count()。

複雜度分析

時間複雜度： $\mathcal{O}(k \log n)$ $O (k lo g n)$ 。
- 狀態數量為 $O(k \log n)$ ，每個狀態需要 $O(1)$ 的時間來計算。
- 由於 DP 中 $k$ 被限制在 32 以內，且位數約為 30，每個 Testcase 幾乎是常數時間。
空間複雜度： $\mathcal{O}(k \log n)$ 。

Code

from functools import cache

def solve():
    n, k = map(int, input().split())

    if k >= 32:
        print(n.bit_count() + k - 1)
    else:
        @cache
        def dfs(i, j, carry):
            if (n >> i) == 0 and carry == 0:
                return j.bit_count()
            if j < 0:
                return float('inf')
            res = float('inf')
            b = (n >> i) & 1
            for t in range(2):
                tot = b + carry + t
                res = min(res, (tot & 1) + dfs(i + 1, j - t, tot >> 1))
            return res
        print(n.bit_count() + k - dfs(0, k, 0))

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()