CF2173D Taiga's Carry Chains 题解

Mier_Samuelle · 2025-12-16 23:38:40 · 题解

官解做法。

首先考虑 k 很大的情况，我们每次都在最低的会产生进位的数位上进行操作，最终答案为 \text{popcount}(n)+k-1。

事实上，不难发现答案为 \text{popcount}(n)+k-\text{popcount}(n')，其中 n' 为所有操作后 n 的值。其中 \text{popcount}(n)+k 是定值，故我们只需最小化 \text{popcount}(n') 的值。

定义 dp_{i,j,0/1} 为考虑最低的 i 个数位，进行 j 次操作，第 i 位不进位 / 进位时，\text{popcount}(n') 的最小值。据此转移即可。

时间复杂度 O(wk)，其中 w=64。

:::success[代码]

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int MAXN = 65, MAXK = 35;
int dp[MAXN][MAXK][2], n, k;
void solve(){
    cin >> n >> k;
    if (k >= 32){
        cout << __builtin_popcount(n) + k - 1 << endl;
        return;
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;
    for (int i = 0; i < 64; i++){
        int st = (n >> i) & 1;
        for (int j = 0; j <= k; j++){
            for (int c = 0; c <= 1; c++){
                int nc = (st + c) >> 1, val = (st + c) & 1;
                dp[i + 1][j][nc] = min(dp[i + 1][j][nc], dp[i][j][c] + val);
                nc = (st + c + 1) >> 1, val = (st + c + 1) & 1;
                dp[i + 1][j + 1][nc] = min(dp[i + 1][j + 1][nc], dp[i][j][c] + val);
            }
        }
    }
    int minn = 2e9;
    for (int j = 0; j <= k; j++){
        for (int c = 0; c <= 1; c++){
            minn = min(minn, dp[64][j][c] + c);
        }
    }
    cout << __builtin_popcount(n) + k - minn << endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::