「POI2007 R3」四进制天平 Quaternary Balance 题解

题目大意

我们需要用质量为 $4^k$ 的砝码（$k$ 是非负整数）在天平上称量重量为 $n$ 的金子，要求：

1. 使用的砝码数量尽可能少
2. 在满足最少砝码的前提下，求不同的称量方案数
3. 结果对 $10^9$ 取模

核心思想

1. 四进制表示

因为砝码重量都是 $4$ 的幂，可以想到用四进制来分析问题。

将金子重量 $n$ 表示为四进制：

$$n = \sum_{i=0}^{L} d_i \times 4^i \quad (0 \le d_i \le 3) $$

2. 天平状态分析

对于每个四进制位 $d_i$，有三种情况：

• 放在右盘（减）：直接使用 $d_i$ 个重量为 $4^i$ 的砝码
• 放在左盘（加）：使用 $(4-d_i)$ 个重量为 $4^i$ 的砝码放在左盘，同时在右盘加一个 $4^{i+1}$ 的砝码
• 借位处理：可以从高位借位，$d_i$ 变成 $d_i+4$，然后减去

3. 动态规划状态定义

设 $dp[i][carry]$ 表示处理到第 $i$ 位（从低位开始），当前进位为 $carry$ 时的状态：

• $carry \in \{-1, 0, 1\}$ 表示来自低位的借位或进位
• 我们需要同时记录：最少砝码数量和对应的方案数

更精确地说，每个状态存储两个值：

• $cnt$：使用的最少砝码数
• $ways$：对应的方案数

4. 状态转移

对于当前位值 $x = d_i + carry_{in}$（考虑进位后），我们可以：

1. 直接使用砝码：使用 $x$ 个 $4^i$ 的砝码在右盘，$carry_{out} = 0$
2. 补到4：使用 $(4-x)$ 个 $4^i$ 的砝码在左盘，产生进位 $+1$ 到高位
3. 借位：如果 $x > 0$，可以考虑从高位借位，但需要结合后续处理

实际处理时，$x$ 的可能值为 $0,1,2,3,4,5$（考虑进位-1到+1）

算法步骤

1. 将 $n$ 转换为四进制数组

vector<int> to_base4(string n) {
    vector<int> digits;
    // 高精度除法，反复除以4
    while (n != "0") {
        int rem = 0;
        string next;
        for (char c : n) {
            int cur = rem * 10 + (c - '0');
            next.push_back((cur / 4) + '0');
            rem = cur % 4;
        }
        // 去除前导零
        int start = 0;
        while (start < next.size() && next[start] == '0') start++;
        if (start == next.size()) next = "0";
        else next = next.substr(start);
        
        digits.push_back(rem);
        n = next;
    }
    return digits;  // 低位在前
}

2. 动态规划

const int MOD = 1e9;
const int INF = 1e9;

struct State {
    int cnt;     // 最少砝码数
    int ways;    // 方案数
    
    State() : cnt(INF), ways(0) {}
    State(int c, int w) : cnt(c), ways(w) {}
    
    void update(const State& other) {
        if (other.cnt < cnt) {
            cnt = other.cnt;
            ways = other.ways;
        } else if (other.cnt == cnt) {
            ways = (ways + other.ways) % MOD;
        }
    }
};

State dp[2][3];  // dp[当前位][进位(-1,0,1)]

3. 状态转移方程

设当前位值为 $x = digit + carry$：

• 情况1：放 $x$ 个砝码在右盘，$new\_carry = 0$
• 情况2：放 $(4-x)$ 个砝码在左盘，$new\_carry = 1$
• 情况3：如果 $x < 0$（需要借位），则 $x += 4$，$new\_carry = -1$

砝码数增加 $|x|$ 或 $|4-x|$

完整代码框架

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

const int MOD = 1e9;
const int INF = 1e9;

struct State {
    int cnt;
    int ways;
    
    State() : cnt(INF), ways(0) {}
    State(int c, int w) : cnt(c), ways(w) {}
    
    void update(const State& other) {
        if (other.cnt < cnt) {
            cnt = other.cnt;
            ways = other.ways;
        } else if (other.cnt == cnt) {
            ways = (ways + other.ways) % MOD;
        }
    }
};

// 高精度转换为四进制
vector<int> to_base4(const string& s) {
    vector<int> digits;
    string n = s;
    
    while (n != "0") {
        int rem = 0;
        string next;
        
        for (char c : n) {
            int cur = rem * 10 + (c - '0');
            next.push_back((cur / 4) + '0');
            rem = cur % 4;
        }
        
        // 去除前导零
        int start = 0;
        while (start < next.size() && next[start] == '0') start++;
        if (start == next.size()) next = "0";
        else next = next.substr(start);
        
        digits.push_back(rem);
        n = next;
    }
    
    return digits;  // 低位在前
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string n_str;
    cin >> n_str;
    
    vector<int> digits = to_base4(n_str);
    int len = digits.size();
    
    // dp[进位状态][0/1]：当前位和进位
    // 进位状态：0表示-1，1表示0，2表示1
    State dp[3][2];
    int cur = 0, nxt = 1;
    
    // 初始化
    dp[1][cur] = State(0, 1);  // 进位为0，砝码数0，方案数1
    
    for (int i = 0; i < len; i++) {
        int d = digits[i];
        
        // 初始化下一层
        for (int c = 0; c < 3; c++) {
            dp[c][nxt] = State();
        }
        
        // 状态转移
        for (int carry_state = 0; carry_state < 3; carry_state++) {
            int carry = carry_state - 1;  // -1, 0, 1
            
            if (dp[carry_state][cur].cnt == INF) continue;
            
            int base_cnt = dp[carry_state][cur].cnt;
            int base_ways = dp[carry_state][cur].ways;
            
            // 当前位的实际值
            int x = d + carry;
            
            // 情况1：直接使用x个砝码（放在右盘）
            if (x >= 0 && x <= 3) {
                int new_carry = 0;
                State new_state(base_cnt + x, base_ways);
                dp[new_carry + 1][nxt].update(new_state);
            }
            
            // 情况2：补到4（放在左盘）
            if (x >= 0 && x <= 4) {
                int new_carry = 1;
                State new_state(base_cnt + (4 - x), base_ways);
                dp[new_carry + 1][nxt].update(new_state);
            }
            
            // 情况3：借位
            if (x < 0 || x > 3) {
                // 借位处理：x < 0时，需要+4；x > 3时可能需要特殊处理
                // 实际上x只能是-1,0,1,2,3,4,5
                if (x < 0) {
                    int new_carry = -1;
                    State new_state(base_cnt + (4 + x), base_ways);
                    dp[new_carry + 1][nxt].update(new_state);
                }
            }
        }
        
        // 交换当前和下一层
        swap(cur, nxt);
    }
    
    // 最终结果：处理完所有位后，进位必须为0
    State result = dp[1][cur];  // carry = 0
    
    cout << result.ways % MOD << endl;
    
    return 0;
}

样例解析

输入：166

四进制表示：$166_{10} = 2212_4$（验证：$2×64 + 2×16 + 1×4 + 2×1 = 128+32+4+2=166$）

动态规划过程：

• 处理各位，考虑不同进位情况
• 最终找到最少需要7个砝码
• 有3种不同的方案

输出：3

复杂度分析

• 四进制转换：$O(L^2)$，其中 $L$ 是十进制数的长度（最大1000）
• 动态规划：$O(L × 3 × 常数)$，$L$ 是四进制位数（约 $log_4 n ≈ 500$）
• 总复杂度可行

总结

本题的关键在于：

1. 将问题转化为四进制表示
2. 每个四进制位的三种处理方式
3. 使用动态规划同时追踪最少砝码数和方案数
4. 注意高精度处理和进位状态

这种"进制转换+动态规划"的组合是解决此类天平称量问题的经典方法。